2

我试图找到从给定
initial_state（形式为 list[row,col,orientation]）到给定目标（形式为 list[row,col]）的汽车的最佳路径。

汽车可以沿方向（上、左、下、右）自由前进。

它可以执行 3 个动作，分别是：
右转前进（2）、前进（1）、左转前进（20）
注意：括号中的数字是执行相应动作所涉及的成本

转向发生在同一个单元格中。
由 0 和 1 组成的2D 列表（称为grid）作为输入（2D 非循环世界）。
0 --- 可导航单元格
1 --- 不可导航单元格

任务是从多个可能的路径中找到一条路径（成本最低）。

这是我的代码。

forward = [[-1,0],[0,-1],[1,0],[0,1]]
forward_name = ['up','left','down','right']
action = [-1,0,1]  ## turnRight, noTurn, turnLeft
action_name = ['R','#','L']
grid = [[1,1,1,0,0,0],
        [1,1,1,0,1,0],
        [0,0,0,0,0,0],
        [1,1,1,0,1,1],
        [1,1,1,0,1,1]]
init = [4,3,0]  ## for init[2]-- 0-up, 1-left, 2-down, 3-right 
goal = [2,0]
cost = [2,1,20]  ## turnRight, noTurn, turnLeft

def optimum_policy2D(grid, init, goal, cost):
    value = [[999*i for i in row] for row in grid]
    #print(value)
    r,c,orientation = init
    Routes = []   ##list of routes
    Routes.append([0,[init[:2]],orientation]) 
                   ## [cost,list of cell in the route,orientation]

    while [r,c]!=goal:
        presentRoute = Routes[0]
        for i in range(len(action)):
            dr, dc = forward[(presentRoute[2]+action[i])%4]
            if r+dr in range(len(grid)) and c+dc in range(len(grid[0])) and 
            value[r+dr][c+dc]!=999:
                thisRoute = presentRoute[:]
                thisRoute[1].append([r+dr,c+dc])
                thisRoute[0] += cost[i]
                thisRoute[2] = (thisRoute[2]+action[i])%4
                Routes.append(thisRoute[:])
        Routes = Routes[1:]
        Routes.sort()
        r,c = Routes[0][1][-1]
    print(Routes[0])

optimum_policy2D(grid, init, goal, cost)

我在不可导航的单元格处创建了一个具有任意高值 999（高于所涉及的最大成本）的 2D 列表值。

接下来我创建一个空列表（称为 Routes），它将存储不同的路由。每条路线将采用以下形式 - [成本、路线中的单元格列表、汽车的最终方向]。在进入 while-Loop 之前，Route 被初始化为初始状态（因为它将成为任何 Route 的一部分）。

一个 for 循环检查有效邻居（邻居的有效性 - 应该在网格中，应该是可导航的）。

对于一个有效的邻居——
在 thisRoute 中创建 presentRoute 的副本。
将新的单元格坐标附加到路线中的单元格列表中。
根据执行的操作更新成本。
根据动作更新最终方向。
*最后将此新路由附加到 Routes。
（对于每个有效的邻居，一个新的路由被附加到 Routes 中）

Routes[0] 现已删除。在对路线进行排序时，列表中的第一条路线将是成本最低的路线。变量 'r' 和 'c' 用 min-cost Route 的最后一个单元格更新。

一旦 [r,c] 等于目标，我们就找到了成本最低的路线。

输出与我的信念不同。我查找此代码中的错误。

4

0 回答 0