我的代码可以归类为深度优先搜索吗？

Question

我在阅读了有关 DFS 的内容后为 DFS 编写了代码，但并未真正看到代码。我这样做是为了挑战自己（我一直相信要学习新事物，您必须首先挑战自己）。事情是在我编写代码之后，我将我的实现与我读过的书中的实现进行了比较（算法设计和分析简介 - A. Levitin），它是完全不同的。所以现在我想知道它是否按预期工作......它仍然是 DFS 吗？

我做了解决迷宫的实现。我将运行打压我的代码，并将代码上传到此处（有些人讨厌阅读其他人的代码，而另一些人则讨厌。）

算法（我理解和做的）：

将迷宫变成 graph/map
将起始位置设置为当前节点并运行循环其中...
我选择一个相邻的节点作为下一个当前节点并这样做，直到我偶然发现了死胡同。此外，我将通过的每个节点添加到充当我的堆栈的列表中。
一旦进入死胡同，我就会不断从堆栈中弹出项目，每次弹出时，我都会检查它是否有未访问过的相邻节点。
一旦我找到一个未访问的相邻节点，我们就从第 3 步开始继续整个过程。
我们这样做直到当前节点是结束位置。
然后我就通过堆栈回溯我的方式。

这是我的代码：

# Depth First Search implementation for maze...

# from random import choice
from copy import deepcopy
import maze_builderV2 as mb

order = 10
space = ['X']+['_' for x in range(order)]+['X']
maze = [deepcopy(space) for x in range(order)]
maze.append(['X' for x in range(order+2)])
maze.insert(0, ['X' for x in range(order+2)])

finalpos = (order, order)

pos = (1, 1)

maze[pos[0]][pos[1]] = 'S'  # Initializing a start position
maze[finalpos[0]][finalpos[1]] = 'O'  # Initializing a end position

mb.mazebuilder(maze=maze)


def spit():
    for x in maze:
        print(x)

spit()
print()

mazemap = {}

def scan():  # Converts raw map/maze into a suitable datastructure.
    for x in range(1, order+1):
        for y in range(1, order+1):
            mazemap[(x, y)] = []
            t = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
            for z in t:
                if maze[z[0]][z[1]] == 'X':
                    pass
                else:
                    mazemap[(x, y)].append(z) 

scan()

path = [pos] # stack
impossible = False

while path[-1] != finalpos:
    curpos = path[-1]
    i = 0
    while i < len(mazemap[curpos]):
        if mazemap[curpos][i] in path:
            del mazemap[curpos][i]
        else:
            i += 1
    nextpos = None
    if mazemap[curpos] == []:
        while nextpos == None:
            try:
                wrongpos = path.pop(-1)
                if mazemap[wrongpos] == []:
                    pass
                else:
                    path.append(wrongpos)
                    # nextpos = choice(mazemap[wrongpos])
                    nextpos = mazemap[wrongpos][-1]
                    mazemap[wrongpos].remove(nextpos)
            except IndexError:
                impossible = True
                break
    else:
        # nextpos = choice(mazemap[curpos])
        nextpos = mazemap[curpos][-1]
    if impossible:
        break
    path.append(nextpos)

if not impossible:
    for x in path:
            if x == pos or x == finalpos:
                pass
            else:
                maze[x[0]][x[1]] = 'W'
else:
    print("This maze not solvable, Blyat!")
    print()

spit()

一如既往，非常感谢您的建议！

Answer 1

你的算法在我看来是 DFS。 DFS 意味着尽可能深入地探索路径，只有在没有解决方案时才回溯到前一个节点，并且您的算法通过从堆栈中弹出节点以类似的方式工作。您只需使用自己的堆栈来模拟递归堆栈，因此它看起来与标准解决方案完全不同。

本质上，所有的递归算法都可以使用栈和循环来模拟。但大多数时候这样做会使算法的可读性大大降低。要解决一个难题，我认为通常的做法是先想出递归的解决方案。确保递归解决方案没有错误后，如果您非常关心效率，则开始使用堆栈实现迭代版本。

其他建议：

if mazemap[curpos][i] in path: 是一个 O(n) 操作，因为路径是一个普通列表。考虑使用单独的哈希集来存储访问过的节点，并使用该集来检查重复而不是使其成为 O(1)。

我的代码可以归类为深度优先搜索吗？

Can my code be classified as a depth first search?

python

algorithm

depth-first-search