python - 第一个搜索程序 - 用于机器人路径打印的人工智能

Question

我是 Python 编程的新手，我正在尽力完全理解这段代码。在这里，我们正在打印第一个搜索程序的路径 - 机器人算法的人工智能。我知道这些行的基本原理一般是如何工作的，但是它们在这段代码中是如何工作的。请问我可以澄清一下下面的这段代码吗？

这是下面的代码：

policy=[[' ' for row in range(len(grid[0]))] for col in range(len(grid))]
    x=goal[0]
    y=goal[1]
    policy[x][y]='*'
    while x !=init[0] or y !=init[1]:
        x2=x-delta[action[x][y]][0]
        y2=y-delta[action[x][y]][1]
        policy[x2][y2]= delta_name[action[x][y]]
        x=x2
        y=y2
    for i in range(len(policy)):
        print(policy[i])

这是代码：

#grid format
# 0 = navigable space
# 1 = occupied space

grid = [[0,0,1,0,0,0],
        [0,0,1,0,0,0],
        [0,0,0,0,1,0],
        [0,0,1,1,1,0],
        [0,0,0,0,1,0]]

init = [0,0]                            #Start location is (0,0) which we put it in open list.
goal = [len(grid)-1,len(grid[0])-1]     #Our goal in (4,5) and here are the coordinates of the cell.


#Below the four potential actions to the single field

delta = [[-1 , 0],   #up by subtracting one from the first dimention, I mean the demension of (0,0)
         [ 0 ,-1],   #left
         [ 1 , 0],   #down
         [ 0 , 1]]   #right

delta_name = ['^','<','V','>']  #The name of above actions

cost = 1   #Each step costs you one

def search():
    #open list elements are of the type [g,x,y] 

    #To check cells once they expanded and don't expand them again. We defined an array called closed 
    #and its size as our grid. It has two values 0 & 1. 0 means open and 1 means closed.
    closed = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
    action=[[-1 for row in range(len(grid[0]))] for col in range(len(grid))]
    #We initialize the starting location as checked
    closed[init[0]][init[1]] = 1

    # we assigned the cordinates and g value
    x = init[0]
    y = init[1]
    g = 0

    #our open list will contain our initial value
    open = [[g, x, y]]


    found  = False   #flag that is set when search complete
    resign = False   #Flag set if we can't find expand

    #print('initial open list:')
    #for i in range(len(open)):
            #print('  ', open[i])
    #print('----')


    while found is False and resign is False:

        #Check if we still have elements in the open list
        if len(open) == 0:    #If our open list is empty, there is nothing to expand.
            resign = True
            print('Fail')
            print('############# Search terminated without success')

        else: 
            #if there is still elements on our list
            #remove node from list
            open.sort()             #sort elements in an increasing order from the smallest g value up
            open.reverse()          #reverse the list
            next = open.pop()       #remove the element with the smallest g value from the list
            #print('list item')
            #print('next')

            #Then we assign the three values to x,y and g. Which is our expantion.
            x = next[1]
            y = next[2]
            g = next[0]

            #Check if we are done
            if x == goal[0] and y == goal[1]:
                found = True
                print(next) #The three elements above this "if".
                print('############## Search is success')

            else:
                #expand winning element and add to new open list
                for i in range(len(delta)):       #going through all our actions the four actions
                    #We apply the actions to x and y with additional delta to construct x2 and y2
                    x2 = x + delta[i][0]
                    y2 = y + delta[i][1]

                    #if x2 and y2 falls into the grid
                    if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 <= len(grid[0])-1:
                        #if x2 and y2 not checked yet and there is not obstacles
                        if closed[x2][y2] == 0 and grid[x2][y2] == 0:
                            g2 = g + cost             #we increment the cose
                            open.append([g2,x2,y2])   #we add them to our open list
                            #print('append list item')
                            #print([g2,x2,y2])
                            #Then we check them to never expand again
                            closed[x2][y2] = 1
                            action[x2][y2]=i

    policy=[[' ' for row in range(len(grid[0]))] for col in range(len(grid))]
    x=goal[0]
    y=goal[1]
    policy[x][y]='*'
    while x !=init[0] or y !=init[1]:
        x2=x-delta[action[x][y]][0]
        y2=y-delta[action[x][y]][1]
        policy[x2][y2]= delta_name[action[x][y]]
        x=x2
        y=y2
    for i in range(len(policy)):
        print(policy[i])


search()

标签： pythonalgorithmdepth-first-search