python - 我如何将八个方向效果添加到我的 A 星算法而不是 4 个运动？

Question

我正在研究 A-star 算法，我已经实现了我的代码以仅在 四个方向 上移动，如下所示，使用 fixed heuristic:

[11, 11, 0, 4, 5]
############## Search is success

[0, -1, -1, -1, -1, -1]
[1, -1, -1, -1, -1, -1]
[2, -1, -1, -1, -1, -1]
[3, -1, 8, 9, 10, 11]
[4, 5, 6, 7, -1, 12]

['V', ' ', ' ', ' ', ' ', ' ']
['V', ' ', ' ', ' ', ' ', ' ']
['V', ' ', ' ', ' ', ' ', ' ']
['V', ' ', ' ', '>', '>', 'V']
['>', '>', '>', '^', ' ', '*']

我尝试使用 Euclid distance 来计算 heuristic，如下所示:

h = math.sqrt((x - goal[0])**2 + (y - goal[1])**2)

我添加了 8 Action ，如下所示，带有 delta 和 delta name:

delta =      [[1, 0, 1],
              [0, 1, 1],
              [-1, 0, 1],
              [0, -1, 1],
              [-1, -1, math.sqrt(2)],
              [-1, 1, math.sqrt(2)],
              [1, -1, math.sqrt(2)],
              [1, 1, math.sqrt(2)]]

delta_name = ['^','\','/','<','V','>','\','/']

它给了我一些错误，如下所示:

1-

File "<ipython-input-24-224819b0ad4c>", line 55
    delta_name = ['^','\','/','<','V','>','\','/']
                                   ^
SyntaxError: invalid syntax

2-

IndexError                                Traceback (most recent call last)
<ipython-input-25-bc33334a69ba> in <module>
    174 
    175 
--> 176 search()

<ipython-input-25-bc33334a69ba> in search()
    140         x2=x-delta[action[x][y]][0]
    141         y2=y-delta[action[x][y]][1]
--> 142         policy[x2][y2]= delta_name[action[x][y]]
    143         x=x2
    144         y=y2

IndexError: list index out of range

请问我该如何修复它们？你能找到我的三角洲的运动吗，哪个是向上的，向右的，向下的……等等？

这是我的代码:

import random
Import math
grid = [[0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0]]
heuristic = [[9, 8, 7, 6, 5, 4],
             [8, 7, 6, 5, 4, 3],
             [7, 6, 5, 4, 3, 2],
             [6, 5, 4, 3, 2, 1],
             [5, 4, 3, 2, 1, 0]]
init = [0,0]                           
goal = [len(grid)-1,len(grid[0])-1]
#Below the four potential actions to the single field
'''
delta = [[-1 , 0],   #up 
         [ 0 ,-1],   #left
         [ 1 , 0],   #down
         [ 0 , 1]]   #right
'''

delta =      [[1, 0, 1],
              [0, 1, 1],
              [-1, 0, 1],
              [0, -1, 1],
              [-1, -1, math.sqrt(2)],
              [-1, 1, math.sqrt(2)],
              [1, -1, math.sqrt(2)],
              [1, 1, math.sqrt(2)]]


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

delta_name = ['^','\','/','<','V','>','\','/']

cost = 1
def search():
    #open list elements are of the type [g,x,y]
    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
    expand=[[-1 for row in range(len(grid[0]))] for col in range(len(grid))]

    # we assigned the cordinates and g value
    x = init[0]
    y = init[1]
    g = 0
    #h = heuristic[x][y]
    h = math.sqrt((x - goal[0])**2 + (y - goal[1])**2)
    f = g + h 

    #our open list will contain our initial value
    open = [[f, g, h, x, y]]
    found  = False   #flag that is set when search complete
    resign = False   #Flag set if we can't find expand
    count = 0

    #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')
            print()
        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[3]
            y = next[4]
            g = next[1]

            expand[x][y] = count
            count+=1

            #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')
                print()

            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 closed[x2][y2] == 0 and grid[x2][y2] == 0:
                            g2 = g + cost            
                            #h2 = heuristic[x2][y2]
                            h2 = math.sqrt((x2 - goal[0])**2 + (y2 - goal[1])**2)
                            f2 = g2 + h2 

                            open.append([f2,g2,h2,x2,y2])   
                            #print('append list item')
                            #print([g2,x2,y2])
                            #Then we check them to never expand again
                            closed[x2][y2] = 1
                            action[x2][y2] = i

    for i in range(len(expand)):
        print(expand[i])
    print()

    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()

Answer 1

使用语法高亮

在行delta_name = ['^','\','/','<','V','>','\','/']你没有“字符”列表，因为在第二个字符串中 \字符转义结束引号，因此它不会在您想要的地方关闭。大多数编辑器中的语法突出显示都会向您展示这一点。

如果你想要一个包含单个字符的字符串 \那么你必须把它写成 '\\' .

有关详细信息，请参阅 https://docs.python.org/3/reference/lexical_analysis.html#string-and-bytes-literals - “反斜杠 () 字符用于转义具有特殊含义的字符，例如换行符、反斜杠本身 或引号字符。”