Skip to content

skyfaker/search_algorithm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

15 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

search_algorithm

Different search algoruthm to find path in a maze

目前有A*算法、BFS、DFS、Dijkstra和GBFS(贪婪最佳优先)。

文件

random_map.py包含了节点类和地图类,有随机地图与固定地图2种;

search_algorithm.py包含了AStar类,即A*算法;BFS类,即BFS算法……

main.py为入口文件。

使用

使用方法:运行main.py即可。

使用matplotlib的交互模式,实现搜索节点时的map动态刷新功能。

最终保存寻找到的路径图片到img文件夹。

样例

A*

代价函数 $ f(n) = g(n)+h(n) $ ,其中g(n) = x_dis + y_dis + round(float((math.sqrt(2) - 2)*min(x_dis, y_dis)), 3)即对角距离,使用对角距离是为了控制路线靠近中心线,h(n) = x_dis + y_dis 即曼哈顿距离。

A*示例

蓝色+绿色为经过的点,绿色为回溯时寻找的路径。

BFS

BFS示例

DFS

DFS示例

Dijkstra

Dijkstra示例

由于格子之间的路径是一致的,所以看起来会和BFS一样。

GBFS

GBFS示例

TODO:

  • BFS
  • DFS
  • Dijkstra
  • GBFS

About

different search algoruthm to find path in a maze, A*、BFS、DFS、Dijkstra and GBFS

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages