Python: Мой алгоритм поиска с ограничением по глубине не будет работать

Question

новичок в Python.

Я реализовал алгоритм поиска с ограниченной глубиной, чтобы найти маршрут от S до G. Где S - начальная позиция, а G - пункт назначения.

R обозначает дорогу, а X обозначает препятствие, через которое мы не можем пройти.
ADJ - это словарь, содержащий соседние пути из заданного местоположения.

Таким образом, для S соседями являются 2 и 6. 2 и 6 представляют соседние дороги. Я не включил X, поскольку X является препятствием. Однако он не может двигаться по диагонали, если одно из направлений, составляющих диагональ, содержит X.

Проблема в том, что когда я запускаю приведенный ниже код, мой алгоритм не находит маршрут и застревает навсегда, пока он не превысит предел глубины.
Существует маршрут от S до G, но мой алгоритм его не находит.
Как мне решить эту ошибку? Спасибо
Вот мой код:

ADJ = {}
""""
SRRXG
RXRXR
RRRXR
XRXRR
RRRRX
"""
ADJ['S'] = ['2', '6']
ADJ['2'] = ['S', '3']
ADJ['3'] = ['2','8']
ADJ['G'] = ['10']
ADJ['6'] = ['S', '11']
ADJ['8'] = ['3', '13']
ADJ['10'] = ['G', '15']
ADJ['11'] = ['6', '12']
ADJ['12'] = ['11', '13', '17']
ADJ['13'] = ['8', '12']
ADJ['15'] = ['10', '20']
ADJ['17'] = ['12','22']
ADJ['19'] = ['20', '24']
ADJ['20'] = ['15','19']
ADJ['21'] = ['22']
ADJ['22'] = ['17','21','23']
ADJ['23'] = ['22', '24']
ADJ['24'] = ['19','23']
print (ADJ)
def dls(start, goal):
    depth = 0
    limit = 200
    OPEN=[]
    CLOSED=[]
    OPEN.append(start)
    while OPEN != []: # Step 2
        if depth<=limit:
            current = OPEN.pop() 
            if current == goal:
                CLOSED.append(current)
                print("Goal Node Found")
                print(CLOSED)
                return True
            else:
                CLOSED.append(current)
                lst = successors(current)
                for i in lst:
                    OPEN.append(i)
                depth +=1
        else:
            print("Not found within depth limit")
            return False


    return False

def successors(city):
    return ADJ[city]

def test():
    start = 'S'
    goal = 'G'
    print("Starting a dls from " + start)
    print(dls(start, goal))


if __name__ == "__main__":
    test()

Answer 1

Проблема в том, что вы не ведете проверку уже посещенных узлов. Например, вы начинаете с узла «S», а затем переходите к его соседям, вы должны пометить его как посещенный и выполнить проверку при добавлении в список OPEN, чтобы вы не пытались вернуться к нему снова. Если вы этого не сделаете, ваш код застрянет в бесконечном цикле, так как вы будете продолжать переходить между двумя узлами.

Кроме того, в ADJ была некоторая проблема, которую вы создали, особенно в «22». Я попытался внести минимальные изменения в ваш код (сохранив удаленные части в качестве комментариев), хотя есть несколько других мест, где его можно улучшить. Исправленный код:

ADJ = {}
""""
SRRXG
RXRXR
RRRXR
XRXRR
RRRRX
"""
ADJ['S'] = ['2', '6']
ADJ['2'] = ['S', '3']
ADJ['3'] = ['2','8']
ADJ['G'] = ['10']
ADJ['6'] = ['S', '11']
ADJ['8'] = ['3', '13']
ADJ['10'] = ['G', '15']
ADJ['11'] = ['6', '12']
ADJ['12'] = ['11', '13', '17']
ADJ['13'] = ['8', '12']
ADJ['15'] = ['10', '20']
ADJ['17'] = ['12','22']
ADJ['19'] = ['20', '24']
ADJ['20'] = ['15','19']
ADJ['21'] = ['22']
ADJ['22'] = ['17','21','23']
ADJ['23'] = ['22', '24']
ADJ['24'] = ['19','23']
print (ADJ)
# keep track of visited nodes
visited = {str(i) : False for i in range(1,26)}
visited['S'] = False
visited['G'] = False

def dls(start, goal):
    depth = 0
    limit = 200
    OPEN=[]
    CLOSED=[]
    OPEN.append(start)
    visited["S"] = True
    while OPEN != []: # Step 2
        if depth<=limit:
            current = OPEN.pop() 
            # visited[current] = False
            if current == goal:
                # CLOSED.append(current)
                print("Goal Node Found")
                # print(CLOSED)
                return True
            else:
                # CLOSED.append(current)
                lst = successors(current)
                for i in lst:
                    # try to visit a node in future, if not already been to it
                    if(not(visited[i])):
                        OPEN.append(i)
                        visited[i] = True
                depth +=1

        else:
            print("Not found within depth limit")
            return False


    return False

Кроме того, вы можете написать функцию для вычисления ADJ по заданному лабиринту очень легко вместо жесткого кодирования.