Найти ВСЕ пути в сетке между 2 узлами

Question

Я пытаюсь найти все пути между 2 узлами в сетке, и путь должен проходить через все узлы от начала до конца.Пример (Start = S, End = E)

0 0 0
0 S 0
0 0 E

Ответ на приведенный выше вопрос - 2 пути: (игнорировать '. 's)

0-0-0
| ....... |
0 S-0
|
0-0-E

0-0-0
| ...... |
0 S 0
| ... | ... |
0-0 E

Я подумал об использовании рекурсии, но отказался от этого из-за высоких издержек при каждом вызове ... и решил использовать итеративный подход с использованием стека.(вроде как повторение, но не ... фиксированные накладные расходы памяти).Решение отлично работает для сеток размером (4x7), но пробовал его на сетке 8x8 ... и оно не закончилось за 4 часа ... что имеет смысл, поскольку общее число возможностей составляет около 3 **62 (приблизительно), так как каждый узел, который не находится на краю, имеет 3 возможных пути обхода ... и, следовательно, это решение терпит неудачу.

Я думал разбить сетку 8x8 на 2, используя вертикальную и горизонтальнуюразделить ... но это привело бы к нахождению путей, не являющихся идеальными.

Есть ли что-то, что я пропускаю ????Можно ли что-то сделать, чтобы сделать это быстрее?Я опубликую решение, которое у меня есть завтра (сделано в C).

Answer 1

Нет, вы ничего не пропустите и ничего не сможете сделать быстрее.

Это проблема самого длинного пути , которая является NP-Hard.

Answer 2

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

Answer 3

Взгляните на проблему кратчайших путей, с которой вам следует начать. Стоит попробовать алгоритм Беллмана-Форда или Дейкстры. Возможно, вы сможете улучшить эффективность этих функций, если ваша сетка имеет некоторые свойства, которые вы можете использовать.