【B377】使用A星算法的Python迷宫解算器

项目编号：B377

文件大小：9M

源码说明：带中文注释

开发环境：Python

简要概述：

此代码生成指定大小的随机迷宫，给定开始和目标节点，使用*算法求解迷宫以生成次优路径。编写该代码是为了帮助理解如何使用python数据结构来减少执行时间，从而解决流行的路径规划算法。

-网格大小-77x77

-开始节点-2,2

-结束节点-28,68

-网格大小-125x125

-开始节点-2,2

-结束节点-58,110

A*类似于Dijkstra的算法，因为它可以用来找到最短路径。A*类似于贪婪的最佳优先搜索，因为它可以使用启发式来引导自己。

它成功的秘诀在于它结合了Dijkstra算法使用的信息片段（偏爱接近起点的顶点）和贪婪的Best First搜索使用的信息片段（偏爱接近目标的顶点）。在讨论A*时使用的标准术语中，g（n）表示从起点到任意顶点n的路径的精确成本，h（n）表示从顶点n到目标的启发式估计成本。在上图中，黄色（h）表示远离目标的顶点，而teal（g）表示远离起点的顶点。A*在从起点移动到目标时平衡两者。每次通过主循环，它都检查具有最低f（n）=g（n）+h（n）的顶点n。

先决条件

-Python 3.x

-Numpy

-sympy

-matplotlib

如何使用

运行Maze_Solver.py

在执行时，接口要求您输入设计所需迷宫的信息。迷宫创建是随机的，但稀疏度和大小可以由用户定义。

开始节点和结束节点需要输入，并且必须是偶数。

断言是为错误处理而设置的。

目录│文件列表:

 └ A_star

    │ A_star.py

    │ Image_Demo1.gif

    │ Image_Demo2.gif

    │ Maze.py

    │ Maze_Solver.py

    ├ create_gif

    │  │ astar_100.png

    │  │ astar_150.png

    │  │ astar_200.png

    │  │ astar_250.png

    │  │ astar_300.png

    │  │ astar_350.png

    │  │ astar_400.png

    │  │ astar_450.png

    │  │ astar_50.png

    │  │ astar_500.png

    │  │ astar_550.png

    │  └ astar_600.png

    └ Data

       │ Image_Demo1.gif

       └ Image_Demo2.gif