| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Гамильтонов путь двумерной целочисленной решетки |
| Автор: MoDErahN 14.10.2010, 18:24 |
| Облазил пол интернета, так и не нашел решения. Представьте себе листик в клеточку, вот у меня есть поле N*M клеток, мне нужно провести из клетки (X1, Y1) в клетку (X2, Y2) линию так, чтобы она проходила через все остальные клетки поля (кроме, быть может, одной), ходить можно вверх/вправо/вниз/влево, ну и, естественно, за границы выходить нельзя. Эта задача сводится к нахождению Гамильтонова пути на графе, где вершины = клетки, ну а дуги, соответственно, соединяют соседние клетки. Фактически такой граф - это двумерная целочисленная решетка. В общем случае нахождение Гамильтонова пути на графе это NP полная задача. Но у меня очень частный случай графа - двумерная решетка, и я почти уверен, что для такого случая уже разработаны алгоритмы нахождения Гамильтонова пути (например для тех же игр, где игровое поле это лабиринт без ответвлений от основного пути). Уже не одну неделю убил в поисках решения. Может здесь кто знает, как подступиться к этой задачке? PS: Алгоритм должен позволять находить произвольный путь, а не какое-то частное решение (ну или хотя бы возможность доработать алгоритм в этом направлении), т.е. чтобы за счет генератора случайных чисел можно было бы при каждом запуске этого алгоритма получать разные пути, в идеале вообще произвольный путь из всего множества Гамильтоновых путей для заданного размера решетки и точек начала/конца. PSPS: Если кто знает решение не для нахождения Гамильтонова пути, а хотя бы для нахождения Гамильтонова цикла - пишите, тоже буду премного благодарен. |
| Автор: Lipetsk 15.10.2010, 08:34 |
| здесь совсем недавно было, посмотрите http://forum.vingrad.ru/forum/topic-311321.html |
| Автор: MoDErahN 15.10.2010, 15:26 |
| Спасибо, сейчас консультируюсь у автора конкурса. Вот задам заодно вопрос и здесь. В http://habrahabr.ru/blogs/algorithm/105705/ говорится о построении циклов при помощи конечного автомата, но метод его построения не изложен. Быть может вы подскажете, где можно прочесть именно метод построения данного автомата для циклов, а еще лучше, для Гамильтоновых путей. |