Использование A * для решения задачи коммивояжера

Question

Мне было поручено написать реализацию алгоритма A * (эвристика предоставлена), которая решит проблему коммивояжера. Я понимаю алгоритм, он достаточно прост, но я просто не вижу кода, который его реализует. Я имею в виду, я понимаю. Приоритетная очередь для узлов, отсортированная по расстоянию + эвристика (узел), добавляет ближайший узел к пути. Вопрос, например, что произойдет, если ближайший узел не может быть достигнут от предыдущего ближайшего узла? Как на самом деле взять «граф» в качестве аргумента функции? Я просто не вижу, как на самом деле функционирует алгоритм, как код.

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

Вы можете получить график, по которому некоторые узлы никогда не достигаются, если всегда идти ближе всего.

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

Answer 1

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

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

Set Начальное состояние: агент в стартовом городе и не посещал другие города

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

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

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

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

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

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

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

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

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

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

Как на самом деле взять «граф» в качестве аргумента функции?

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

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

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

Answer 6

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

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

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