項(xiàng)目編號：B377

文件大?。?M

源碼說明：帶中文注釋

開發(fā)環(huán)境：Python

簡要概述：

此代碼生成指定大小的隨機(jī)迷宮，給定開始和目標(biāo)節(jié)點(diǎn)，使用*算法求解迷宮以生成次優(yōu)路徑。編寫該代碼是為了幫助理解如何使用python數(shù)據(jù)結(jié)構(gòu)來減少執(zhí)行時間，從而解決流行的路徑規(guī)劃算法。

-網(wǎng)格大小-77x77

-開始節(jié)點(diǎn)-2,2

-結(jié)束節(jié)點(diǎn)-28,68

-網(wǎng)格大小-125x125

-開始節(jié)點(diǎn)-2,2

-結(jié)束節(jié)點(diǎn)-58,110

A*類似于Dijkstra的算法，因?yàn)樗梢杂脕碚业阶疃搪窂健*類似于貪婪的最佳優(yōu)先搜索，因?yàn)樗梢允褂脝l(fā)式來引導(dǎo)自己。

它成功的秘訣在于它結(jié)合了Dijkstra算法使用的信息片段（偏愛接近起點(diǎn)的頂點(diǎn)）和貪婪的Best First搜索使用的信息片段（偏愛接近目標(biāo)的頂點(diǎn)）。在討論A*時使用的標(biāo)準(zhǔn)術(shù)語中，g（n）表示從起點(diǎn)到任意頂點(diǎn)n的路徑的精確成本，h（n）表示從頂點(diǎn)n到目標(biāo)的啟發(fā)式估計(jì)成本。在上圖中，黃色（h）表示遠(yuǎn)離目標(biāo)的頂點(diǎn)，而teal（g）表示遠(yuǎn)離起點(diǎn)的頂點(diǎn)。A*在從起點(diǎn)移動到目標(biāo)時平衡兩者。每次通過主循環(huán)，它都檢查具有最低f（n）=g（n）+h（n）的頂點(diǎn)n。

先決條件

-Python 3.x

-Numpy

-sympy

-matplotlib

如何使用

運(yùn)行Maze_Solver.py

在執(zhí)行時，接口要求您輸入設(shè)計(jì)所需迷宮的信息。迷宮創(chuàng)建是隨機(jī)的，但稀疏度和大小可以由用戶定義。

開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)需要輸入，并且必須是偶數(shù)。

斷言是為錯誤處理而設(shè)置的。

目錄│文件列表:

 └ 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