Python:我的非限制搜索算法赢了

Question

Python新手。在

我实现了一个深度受限的搜索算法来查找从S到{}的路由。其中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”开始，然后转到它的邻居，您应该将其标记为已访问，并在附加到打开列表时进行检查，这样就不会再次尝试访问它。如果您不这样做，您的代码将陷入无限循环，因为您将继续在两个节点之间跳跃。在

此外，在你创造的形容词中也有一些问题，特别是在'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，而不是硬编码。在