Использование A * для решения Traveling Salesman

Ответ 1

Я нашел решение здесь

Используйте минимальное связующее дерево как эвристику.

Set Исходное состояние: агент в стартовом городе и не посетил какой-либо другой город.

Состояние цели: агент посетил все города и снова достиг нового города.

Функция преемника: создает все города, которые еще не посетили

Граничная стоимость: расстояние между городами, представленными узлами, использует эту стоимость для расчета g (n).

h (n): расстояние до ближайшего нераскрытого города от текущего города + расчетное расстояние до всех незаметных городов (используемая здесь эвристика MST) + ближайшая дистанция от города до центра города. Обратите внимание, что это допустимая эвристическая функция. Вы можете рассмотреть вопрос о сохранении списка посещенных городов и списке городов, которые не были открыты для облегчения вычислений.

Ответ 2

Если это просто проблема понимания алгоритма и того, как он работает, вы можете рассмотреть возможность рисования графика на бумаге, присвоения ему веса и его вычеркивания. Также вы можете найти некоторые анимации, которые показывают кратчайший путь Дейкстры, Wikipedia имеет хороший. Единственная разница между Dijkstra и A * заключается в добавлении эвристики, и вы останавливаете поиск, как только достигнете цели node. Что касается использования этого решения для решения TSP, удачи с этим!

Ответ 3

Подумайте об этом немного более абстрактно. Забудьте о A * на мгновение, это просто дикстра с эвристикой в ​​любом случае. Раньше вы хотели получить от A до B. Какова была ваша цель? Чтобы добраться до B. Цель заключалась в том, чтобы добраться до B с наименьшими затратами. В любой момент, каково ваше нынешнее "состояние"? Вероятно, просто ваше местоположение на графике.

Теперь вы хотите начать с A, а затем перейти к B и C. Какова ваша цель сейчас? Передавать как B, так и C, сохраняя наименьшую стоимость. Вы можете обобщить это с большим количеством узлов: D, E, F,... или только N узлов. Теперь, в любой момент, каково ваше текущее "состояние"? Это очень важно: это НЕ только ваше местоположение на графике - это также то, что из B или C или любых узлов, которые вы посетили до сих пор в поиске.

Внесите свой первоначальный алгоритм, чтобы он вызывал некоторую функцию, спрашивая, достиг ли она "состояния цели" после перемещения X. Раньше функция только что говорила "да, вы в состоянии B, поэтому вы находитесь в цели". Но теперь пусть эта функция вернется "да, вы находитесь в состоянии цели", если путь поиска прошел через каждую из интересующих объектов. Он будет знать, прошел ли поиск по всем интересующим точкам, потому что он включен в текущее состояние.

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

Ответ 4

Путаница здесь заключается в том, что граф, на котором вы пытаетесь решить TSP, не график, в котором вы выполняете поиск A *.

Смотрите связанный: алгоритм решения Sudoku С++

Чтобы решить эту проблему, вам необходимо:

• Определите свой:
  • Состояние TSP
  • Начальное состояние TSP
  • Состояние цели (ов) TSP
  • Функция преемника состояния TSP
  • Эвристика состояния TSP
• Примените общий алгоритм A * к этому графику состояния TSP

Быстрый пример, который я могу придумать:

• Состояние TSP: список узлов (городов), находящихся в цикле TSP
• Начальное состояние TSP: список, содержащий один node, домашний город коммивояжера.
• Состояние цели TSP: состояние является целью, если оно содержит каждый node в графе городов
• Функция преемника TSP: может добавить любой node (город), который не находится в текущем цикле, в конец списка узлов цикла, чтобы получить новое состояние
  • Стоимость перехода равна стоимости края, добавляемого в цикл
• Эвристика состояния TSP: вы решаете

Ответ 5

Чтобы ответить на один из ваших вопросов...

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

Что касается вашего другого вопроса о ближайших узлах, не является частью поиска A *, который он будет возвращать по мере необходимости? Или вы могли бы реализовать свой собственный тип обратного отслеживания, чтобы справиться с такой ситуацией.

Ответ 6

Вопрос в том, что произойдет, если ближайший node не может быть достигнут из предыдущего ближайшего node?

Этот шаг не требуется. Как и в случае, вы не вычисляете путь от предыдущего ближайшего к текущему ближайшему, вы пытаетесь достичь своей цели node, и текущее ближайшее - это единственное, что имеет значение (например, алгоритм не заботится о том, чтобы последняя итерация была в 100 км, потому что эта итерация вы всего лишь в 96 км).

Как широкое введение, A * напрямую не конструирует путь: он исследует, пока он определенно не знает, что путь содержится в исследуемой области, а затем конструирует путь на основе информации, записанной во время исследования.

(Я собираюсь использовать код в статье Википедии в качестве эталонной реализации, чтобы помочь моему объяснению.)

У вас есть два набора узлов: closedset и openset

closedset содержит узлы, которые были полностью оценены, то есть вы точно знаете, насколько они далеки от start, и все их соседи находятся в одном из двух наборов. Это больше не вычисление, которое вы можете сделать с ними, и поэтому мы можем (вроде) игнорировать их. (В основном они полностью содержатся в пределах границы.)

openset содержит узлы "границы", вы знаете, как далеко они расположены от start, но вы еще не коснулись их соседей, поэтому они пока находятся на краю вашего поиска.

(Неявно, есть третий набор: полностью нетронутые узлы, но вы не трогаете их, пока они не находятся в openset, поэтому они не имеют значения.)

На заданной итерации, если у вас есть узлы для изучения (т.е. узлы в openset), вам нужно выяснить, какой из них нужно исследовать. Это задача эвристики, она в основном дает вам подсказку о том, какой пункт на границе будет лучше всего исследовать дальше, сообщив вам, какой node он считает самым коротким путем к goal.

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

Сначала openset содержит только start, но затем вы повторяетесь и на каждом шаге граница немного расширяется (в наиболее перспективном направлении), пока вы не достигнете значения goal.

Когда A * действительно проводит исследование, он не беспокоится о том, откуда пришли узлы. Это не нужно, потому что он знает свое расстояние от start и эвристическую функцию и все, что ему нужно.

Однако для восстановления пути позже вам потребуется некоторая запись пути, это то, что camefrom. Для данного node, camefrom связывает его с node, ближайшим к start, поэтому вы можете восстановить кратчайший путь, следуя ссылкам назад от goal.

Как фактически взять "график" в качестве аргумента функции?

Передавая одно из представлений графа.

Я действительно не вижу, как A * относится к TSP. Я имею в виду, найдя маршрут от А до Б, конечно, я понял. Но TSP? Я не вижу связи.

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