#algorithm #graph
#алгоритм #График
Вопрос:
Предположим, я начинаю с некоторой вершины (m, n) и хочу достичь вершины (i, j), и на графике есть допустимые пути (значение 1) и недопустимые (значение 0). Я хочу найти уникальное количество путей к (i, j).
Моя текущая идея имеет следующий псевдокод:
-
Отметьте текущий узел из начальной точки как посещаемый, используя переменную-заполнитель, сохраните исходное состояние.
-
DFS в соседний узел, где DFS обрабатывает выходящие за границы и недопустимые пути. Если DFS входит в узел, посещаемый (не посещенный) в данный момент, остановите DFS, поскольку есть цикл.
-
Если DFS находит (i, j), увеличьте возвращаемое значение.
-
После DFS восстановите исходное состояние ячейки.
Тестирование на нескольких тестовых примерах, это работает, но я не уверен, что это лучшее решение, поскольку сложности потенциально очень велики. Я не очень уверен, что это правильная сложность:
-
Время: O (M N) время для каждого DFS, и потенциально выполняет DFS O (MN) время, поэтому O(MN * (M N)) время.
-
4 вызова на ячейку DFS, так что O(4 ^ (MN)) пространство?
Сложность выглядит слишком большой, чтобы быть жизнеспособной. Есть ли лучший алгоритм и правильно ли написана сложность?