Как алгоритм ветвей и границ быстрее алгоритма грубой силы при решении задачи коммивояжера?

Я понимаю, как работает алгоритм ветвей и границ для решения задачи коммивояжера, но у меня возникают проблемы с попыткой понять, почему алгоритм работает быстрее грубой силы. Как я понимаю, в конце концов вы пройдете все пути. Может ли кто-нибудь показать пример, в котором алгоритм B&B работает быстрее, чем перебор всех путей?


algorithm branch-and-bound traveling-salesman brute-force
person Fateh    schedule 16.05.2020    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Допустим, у нас есть следующий экземпляр Euclidean TSP:

0                                                       7
1                                                       6
2                                                       5
3                                                       4

Каждое число — это вершина, а отрезки между всеми узлами — ребра (не нарисованные).

Подход грубой силы проверил бы все 8! = 40320 возможных путей.

Алгоритм ветвей и границ, с другой стороны, может начинаться с пути 0→1→2→3→4→5→6→7, который оказывается оптимальным, и отфильтровывать все другие пути, которые начинаются с чередования между узлами слева и справа более одного раза. Например, когда он рассматривает неполный путь 0→4→1, он увидит, что длина этого префикса уже превышает длину кратчайшего пути, найденного до сих пор, поэтому нет необходимости спускаться и проверять каждый из путей, начинающихся с 0→ 4→1 индивидуально. Один только этот префикс отфильтровывает 5! = 120 отдельных путей, но есть 96 таких чередующихся префиксов, что в совокупности отфильтровывает 11520 потенциальных решений, или 29% пространства решений.

person Yakov Galka    schedule 16.05.2020