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

Question

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

Например:

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

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

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

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

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

Спасибо.

Edit:

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

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

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

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

Answer 1

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

Answer 2

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

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

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

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