搵路
From Wikipedia, the free encyclopedia
- 一幅表示移動空間嘅圖、
- 起點、以及
- 終點,
然後個演算法就需要計出一條由起點去終點嘅路線(output)[2]。
一個典型嘅搵路演算法通常會同另外兩個特定嘅演算法一齊做嘢:一方面,搵路演算法一般唔能夠直接對要探索嘅環境作出運算,而係要靠另外一個演算法 simp
,simp
要以個環境嘅地圖做輸入,將幅地圖抽象化,變成一幅圖論上嘅圖做輸出,等個搵路演算法用呢幅圖做輸入[1];另一方面,因為搵路演算法做嘅只係「搵條路線出嚟」,所以喺搵路演算法行完之後,個程式要將條路線交俾一個教個人工智能移動嘅演算法 follow
,等 follow
教部電腦執行「沿條路線移動」呢個動作[3]。
用嚟做搵路嘅演算法有好多實用價值:例如係喺機械人學上教機械人喺自己周圍嘅空間當中搵出要行嘅路線,以及係喺遊戲製作上教遊戲 AI 控制啲 NPC 喺遊戲空間入面搵出要行嘅路線呀噉,都要用到搵路演算法[4][5]。