Java: коммивояжер - найден полиномиальный алгоритм

Изменить: улучшение этого алгоритма. был найден. Добро пожаловать, чтобы увидеть это.

Этот вопрос является улучшением моего старого вопроса. Теперь я хочу показать вам пример кода Java и более подробно объяснить мой алгоритм. Детали.

Я думаю, что нашел полиномиальный алгоритм для получения точного решения задачи коммивояжера. Моя реализация построена из 5 шагов:

1) Быстрая настройка
2) Поиск решения
3) Условие остановки 1
4) Условие остановки 2
5) Условие остановки 3

Я хочу начать с шага 2 и 3, и если я не ошибусь, я покажу вам остальную часть.

Итак, что я собираюсь показать вам сейчас, это не полиномиальный алгоритм, а улучшение алгоритм Хелда-Карпа, решающий задачу за время O(n^2 2^n)

Допустим, мы хотим решить маршрут из 6 городов с помощью алгоритма brout. Есть (6-1)! = 120 вариантов, нам нужно протестировать их все и вернуть найденный кратчайший маршрут. Таким образом, это будет выглядеть примерно так (названия городов: A, B, C, D, E, F):

Вариант 1: А -> В -> С -> D -> Е -> F -> А
Вариант 2: A -> B -> C -> D -> F -> E -> A
Вариант 3: A -> C -> B -> D -> E -> F -> A
Вариант 4: A -> C -> B -> D -> F -> E -> A
.
.
Вариант 120

Теперь я говорю, что после расчета вариантов 1 и 2 вы можете пропустить варианты 3 и 4. Как вы это делаете? Это просто: при расчете варианта 1 вам нужно рассчитать, каким будет кратчайший маршрут, начинающийся из города D, заканчивающийся в городе A и проходящий через города E, F, на самом деле он рассчитывает варианты 1 и 2. Что мы хотим сделать, так это построить карту из 4 городов, где мы задаем, что будет первым и последним городом, в этом примере при расчете варианта 1 вы создаете карту D, E, F, A, которая содержит данные о том, что будет кратчайшим путем из от D до A через E,F. Итак, теперь, когда вы начнете рассчитывать варианты 3 и 4, вы можете остановиться, достигнув города D, потому что вы уже знаете, какой будет кратчайший маршрут, начинающийся в городе D, заканчивающийся в городе A и проходящий через города E, F.

Это принцип, который я использовал в своем алгоритме. Я запускаю алгоритм перебора и сопоставляю все вложенные результаты, эти результаты не являются вложенными маршрутами, не путайте. Это всего лишь часть вычислений, которые необходимо выполнить, чтобы найти кратчайший маршрут. Поэтому каждый раз, когда я узнаю, что делаю один и тот же расчет, я использовал решение с карты.

Вот результат работы моего алгоритма по 19 городам. Это всего лишь один пример, но он имеет большее значение, чем это. Фактически это все результаты для 19 городов. Независимо от того, какие 19 городов будут введены, алгоритм всегда создаст одинаковое количество карт, выполнит одинаковое количество действий и разрешится за одно и то же время.

Source(19)  [10.0,65.0, 34.0,52.0, 37.0,98.0, 39.0,44.0, 43.0,37.0, 45.0,89.0, 66.0,79.0, 69.0,74.0, 7.0,76.0, 70.0,15.0, 77.0,27.0, 78.0,11.0, 78.0,13.0, 80.0,5.0, 81.0,38.0, 82.0,64.0, 87.0,7.0, 90.0,61.0, 93.0,31.0]
Finish MapEngine test after 321550 mills
Created: 20801457
Map(3)  Write    2448       Read     34272
Map(4)  Write    12240      Read     159120
Map(5)  Write    42840      Read     514080
Map(6)  Write    111384     Read     1225224
Map(7)  Write    222768     Read     2227680
Map(8)  Write    350064     Read     3150576
Map(9)  Write    437580     Read     3500640
Map(10) Write    437580     Read     3084270
Map(11) Write    352185     Read     2344256
Map(12) Write    245131     Read     1382525
Map(13) Write    135638     Read     570522
Map(14) Write    54320      Read     156758
Map(15) Write    15077      Read     27058
Map(16) Write    2809       Read     2087
Map(17) Write    306        Read     0
Map(18) Write    18         Read     0
Map(19) Write    1          Read     0

0) 295.5947584525372>   [10.0,65.0, 34.0,52.0, 39.0,44.0, 43.0,37.0, 70.0,15.0, 78.0,13.0, 78.0,11.0, 80.0,5.0, 87.0,7.0, 77.0,27.0, 93.0,31.0, 81.0,38.0, 90.0,61.0, 82.0,64.0, 69.0,74.0, 66.0,79.0, 45.0,89.0, 37.0,98.0, 7.0,76.0, 10.0,65.0]

Source(19) — это входные города. Моему ПК потребовалось 321550 mills для расчета (около 5 минут). Created: 20801457 представляют количество созданных экземпляров поиска (все разы, когда я использовал карту или создавал карту. Вам нужно будет увидеть код, чтобы лучше понять это число). Map(3) говорит о количестве созданных карт с 3 городами. Он создал 2448 карт 3 городов и использовал их 34272 раза.

Количество карт, которые мой алгоритм создаст с размером K городов в маршруте N городов, будет: Количество раз, когда я могу выбрать первый город на моей карте: N умножает количество раз, которое я могу выбрать отличный выбор моих городов от остальных городов: (n-1)! /((n-k-1)!*(k-1)!). Это пришло к n! / ((n - k - 1)! * (k-1)!). Если предположить, что создание карты размера 3 является атомарным действием, то эффективность моего алгоритма будет равна сумме всех этих карт.

Поэтому мой алгоритм имеет следующую эффективность.

Н*(Н-1)*(Н-2)/2! + Н * (Н - 1) * (Н - 2) * (Н - 3) / 3! + Н * (Н - 1) * (Н - 2) * (Н - 3) (Н - 4) / 4! + ... Н! / (Н - 1)! = N * (N - 1) * (N - 2) / 2! + Н * (Н - 1) * (Н - 2) * (Н - 3) / 3! + Н * (Н - 1) * (Н - 2) * (Н - 3) (Н - 4) / 4! + ... Н

Так что же это за эффективность?

Это похоже на экспоненциальную функцию O(N^C*2^N), где C чуть меньше единицы. Я нашел это, решив алгоритм эффективности с N от 7 до 100 и сравнив его с предыдущими результатами (результат N = 9 с N = 8, результат N = 24 с N = 23), и я обнаружил, что для большие числа N результат сравнения равен 2. Затем я сделал то же самое с эффективностью традиционного алгоритма динамического программирования. Вот список того, что я получил:

Столбец 1 — N, столбец 2 — сравнение эффективности моего алгоритма, столбец 3 — сравнение алгоритма динамического программирования, а столбец 4 — сравнение эффективности моего алгоритма, умноженное на N.

7   2.55769     2.72222     2.98397 
8   2.40601     2.61224     2.74973 
9   2.31562     2.53125     2.60507 
10  2.2582      2.46913     2.50912 
11  2.21972     2.42        2.44169 
12  2.19258     2.38016     2.39191 
13  2.17251     2.34722     2.35356 
14  2.15701     2.31952     2.32293 
15  2.14456     2.29591     2.29774 
16  2.13424     2.27555     2.27652 
17  2.12548     2.25781     2.25832 
18  2.1179      2.24221     2.24248 
19  2.11124     2.22839     2.22853 
20  2.10533     2.21606     2.21614 
21  2.10003     2.205       2.20503 
22  2.09525     2.19501     2.19503 
23  2.09091     2.18595     2.18596 
24  2.08696     2.17769     2.17769 
25  2.08333     2.17013     2.17014 
26  2.08        2.1632      2.1632 
27  2.07692     2.1568      2.1568 
28  2.07407     2.15089     2.15089 
29  2.07142     2.1454      2.1454 
30  2.06896     2.1403      2.1403 
31  2.06666     2.13555     2.13555 
32  2.06451     2.13111     2.13111 
33  2.0625      2.12695     2.12695 
34  2.0606      2.12304     2.12304 
35  2.05882     2.11937     2.11937 
36  2.05714     2.11591     2.11591 
37  2.05555     2.11265     2.11265 
38  2.05405     2.10956     2.10956 
39  2.05263     2.10664     2.10664 
40  2.05128     2.10387     2.10387 
41  2.05        2.10125     2.10125 
42  2.04878     2.09875     2.09875 
43  2.04761     2.09637     2.09637 
44  2.04651     2.0941      2.0941 
45  2.04545     2.09194     2.09194 
46  2.04444     2.08987     2.08987 
47  2.04347     2.0879      2.0879 
48  2.04255     2.08601     2.08601 
49  2.04166     2.0842      2.0842 
50  2.04081     2.08246     2.08246 
51  2.04        2.0808      2.0808 
52  2.03921     2.0792      2.0792 
53  2.03846     2.07766     2.07766 
54  2.03773     2.07618     2.07618 
55  2.03703     2.07475     2.07475 
56  2.03636     2.07338     2.07338 
57  2.03571     2.07206     2.07206 
58  2.03508     2.07079     2.07079 
59  2.03448     2.06956     2.06956 
60  2.03389     2.06837     2.06837 
61  2.03333     2.06722     2.06722 
62  2.03278     2.06611     2.06611 
63  2.03225     2.06503     2.06503 
64  2.03174     2.06399     2.06399 
65  2.03125     2.06298     2.06298 
66  2.03076     2.06201     2.06201 
67  2.0303      2.06106     2.06106 
68  2.02985     2.06014     2.06014 
69  2.02941     2.05925     2.05925 
70  2.02898     2.05839     2.05839 
71  2.02857     2.05755     2.05755 
72  2.02816     2.05673     2.05673 
73  2.02777     2.05594     2.05594 
74  2.02739     2.05516     2.05516 
75  2.02702     2.05441     2.05441 
76  2.02666     2.05368     2.05368 
77  2.02631     2.05297     2.05297 
78  2.02597     2.05228     2.05228 
79  2.02564     2.05161     2.05161 
80  2.02531     2.05095     2.05095 
81  2.025       2.05031     2.05031 
82  2.02469     2.04968     2.04968 
83  2.02439     2.04907     2.04907 
84  2.02409     2.04848     2.04848 
85  2.0238      2.0479      2.0479 
86  2.02352     2.04733     2.04733 
87  2.02325     2.04678     2.04678 
88  2.02298     2.04624     2.04624 
89  2.02272     2.04571     2.04571 
90  2.02247     2.04519     2.04519 
91  2.02222     2.04469     2.04469 
92  2.02197     2.04419     2.04419 
93  2.02173     2.04371     2.04371 
94  2.0215      2.04324     2.04324 
95  2.02127     2.04277     2.04277 
96  2.02105     2.04232     2.04232 
97  2.02083     2.04188     2.04188 
98  2.02061     2.04144     2.04144 
99  2.0204      2.04102     2.04102 
100 2.0202      2.0406      2.0406

Посмотрите, как столбцы 3 и 4 почти одинаковы. Вот как я это нашел.

Пожалуйста, проверьте мою работу, взгляните на код, скажите, согласны вы со мной или нет. Если нет, пожалуйста, покажите мне, где мой алгоритм или моя математика не работает по точному образцу. Если вы со мной согласны, то помогите мне изменить вики-страницу, показав, что эта часть моего алгоритма лучше, чем алгоритм Хельда-Карпа.

Ilya Gazman 11.10.2013 источник

comment

Если вы считаете, что нашли полиномиальное решение для коммивояжера, вам следует опубликовать научную статью, а не вопрос Stackoverflow. - Wormbo 11.10.2013

comment

так что NP = P и никаких сложных проблем больше не существует, счастливый мир! - McMannus 11.10.2013

comment

Вы до сих пор не поняли, что ваш метод не работает? Базовое предположение о том, что, зная лучший маршрут для подцепи, вы можете просто заменить эту подцепь как оптимальную в более крупной композиции после добавления большего количества городов, неверно. Вам уже сказали, что ваш метод фактически не нашел оптимального решения для примера проблемы в одном из ваших других вопросов: cs.stackexchange .com/questions/14902 Как насчет того, чтобы заставить ваш метод хотя бы работать должным образом, прежде чем делать экстраординарные заявления и тратить чужое время впустую. Отказ видеть проблему не избавляет от нее! - Durandal 11.10.2013

comment

@Durandal Этот вопрос не связан с тем, который вы упомянули (у меня была ошибка, и я уже исправил ее). Это две разные вещи, и именно поэтому они публикуются в разных вопросах. Также, если вы считаете, что мое предположение неверно, то докажите это. Я даже исходник приложил, покажите хоть один случай, где я не прав. - Ilya Gazman 12.10.2013

comment

@Phpdna есть прикрепленный код, просто установите для логического значения ShowGuid в настройках значение true, и вы получите множество образцов. Также, пожалуйста, прочитайте мое последнее обновление поста о том, почему одного примера достаточно. - Ilya Gazman 14.10.2013

comment

Вы ведь понимаете, что O(2^N) — это экспоненциальное время, верно? Экспоненциальная сложность сложнее, чем полиномиальная сложность. - Daniel 26.11.2013

Ответы (3)

arrow_upward
10
arrow_downward

Я постараюсь разбить это на самое необходимое. Но сначала позвольте мне поблагодарить вас за решение проблемы, которая, как известно, чрезвычайно сложна. Никакой прогресс невозможен без риска.

Вы приближаетесь к TSP с точки зрения рекурсивного выражения для S(a, b, I), длины кратчайшего пути из города a в город b, a \ne b, проходящего через каждый город в неупорядоченном множестве I ровно один раз.

Имея на руках S, TSP легко решить. Для множества городов C найдите

min( D(b, a) + S(a, b, C\a\b) ) over all pairs a, b drawn from C where a \ne b

Здесь D(x, y) = D(y, x) — расстояние от города x до y, а C\a\b — это C с удаленными a и b.

Рекурсивное выражение, которое вы предлагаете для S, равно

S(a, b, I) = min( D(a, p) + S(p, q, I\p\q) + D(q, b) ) 
               over all pairs p, q drawn from I where p \ne q ,

Базовые случаи - это когда I имеет ноль или один элемент (элементы). Это довольно очевидно.

Вы предлагаете кэшировать значения S(a, b, I), чтобы такие вычисления никогда не повторялись. (Кстати, это называется запоминанием.)

Так какова стоимость этих вычислений или, что то же самое, размер кеша? Для него можно написать рекурсию, где параметр n = |I| — количество городов в промежуточном множестве:

C(n) = M(n, 2) C(n - 2) = ( n(n-1)/2 )  C(n - 2)
C(0) = C(1) = 1

Здесь M(n, m) — это комбинация n вещей, взятых m одновременно, n! / (м! (н-м)!)

Мы можем решить это. Для четного n:

C(n) = n! /  2^(n/2)

Я позволю тебе разобраться со странным случаем.

Для тура по m городам нам нужно будет повторить это для всех пар городов и соответствующих промежуточных наборов:

(m(m-1)/2) C(m-2) = m! / 2^(m/2-2)

Таким образом, ваш метод позволяет избежать экспоненциального объема работы по сравнению с наивным алгоритмом генерации всех возможных туров, но факториал все еще доминирует: эта функция является суперэкспоненциальной.

Обратите внимание на другие ваши «критерии остановки»: выше указана стоимость вычисления всех возможных значений S (a, b, I) ровно один раз. Чтобы получить алгоритм полигонального времени, вам придется придумать схему полного пропуска суперэкспоненциального числа (a,b,I) троек. Маловероятно, что вы сможете это сделать, но не позволяйте этому ослабить ваш энтузиазм.

Gene 19.10.2013

comment

Tnx, Джин. На самом деле это было только начало, я сильно улучшился и очень близко подобрался к полиномиальному решению. Вы можете найти мои последние посты на бирже стека. Получил теорию, теперь пытаюсь реализовать. Пока что я могу сделать 21 город длины за 6 секунд, на моем ноутбуке это еще не поли, но эти рекорды точно. - Ilya Gazman; 20.10.2013

arrow_upward
26
arrow_downward

Ваша работа, кажется, сводится к четырем ключевым моментам:

Вы, кажется, не понимаете, что означает полиномиальное время
Ваш алгоритм не решает общую задачу коммивояжера.
Даже если проблема, которую решает ваш алгоритм, — это задача коммивояжёра, она основана на ложном предположении, что приводит к неверным ответам.
Даже если ваш алгоритм правильно решил правильную задачу, он не работает за полиномиальное время.

Что касается пункта 1, алгоритм с полиномиальным временем — это не тот алгоритм, который можно запустить на домашнем компьютере за пять минут. Термины «поли-время», «постоянное время», «время регистрации» и т. д. относятся к тому, как алгоритм масштабируется. Предоставление результатов одного запуска алгоритма ничего нам об этом не говорит. Чтобы получить эмпирические данные об асимптотическом времени работы вашего алгоритма, вам потребуется провести усреднение по очень большому количеству случайных экземпляров задачи. Например, этот график свидетельствует о том, что в двух измерениях наивный метод отчет о диапазоне по n случайным точкам O(n) с помощью наивного метода и O(n^0.5) с использованием двумерного дерева. Я решил 10 000 случайно сгенерированных задач для количества точек от 2 до 2^(20) и нанес на график время завершения в некоторых логарифмических масштабах — градиенты этих линий свидетельствуют об асимптотическом времени выполнения алгоритмов.

Результаты одного испытания почти полностью бессмысленны. Если вы не можете строго доказать полиномиальность алгоритма, то большой, хорошо проанализированный набор эмпирических результатов подтвердит ваше утверждение и заинтересует людей. Я должен сделать большой акцент на слове «большой».

Во-вторых, ваш алгоритм решает евклидову задачу коммивояжера, а не задачу коммивояжера. Это разные наборы проблем. Хотя это различие является техническим, а ETSP по-прежнему является NP-трудным, тот факт, что вы не рассмотрели его или даже не упомянули об этом ни в одном из ваших 7 вопросов по теме, предполагает, что вы недостаточно исследовали область, прежде чем утверждать, что ваше решение действительный.

Что касается третьего пункта, насколько я понимаю из вашего вопроса, ваше решение основано на предположении, что кратчайший гамильтонов путь через вершины D E F A каким-то образом связан с кратчайшим гамильтоновым путем через вершины E F A. Это неверно. Предположим, что E->F->A — кратчайший путь через эти вершины. Если D близко к E и выбрано так, что DEF лежат на одной прямой с вершинами, расположенными в указанном порядке, то кратчайший путь будет D->E->F->A. Если D выбрано на полпути между E и F, кратчайший путь будет E->D->F->A. Выбор, аналогичный предыдущему, может дать нам такое расположение вершин, что E->F->D->A и E->F->A->D являются кратчайшими путями, и такую конструкцию можно обобщить на любое количество вершин. Знание кратчайшего гамильтонова пути через некоторое подмножество вершин ничего не говорит о ситуации, когда в дело вмешивается другая вершина.

Действительно, в одном из ваших тестовых случаев ваш алгоритм показал неправильные результаты. Вы не дали никаких объяснений того, что произошло в этом случае, и никаких указаний на то, как и даже если вы устранили эту проблему.

Наконец, указанная вами сумма больше суммы n биномиальных коэффициентов. . Похоже, что LaTeX не поддерживается на этом сайте, поэтому мы будем использовать (nCk) для обозначения биномиального коэффициента n, выберите k. Ваша сумма может быть переписана как сумма (k)(n-k)(nCk) за k=1 to n. Эта сумма явно больше, чем сумма (nCk) для k=1 to n, поэтому эта сумма должна быть больше 2^n, так что ваш алгоритм определенно не является полиномиальным, основываясь на вашем анализе. Крайне маловероятно, что любая сумма, включающая кучу факториалов, окажется полиномиально ограниченной. Если вам требуется какая-либо нетривиальная комбинаторика для выражения времени выполнения вашего алгоритма, он, вероятно, не будет выполняться за полиномиальное время.

ymbirtt 13.10.2013

comment

Спасибо за ваш ответ, ymbirtt, как бы то ни было, кажется, что вы не прочитали ни мою нижнюю строчку, ни верхнюю. Это всего лишь вторая часть моего алгоритма, и я пытаюсь доказать, что нашел лучшее решение, чем алгоритм Хельда-Карпа со временем O(2^N N^2). Я показываю здесь только один пример, потому что мой алгоритм решит все 19 городов за одно и то же время, рассчитывая одни и те же действия. Также я думаю, что вы не поняли мой пример. Я показываю там не 4 варианта, а все возможные 120 вариантов. И я говорю, что я объясняю, почему я могу избежать тестирования 30 из них. - Ilya Gazman; 14.10.2013

comment

Я только что добавил серьезное редактирование к вопросу. Теперь понятно, почему одного примера из 19 городов достаточно; Как сохранить расчеты; И почему я говорю, что это полиномиальное время, а это не так. Также я объяснил свою ошибку в предыдущих своих сообщениях. Также я могу заверить вас, что здесь нет ошибок. - Ilya Gazman; 14.10.2013

comment

Прежде всего, я хотел бы посоветовать не вносить множественные кардинальные изменения в ваши вопросы. Во-вторых, я действительно прочитал первую и последнюю части вашего вопроса - если одна часть вашего алгоритма, однако, основана на ложном предположении и занимает не менее 2 ^ n времени, без указания того, что делает ваш шаг предварительной обработки, чтобы получить вокруг этого нет смысла рассматривать все остальное. - ymbirtt; 14.10.2013

comment

Эмпирическое время работы программы фактически является случайным числом, поэтому при предоставлении фактических данных всегда рекомендуется брать несколько значений и усреднять их. Я помню из предыдущего поста - cs.stackexchange.com/q/14998/10236 - что вы не смогли проверить однако из чего-либо большего, чем 19 городов, поэтому мне любопытно, как вы собрали эти данные. Вы также не указали, что это за цифры на самом деле. Хотя единицы, в которых измеряется ваше время, не имеют значения, тот факт, что ваша эффективность, кажется, уменьшается с размером задачи, по меньшей мере странен. - ymbirtt; 14.10.2013

comment

Наконец, за последние несколько дней я неоднократно читал и перечитывал вашу схему кэширования и не вижу, как она вообще избавляет вас от работы. Если вы рассматриваете каждый возможный путь, то время, необходимое вам для рассмотрения каждого из них, не имеет значения. Вы еще посчитали (n-1)! пути, что делает ваш алгоритм не лучше, чем решение грубой силы. Я отмечаю, что теперь вы прямо сказали, что я говорю, что это полиномиальное время, а это не так. Если ваш алгоритм не является полиномиальным, я не вижу оснований утверждать, что это так. - ymbirtt; 14.10.2013

comment

Вы ошибаетесь. Я делаю ровно наоборот. Допустим, у меня есть N городов, и я строю все карты N-1. Теперь мне потребуется N-1 вычислений, чтобы найти точные решения. - Ilya Gazman; 14.10.2013

comment

давайте продолжим обсуждение в чате - ymbirtt; 14.10.2013

arrow_upward
1
arrow_downward

Вкратце: Ваш подход ничего не выиграл с точки зрения сложности проблемы.

Давайте посмотрим на сложность вашего подхода. Фактически вы вычисляете транзитивное замыкание всех подпутей, исключая более длинные из каждых двух подпутей, которые начинаются и заканчиваются в одном и том же городе, чтобы уменьшить количество оставшихся комбинаций для следующей итерации. Предположим, вы сохранили расстояния между каждой парой городов в хэш-карте, поэтому время поиска составляет O(1).

Учитывая, что у вас есть n городов, которые вы хотите включить в свой маршрут, есть пары n x (n-1).

Чтобы вычислить расстояния для всех подпутей длины 3, вы выбрали один город и объединили его с каждой парой, которая сама не включает выбранный город. Таких пар (n-1) x (n-2). Поскольку у вас есть *n) городов, которые нужно выбрать для первой позиции, у вас есть 3 x 2 x 1 пути длины 3 для расчета. Для n = 3 это означает, что у вас O(n!).

Чтобы вычислить расстояния для всех подпутей длины 4, вы повторяете процесс. На этот раз вам нужны вычисления 4 x 3 x 2 x 1. Для n = 4 это означает, что у вас O(n!). Это момент, когда ваше устранение начинает действовать. Из каждых двух путей, которые начинаются и заканчиваются в одних и тех же городах, нужно запомнить только самый короткий. Это означает, что осталось только (4 x 3 x 2 x 1)/2 путей длины 4.

Чтобы вычислить расстояния для всех подпутей длины 5, вы получаете выигрыш от исключения, сделанного на последнем шаге. Вам нужно вычислить только 5 x (4 x 3 x 2 x 1)/2. Для n = 5 это означает, что O(1/2 x n!) = O(n!). На этот раз вы можете исключить 5 из 6 путей, которые начинаются и заканчиваются в одних и тех же городах (некоторые из которых вы даже не рассчитали из-за исключения на предыдущем шаге), оставив вам (5 x 4 x 3 x 2 x 1)/6 путей длины 5.

Следовательно, для n = 6 у вас есть O(1/6 x n!), что по-прежнему равно O(n!). С каждым последующим шагом коэффициент будет уменьшаться. Это означает, что ваш алгоритм быстрее, чем наивный подход грубой силы, который не сохраняет никаких промежуточных результатов. Но ваша сложность остается O(n!).

Sven Amann 11.10.2013

comment

Если бы это было правдой, я бы смог вычислить путь 19 городов, то есть 18! = 6,40237370e+15. Итак, у вас есть ошибка, и я объясню вам, что это такое. Вы думаете, что если я вычислю города A,B,C,D, мне также нужно будет вычислить города [A,B,D,C], [A,C,B,D], [A,C,D ,B], [A,D,C,B], [A,D,B,C], но это неверно. Я сохраняю k - 1 (в данном примере k = 4) городов, которые вы можете выбрать (порядок не важен и повторение не допускается) из N - 2. Формула для этого: N! / ((Н - Р)!(Р!)) - Ilya Gazman; 11.10.2013

comment

Вы не указываете в своем посте ничего, что уберегло бы вас от вычисления всех этих перестановок. Ваше заявление о том, что не надо рассчитывать Вариант 2, потому что вы уже просчитали вместе с Вариантом 1, для меня не имеет смысла, так как вы все равно делаете расчет, только где-то еще. - Sven Amann; 11.10.2013

comment

Тогда я не знаю, как убедить вас, а не показать вам факты. Этот алгоритм решил карту 19 городов менее чем за 6 минут. Взгляните на код, посмотрите еще раз на мое объяснение и попробуйте объяснить, как это возможно. - Ilya Gazman; 11.10.2013

comment

Время вычислений не является аргументом в дискуссии о сложности. Вы всегда можете добавить больше оборудования для решения проблемы. Это не уменьшит сложность. Если вы даже не можете объяснить, почему вы думаете, что можете пропустить некоторые расчеты, как вы можете быть уверены, что ваши результаты верны? - Sven Amann; 11.10.2013

comment

Но я объяснил. Также не имеет значения, какое программное обеспечение у вас есть. Это не поможет вам выполнить 18! действия. Это число с 18 нулями. - Ilya Gazman; 11.10.2013

comment

Вы не поняли большого O. O(n!) не означает, что их n! действия для выполнения. Кстати, 18! 6.402.373.705.728.000 согласно моему калькулятору Windows. - Marius; 11.10.2013

comment

Вы объяснили, что вы можете пропустить вариант 2, потому что вы уже рассчитали его в варианте 1, который точно говорит то, что я говорю: вы делаете расчет варианта 2, только вместе с расчетом для варианта 1. Это не имеет никакого значения в с точки зрения сложности. - Sven Amann; 11.10.2013

Java: коммивояжер - найден полиномиальный алгоритм

Поэтому мой алгоритм имеет следующую эффективность.

Так что же это за эффективность?

Ответы (3)

Вопросы по теме