#algorithm #graph #graph-theory #graph-algorithm #path-finding
#алгоритм #График #теория графов #граф-алгоритм #поиск пути
Вопрос:
Итак, у меня следующий макет:
Цель состоит в том, чтобы собрать все желтые блоки, перемещая белый шар. Я пытаюсь придумать алгоритм, который вычислит эффективный путь, однако я не слишком уверен, с чего начать.
Изначально я думал об алгоритмах поиска путей, таких как Djikstra и A *, но они, похоже, не соответствуют моей цели. Я также думал о гамильтоновых путях, которые ближе к тому, что я хочу, но, похоже, все еще не решают проблему.
Любые предложения о том, какой алгоритм можно использовать, будут оценены.
Комментарии:
1. Это проблема коммивояжера .
2. Правда ли это? Мне не нужно возвращаться к начальной точке, просто соберите все блоки.
3. @JasonB Это эквивалентно. Вы можете добавить дополнительный узел, связанный со всеми остальными, тогда оптимальный цикл в этом графе соответствует оптимальному открытому пути в оригинале, и наоборот.
4. Почему бы не работать простым BFS или DFS?
5. @AndrewScott По-видимому, вопрос не в том, чтобы путешествовать по каждой вершине один раз. Речь идет о минимизации длины общего обхода при сборе блоков. Отсюда и термин «эффективный путь».
Ответ №1:
Ваша проблема имеет классическое название в литературе, это проблема минимального гамильтонова блуждания. Будьте осторожны, чтобы не перепутать его с проблемой минимального гамильтонова пути, его «кузеном», потому что он намного более известен и намного, намного сложнее (нахождение гамильтонова обхода может быть выполнено за полиномиальное время, нахождение гамильтонова пути является NP-полным). Проблема коммивояжера — это другое название проблемы минимального гамильтонова пути (путь, а не прогулка).
Ресурсов по этой проблеме очень мало, но, тем не менее, вы можете взглянуть на статью под названием «Алгоритм поиска короткого замкнутого обхода в графе» Такамизава, Нисидзеки и Сайто от 1980 года. Они предоставляют полиномиальный алгоритм для поиска такого пути.
Если документ немного сложен для чтения или алгоритм слишком сложен для реализации, я предлагаю вам использовать алгоритм Кристофидеса, потому что он выполняется за полиномиальное время и каким-то образом эффективен (это 2-приближение, если я хорошо помню).).
Другим возможным подходом было бы использовать жадный алгоритм, например, алгоритм ближайшего не посещаемого соседа (начните с чего-нибудь, перейдите к ближайшему узлу, который еще не находится в прогулке, повторяйте, пока все не будут в прогулке).
На самом деле, я думаю, что самое простое и, возможно, лучшее простое решение — стать жадным.