A*算法求解迷宫寻路问题实验

作者：AllinToyou | 2024-05-05 21:55:32

踩

a*算法求解迷宫寻路问题实验

任务要求
参考答案
评论

任务描述

本关任务：编写一个使用 A* 搜索算法完成求解迷宫问题最优解的小程序。

编程要求

根据提示，在右侧 vscode 编辑器补充代码，参考寻路过程中向左、向右、向上三个方向的移动方式，完成向下的移动代码的编写，达到通过使用 A* 搜索算法完成求解迷宫寻路问题的最短路径。

编程路径：/data/workspace/myshixun/step1/test.py

测试说明

平台会对你编写的代码进行测试：

测试输入：无；

预期输出：

Best Way:
* * 0 0 0
1 * 1 0 1
0 * * 0 1
0 1 * * *
0 0 0 1 *
Total steps is 8

代码部分

这里的往下走部分可以参考往上走和往右走的逻辑来仿写，毕竟有很多部分都是相同的就是要注意x轴和y轴的区别


import numpy as np
 
 
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.f = 0
 
    def setF(self, f):
        self.f = f
 
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
 
        
    ########## Begin ##########
    # 曼哈顿距离比较  f = g + h，h=1
    def getFunctionValue(self, end):
        dist = abs(self.x - end.x) + abs(self.y - end.y)
        return dist + 1
 
    ########## Eed ##########
 
 
 
class State:
    def __init__(self, state, current_point=Point(0, 0), end_point=Point(0, 0)):
        self.state = state
        self.cP = current_point
        self.eP = end_point
 
    def __eq__(self, other):
        return self.cP == other.cP
 
    def setF(self, f):
        self.f = f
 
    def setCurrentPoint(self, x, y):
        self.cP.x = x
        self.cP.y = y
 
    def getCurPoint(self):
        return self.cP.x, self.cP.y
 
 
# 确定下一步的方法
def nextStep(map, openTable, closeTable, wrongTable):
    subPoints = []
    boarder = len(map.state) - 1
    # 获取当前所在的点
    x, y = map.getCurPoint()
    # 往左走
    if y > 0 and map.state[x][y - 1] == 0:
        p = Point(x, y - 1)
        if p not in closeTable and p not in wrongTable:
            # 添加到可以走的list
            openTable.append(p)
            # new point
            # 获取F函数值
            p.setF(p.getFunctionValue(map.eP))
            subPoints.append(p)
    # 往上走
    if x > 0 and map.state[x - 1][y] == 0:
        p = Point(x - 1, y)
        if p not in closeTable and p not in wrongTable:
            openTable.append(p)
            p.setF(p.getFunctionValue(map.eP))
            subPoints.append(p)
 
    # 任务：完成往下走的代码逻辑
    ########## Begin ##########
    if x < boarder and map.state[x + 1][y] == 0:
            p = Point(x + 1, y)
            if p not in closeTable and p not in wrongTable:
                openTable.append(p)
                p.setF(p.getFunctionValue(map.eP))
                subPoints.append(p)
 
 
    ########## Eed ##########
 
    # 往右走
    if y < boarder and map.state[x][y + 1] == 0:
        p = Point(x, y + 1)
        if p not in closeTable and p not in wrongTable:
            openTable.append(p)
            p.setF(p.getFunctionValue(map.eP))
            subPoints.append(p)
    #   根据F值排序，获取F值最近的
    subPoints.sort(key=compareF)
    if len(subPoints) < 1:
        # 防止走到死路无法回头情况
        wrongTable.append(Point(map.cP.x, map.cP.y))
        closeTable.remove(map.cP)
        next_point = closeTable[-1]
        map.cP.x, map.cP.y = next_point.x, next_point.y
    else:
        next_point = subPoints[0]
        map.cP.x, map.cP.y = next_point.x, next_point.y
        closeTable.append(next_point)
        openTable.remove(next_point)
 
 
# 迭代走下一步
def solve(map, openTable, closeTable, wrongTable):
    # start the loop
    while not map.cP == map.eP:
        nextStep(map, openTable, closeTable, wrongTable)
 
 
def compareF(p):
    return p.f
 
 
# 展示最后结果
def showInfo(map, path):
    for i in range(len(map.state)):
        for j in range(len(map.state)):
            if Point(i, j) in path:
                # 正确路径用‘*’表示
                print('*', end='  ')
            else:
                print(map.state[i, j], end='  ')
        print("\n")
    return
 
 
if __name__ == '__main__':
    # openList
    openTable = []
    # closeList
    closeTable = []
    # 走错路返回用的
    wrongTable = []
    state = np.array([[0, 0, 0, 0, 0], [1, 0, 1, 0, 1], [0, 0, 0, 0, 1], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0]])
    # 起点终点
    start_point = Point(0, 0)
    end_point = Point(4, 4)
    # 最终路径
    path = [start_point]
    Map = State(state, Point(0, 0), end_point)
    solve(Map, openTable, closeTable, wrongTable)
    print('Best Way:')
    path = path + closeTable
    showInfo(Map, path)
    print("Total steps is %d" % (len(path) - 1))

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/541011

A*算法求解迷宫寻路问题实验

任务描述

相关知识

A* 搜索算法简介

A* 算法步骤

A* 算法求解迷宫问题

编程要求

测试说明

代码部分