Question

A) Задача «Коммивояжер» - это известный пример проблемы, для которой легко угадать и проверить решение, но для точного решения которой требуется экспоненциальное время. Вот, неформально, проблема: вам дается карта 100 городов США с расстоянием между каждой парой городов. Ваша задача - начать с определенного города (скажем, Боулдера); посетить каждый из 99 других городов ровно один раз; а затем вернитесь в Боулдер. Естественно, вы можете выбрать для этого множество маршрутов. Ваша цель состоит в том, чтобы найти маршрут минимальной общей дистанции, который достиг бы вашей цели. (Иногда цель формулируется путем указания целевого значения: то есть ваша цель - найти любой маршрут, который посещает каждый город ровно один раз и требует не более M миль пути.) Безошибочный подход к этой проблеме состоит в том, чтобы (во-первых) перечислить все возможные маршруты из 99 городов (мы предполагаем, что Боулдер - первый и последний город); отсортировать список по пройденным милям; и выберите самый дешевый маршрут. Каков наш список возможных маршрутов из 99 городов запишите свой ответ в виде коэффициента и факториала (например, X!). B) Иногда, когда люди впервые слышат о проблеме коммивояжера, они думают: «О, это несложно. Начните с города на карте; двигайтесь к ближайшему не посещенному городу; а затем на каждом последующем шаге переходите к ближайшему, еще не посещенному. город, пока не закончишь. " Эта стратегия называется «жадной стратегией»: она всегда идет к ближайшему разрешенному шагу. Теперь рассмотрим четыре города, расположенных вдоль числовой прямой. Город A находится в точке 0, город B в точке 2, город C в точке 3 и город D в точке 10: А Б В Г 00-01-02-03-04-05-06-07-08-09-10 Теперь начните тур коммивояжера в Городе B и используйте жадный алгоритм, чтобы выбрать свой тур по четырем городам, начиная и заканчивая в Б. Как долго длится тур жадного алгоритма? C) Есть сторонники нового типа вычислений, который использует нити ДНК в пробирке для выполнения вычислений - для решения таких проблем, как проблема «коммивояжер». Эти сторонники отмечают, что в небольшом томе есть триллионы небольших фрагментов ДНК, которые могут (фактически) попробовать триллионы различных туров для продавца и сообщить о самом коротком туре. Вот ваш вопрос: предположим, что продавцу нужно посетить N городов. Насколько большим должно быть N, чтобы количество туров, которые ему пришлось бы протестировать (в худшем случае), превысило триллион? (И вам понадобится калькулятор!)