Самый длинный путь в сетке без повторного посещения ячеек сетки

Я ищу алгоритм для поиска самого длинного пути между двумя точками в сетке с дополнительным ограничением, что вы не можете повторно посетить ячейку в сетке. (Кроме того, вы можете двигаться только вверх, вниз, влево и вправо).

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


algorithm grid path-finding longest-path language-agnostic
person Paul Manta    schedule 12.05.2013    source источник
comment
Сетка прямоугольная? Я думаю, что почти всегда можно посетить все точки сетки... если только сетка не очень маленькая.   -  person rliu    schedule 12.05.2013
comment
@roliu Он не прямоугольный.   -  person Paul Manta    schedule 12.05.2013
comment
Есть ли препятствия на сетке? Обратите внимание, что для общих графов это проблема с самым длинным путем, то есть NP-Complete   -  person amit    schedule 12.05.2013
comment
@amit Есть препятствия в том смысле, что стены могут быть где угодно на карте. Я знаю, что общая проблема является NP-трудной (неполной), но я подумал, что, может быть, этот конкретный случай можно решить за полиномиальное время. В любом случае, карты приблизительно прямоугольные, поэтому алгоритм, который заполняет прямоугольную карту, все равно будет весьма полезен.   -  person Paul Manta    schedule 12.05.2013
comment
@amit Например, я мог бы найти самый большой прямоугольник, который помещается в область, в которой я сейчас нахожусь, и заполнить его (я могу не посетить несколько ячеек, но это нормально). Затем сделайте то же самое для следующего прямоугольника и т. д.   -  person Paul Manta    schedule 12.05.2013
comment
Если веса ребер одинаковы, я бы рассмотрел кривые, заполняющие пространство.   -  person G. Bach    schedule 12.05.2013
comment
Алгоритм заполнения прямоугольника кажется выполнимым, но очень уродливым... кажется, что у него много угловых случаев. Я не уверен, что для этого есть элегантное решение, и вам, возможно, придется просто работать с ними вручную. Я думаю, что я бы заполнил прямоугольник, взяв конечную точку t и разделив сетку на четыре части, используя t в качестве центра (в основном, начало нормальной декартовой системы координат). Если начальная точка s находится в каком-то участке (скажем, юго-западном), я бы последним заполнил противоположный участок (в моем примере — северо-восточный).   -  person rliu    schedule 12.05.2013
comment
Насколько велики сетки/карты?   -  person גלעד ברקן    schedule 12.05.2013
comment
Техника для этого объясняется в книге «Искусство компьютерного программирования», глава 7.1.4, ZDD для представления простых путей. См. также упражнение 227 (и другие).   -  person harold    schedule 12.05.2013
comment
Эвристическая версия Angluin–Valiant дает довольно хорошие результаты.   -  person David Eisenstat    schedule 12.05.2013

Ответы (2)


arrow_upward
0
arrow_downward

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

Это связано с тем, что гамильтонов путь является NP- завершить на общих графиках сетки. Сокращение тогда такое же: быстрый решатель длиннейшего пути немедленно даст вам быстрый гамильтоновский решатель пути, просто сравнивая длину самого длинного пути между каждой парой узлов с n-1.

person BlueRaja - Danny Pflughoeft    schedule 12.05.2013
comment
Является ли гамильтонов путь в квадратной сетке также NP-трудным? Если нет, то как я могу найти такой путь? - person Paul Manta; 12.05.2013
comment
@PaulManta Графы с прямоугольной сеткой имеют HP/HC, если хотя бы одна из сторон имеет четную длину (см., например, математический мир). Если вы пронумеруете узлы так же, как и ячейки матрицы, где n — количество строк, а m — количество столбцов, начните путь с (1,1), спуститесь к (n,1), перейдите к ( n,2), идите вверх к (2,2), затем к (2,3), снова вниз, вправо, вверх и т. д., пока не дойдете до (2,m). Затем перейдите к (1,m) и вернитесь к (1,1). Точно так же, как если бы вы играли в Змею, если это поможет визуализировать ее. - person G. Bach; 12.05.2013
comment
@PaulManta Для графиков с прямоугольной сеткой этот подход даже даст вам HP независимо от того, являются ли длина или ширина прямоугольника четными. Проблема NP-полноты HP для общих сеточных графов состоит в том, что они не обязательно должны быть прямоугольными; например, любой граф обхода (с использованием BFS/DFS/некоторого другого алгоритма обхода) любого графа сетки сам по себе будет графом сетки, поскольку он является подграфом сетки, индуцированным узлами, но в общем случае он не будет прямоугольным (он также вообще не было бы ХП, но тут не в этом дело). - person G. Bach; 12.05.2013
comment
Небольшая поправка: если вам нужен HP независимо от того, четны ли длины сторон прямоугольного графа сетки, идите до конца, не останавливайтесь на (2,k). - person G. Bach; 12.05.2013
comment
@Paul: На случай, если вы запутались: Г. Бах со мной не согласен. Вы заявили в комментариях, что у вас есть препятствия (иначе произвольные узлы могут быть удалены), что является более общей версией проблемы Г. Баха с NP-полным гамильтоновым путем для непрямоугольных сетчатых графов. (Кроме того, он сделал небольшую ошибку: правило четной длины применимо только к гамильтоновым схемам. Все полные прямоугольные сетки-графы (без препятствий) имеют гамильтонов путь) . - person BlueRaja - Danny Pflughoeft; 12.05.2013
comment
@ BlueRaja-DannyPflughoeft Я упоминал, что прямоугольные графы имеют HP независимо от того, имеет ли хотя бы одна сторона четную длину. Это следствие остается в силе для обычных графов с прямоугольной сеткой; в худшем случае это было плохо сформулировано. - person G. Bach; 13.05.2013

arrow_upward
0
arrow_downward

Вот алгоритм линейного времени для двумерной сетки: http://www.sciencedirect.com/science/article/pii/S0166218X11003088

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

person usamec    schedule 12.05.2013
comment
В комментариях он заявил, что есть препятствия, поэтому это не полный грид-граф, а только частичный. Алгоритм линейного времени (который уже упоминался несколькими людьми в комментариях) здесь не применяется. - person BlueRaja - Danny Pflughoeft; 13.05.2013