Посетите все узлы на графике с наименьшим количеством повторных посещений

У меня есть карта на основе плиток, где несколько плиток представляют собой стены, а другие можно пройти. плитки, по которым можно пройти, составляют график, который я хотел бы использовать при планировании пути. Мой вопрос: есть ли у них какие-либо хорошие алгоритмы для поиска пути, который посещает каждый узел на графике, сводя к минимуму повторные посещения?

Например:

пример карты http://img220.imageshack.us/img220/3488/mapq.png < / а>

Если нижняя желтая плитка является отправной точкой, лучший путь для посещения всех плиток с наименьшим количеством повторов:

пример пути http://img222.imageshack.us/img222/7773/mapd.png < / а>

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

Меня не волнует конечный узел, но важен начальный узел.

Спасибо.

Редактировать:

Я добавил изображения к своему вопросу, но не вижу их при просмотре. они здесь:

http://img220.imageshack.us/img220/3488/mapq.png

http://img222.imageshack.us/img222/7773/mapd.png

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


search path-finding graph-theory
person Community    schedule 14.04.2009    source источник
comment
Коммивояжер: xkcd.com/399   -  person CookieOfFortune    schedule 14.04.2009

Ответы (2)


arrow_upward
1
arrow_downward

Ваша формулировка плохая - она ​​позволяет свести к NP-полной задаче. Если бы вы могли свести к минимуму повторные посещения, вы могли бы довести их до 0, и тогда у вас был бы гамильтонов цикл . Это разрешимо, но сложно.

person JP Alioto    schedule 14.04.2009

arrow_upward
0
arrow_downward

Похоже, это можно было бы сопоставить с задачей коммивояжера ... и поэтому, вероятно, в конечном итоге он будет NP-полным, а эффективный детерминированный алгоритм неизвестен.

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

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

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

person Rob Walker    schedule 14.04.2009