Выбор между подходом грубой силы и параллельными потоками

Question

У меня вопрос по поводу графиков.Рассмотрим граф с узлами и ребрами, каждое ребро имеет стоимость.Проблема состоит в том, чтобы посетить все узлы, чтобы сумма затрат пройденных ребер была наименьшей (я думаю, проблема с коммивояжером).

Какой подход вы бы порекомендовали?Использование метода грубой силы с помощью рекурсии или метода грубой силы с помощью нерестовых нитей для одновременного перемещения по различным путям и расчета их стоимости.

Или у вас есть лучший способ решения этой проблемы?

Answer 1

TSP - это NP hard.Смотрите википедию.Это ужасно масштабируется.Многопоточность на 4-ядерном процессоре может сделать его в 4 раза быстрее, что ничто по сравнению со 100, 1000 или 1000000 раз, когда он работает медленнее, если вы пытаетесь решить проблему чуть большего размера.Просто попробуйте это с данными реального размера, это может занять годы.

Одним из решений является метаэвристика, есть несколько библиотек, таких как Drools Planner (с открытым исходным кодом, Java).Взгляните на пример TTP.

Answer 2

Рекурсия проще, и, поскольку она является грубой силой, многопоточность не гарантирует, что вы получите решение быстрее. Но прежде чем изобретать велосипед, ознакомьтесь с Concorde TSP Solver:

http://www.tsp.gatech.edu/concorde/index.html

Это бесплатная загрузка и включает источник.

Answer 3

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

Answer 4

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