Можно ли классифицировать мой код как поиск в глубину?

Question

Я написал код для DFS после прочтения о том, что это такое, но на самом деле не видел код. Я сделал это, чтобы бросить вызов себе (я всегда считал, что, чтобы узнать что-то новое, вы всегда должны сначала бросить вызов себе). Дело в том, что после того, как я написал свой код, я сравнил свою реализацию с той, что была в книге, в которой я ее читал («Введение в разработку и анализ алгоритмов» - А. Левитин), и она совершенно другая. Так что теперь мне интересно, это работает как задумано ... это все еще DFS?

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

Алгоритм (что я понял и сделал):

1. Преобразование лабиринта в график / карту
2. Установка начальной позиции в качестве текущего узла и запуск l oop, в котором ...
3. Я выбираю один из соседних узлов в качестве следующего текущего узла и делай это, пока я не наткнусь на тупик. Также я добавляю каждый узел, через который я прохожу, в список, который действует как мой стек.
4. Как только я захожу в тупик, я продолжаю выталкивать элементы из стека, и каждый раз, когда я вырываюсь, я проверяю, есть ли у него смежные узлы, которые не были посещены.
5. Как только я нашел не посещенный соседний узел, мы продолжаем весь процесс с шага 3.
6. Мы делаем это до тех пор, пока текущий узел не станет конечной позицией.
7. Тогда я просто возвращаюсь назад через стек.

Вот мой код:

# 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 означает изучение пути как можно глубже, возврат к предыдущему узлу только в том случае, если нет решения, и ваш алгоритм работает аналогичным образом, выталкивая узлы из стека. Вы просто имитируете c стек рекурсии, используя свой собственный стек, так что он выглядит совсем не так, как в стандартном решении.

По сути, все рекурсивные алгоритмы могут быть смоделированы с использованием стека и l oop. Но в большинстве случаев это сделает алгоритм менее читабельным. Чтобы решить сложную проблему, я думаю, что обычный способ сделать это - сначала найти рекурсивное решение. Убедившись, что рекурсивное решение не содержит ошибок, приступайте к реализации итеративной версии с использованием стека, если вам небезразлична эффективность.

Другое предложение:

• if mazemap [curpos] [i] в ​​path: является операцией O (n), поскольку path является обычным списком. Рассмотрите возможность использования отдельного набора ha sh для хранения посещенных узлов и используйте этот набор для проверки повторения, вместо этого сделайте его O (1).