狀態(tài)空間搜索策略上

關(guān)于狀態(tài)空間搜索策略上第1頁，課件共54頁，創(chuàng)作于2023年2月問題求解問題求解是人工智能的核心問題之一問題求解的目的機器自動找出某問題的正確解決策略更進一步，能夠舉一反三，具有解決同類問題的能力是從人工智能初期的智力難題、棋類游戲等問題的研究中開始形成和發(fā)展起來的一大類技術(shù)，搜索技術(shù)是問題求解的主要手段之一問題表示解的搜索第2頁，課件共54頁，創(chuàng)作于2023年2月示例——八數(shù)碼難題在3×3的棋盤，擺有八個棋子，每個棋子上標(biāo)有1至8的某一數(shù)字。棋盤上還有一個空格，與空格相鄰的棋子可以移到空格中。12384567初始狀態(tài)81324567目標(biāo)狀態(tài)如何將棋盤從某一初始狀態(tài)變成最后的目標(biāo)狀態(tài)？第3頁，課件共54頁，創(chuàng)作于2023年2月問題示例4怎樣找到兩點之間的最短路徑呢？第4頁，課件共54頁，創(chuàng)作于2023年2月6.1.2狀態(tài)空間表示法

（1）很多問題的求解過程都可以看作是一個搜索過程。問題及其求解過程可以用狀態(tài)空間表示法來表示。（2）狀態(tài)空間用“狀態(tài)”和“算符”來表示問題。狀態(tài) 狀態(tài)用以描述問題在求解過程中不同時刻的狀態(tài)，一般用一個向量表示：SK=(Sk0,Sk1,…)算符 使問題從一個狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€狀態(tài)的操作稱為算符。在產(chǎn)生式系統(tǒng)中，一條產(chǎn)生式規(guī)則就是一個算符。狀態(tài)空間由所有可能出現(xiàn)的狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間。（3）采用狀態(tài)空間求解問題，可以用下面的一個三元組表示：(S,F,G)其中S是問題初始狀態(tài)的集合；F是算符的集合；G是目標(biāo)狀態(tài)的集合。第5頁，課件共54頁，創(chuàng)作于2023年2月傳教士野人問題（Missionaries&Cannibals，MC問題）

有三個傳教士M和三個野人C過河，只有一條能裝下兩個人的船，在河的一方或者船上，如果野人的人數(shù)大于傳教士的人數(shù)，那么傳教士就會有危險，你能不能提出一種安全的渡河方法呢？第6頁，課件共54頁，創(chuàng)作于2023年2月狀態(tài)：問題在某一時刻所處的“位置”，“情況”等根據(jù)問題所關(guān)心的因素，一般用向量形式表示，每一位表示一個因素0：右岸1：左岸初始狀態(tài)：(0,0,0)目標(biāo)狀態(tài)：(3,3,1)狀態(tài)可有多種表示方法：(左岸傳教士數(shù),右岸傳教士數(shù),左岸野人數(shù),右岸野人數(shù),船的位置)或(左岸傳教士數(shù),左岸野人數(shù),船的位置)第7頁，課件共54頁，創(chuàng)作于2023年2月算子（算符，操作符）——使?fàn)顟B(tài)發(fā)生改變的操作MC問題中的算子將傳教士或野人運到河對岸Move-1m1c-lr：將一個傳教士(m)一個野人(c)從左岸(l)運到右岸(r)所有可能操作Move-1m1c-lrMove-1m1c-rlMove-2c-lrMove-2c-rl Move-2m-lr Move-2m-rlMove-1c-lr Move-1c-rl Move-1m-lrMove-1m-rl

第8頁，課件共54頁，創(chuàng)作于2023年2月傳教士野人問題狀態(tài)空間圖MC第9頁，課件共54頁，創(chuàng)作于2023年2月6.2狀態(tài)空間的搜索策略求解過程轉(zhuǎn)化為在狀態(tài)空間圖中搜索一條從初始節(jié)點到目標(biāo)節(jié)點的路徑問題第10頁，課件共54頁，創(chuàng)作于2023年2月

必須記住哪些點走過了

必須記住下一步還可以走哪些點

必須記住從目標(biāo)返回的路徑OPEN表(記錄還沒有擴展的點)CLOSED表(記錄已經(jīng)擴展的點)每個狀態(tài)的節(jié)點結(jié)構(gòu)中必須有指向父節(jié)點的指針6.2.1狀態(tài)空間的一般搜索過程第11頁，課件共54頁，創(chuàng)作于2023年2月OPEN表和CLOSE表OPEN表用于存放剛生成的節(jié)點。對于不同的搜索策略，節(jié)點在OPEN表中的排列順序是不同的。CLOSE表用于存放將要擴展的節(jié)點。對一個節(jié)點的擴展是指：用所有可適用的算符對該節(jié)點進行操作，生成一組子節(jié)點

OPEN表 CLOSE表狀態(tài)節(jié)點父節(jié)點編號狀態(tài)節(jié)點父節(jié)點第12頁，課件共54頁，創(chuàng)作于2023年2月搜索的一般過程把初始節(jié)點S0放入OPEN表，并建立目前只包含S0的圖，記為G；檢查OPEN表是否為空，若為空則問題無解，退出；把OPEN表的第一個節(jié)點取出放入CLOSE表，并計該節(jié)點為n；考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出；擴展節(jié)點n，生成一組子節(jié)點。把其中不是節(jié)點n先輩的那些子節(jié)點記做集合M，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中；對于那些未曾在G中出現(xiàn)過的M成員設(shè)置一個指向父節(jié)點（即節(jié)點n）的指針，并把它們放入OPEN表；（不在OPEN表）按某種搜索策略對OPEN表中的節(jié)點進行排序；轉(zhuǎn)第2步。第13頁，課件共54頁，創(chuàng)作于2023年2月一些說明一個節(jié)點經(jīng)一個算符操作后一般只生成一個子節(jié)點。但適用于一個節(jié)點的算符可能有多個，此時就會生成一組子節(jié)點。這些子節(jié)點中可能有些是當(dāng)前擴展節(jié)點的父節(jié)點、祖父節(jié)點等，此時不能把這些先輩節(jié)點作為當(dāng)前擴展節(jié)點的子節(jié)點。一個新生成的節(jié)點，它可能是第一次被生成的節(jié)點，也可能是先前已作為其它節(jié)點的子節(jié)點被生成過，當(dāng)前又作為另一個節(jié)點的子節(jié)點被再次生成。此時，它究竟應(yīng)選擇哪個節(jié)點作為父節(jié)點？一般由原始節(jié)點到該節(jié)點的代價來決定，處于代價小的路途上的那個節(jié)點就作為該節(jié)點的父節(jié)點。在搜索過程中，一旦某個被考察的節(jié)點是目標(biāo)節(jié)點就得到了一個解。該解是由從初始節(jié)點到該目標(biāo)節(jié)點路徑上的算符構(gòu)成。如果在搜索中一直找不到目標(biāo)節(jié)點，而且OPEN表中不再有可供擴展的節(jié)點，則搜索失敗。通過搜索得到的圖稱為搜索圖，搜索圖是狀態(tài)空間圖的一個子集。由搜索圖中的所有節(jié)點及反向指針?biāo)鶚?gòu)成的集合是一棵樹，稱為搜索樹。根據(jù)搜索樹可給出問題的解。第14頁，課件共54頁，創(chuàng)作于2023年2月盲目搜索不同的搜索策略其搜索的效率是不同的盲目搜索又稱無信息搜索寬度優(yōu)先搜索深度優(yōu)先搜索特點搜索過程中不使用與問題有關(guān)的經(jīng)驗信息采用固定策略對OPEN表排序搜索效率低不適合大空間的實際問題求解第15頁，課件共54頁，創(chuàng)作于2023年2月6.2.2廣度優(yōu)先搜索基本思想： 從初始節(jié)點S0開始，逐層地對節(jié)點進行擴展并考察它是否為目標(biāo)節(jié)點。在第n層的節(jié)點沒有全部擴展并考察之前，不對第n＋1層的節(jié)點進行擴展。OPEN表中節(jié)點總是按進入的先后順序排列，先進入的節(jié)點排在前面，后進入的排在后面。第16頁，課件共54頁，創(chuàng)作于2023年2月廣度優(yōu)先搜索過程把初始節(jié)點S0放入OPEN表。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。第17頁，課件共54頁，創(chuàng)作于2023年2月重排九宮的廣度優(yōu)先搜索

操作符：空格左移、上移、右移、下移第18頁，課件共54頁，創(chuàng)作于2023年2月在上述廣度優(yōu)先算法中需要注意兩個問題：1、對于任意一個可擴展的節(jié)點，總是按照固定的操作符的順序?qū)ζ溥M行擴展（空格左移、上移、右移、下移）。2、在對任一節(jié)點進行擴展的時候，如果所得的某個子節(jié)點（狀態(tài)）前面已經(jīng)出現(xiàn)過，則立即將其放棄，不再重復(fù)畫出（不送入OPEN表）。因此，廣度優(yōu)先搜索的本質(zhì)是，以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照廣度優(yōu)先的原則，生成一棵搜索樹。第19頁，課件共54頁，創(chuàng)作于2023年2月廣度優(yōu)先搜索的特點優(yōu)點： 只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。缺點： 廣度優(yōu)先搜索盲目性較大，當(dāng)目標(biāo)節(jié)點距初始節(jié)點較遠時將會產(chǎn)生許多無用節(jié)點，搜索效率低。第20頁，課件共54頁，創(chuàng)作于2023年2月6.2.3深度優(yōu)先搜索深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別是：廣度優(yōu)先搜索是將節(jié)點n的子節(jié)點放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點n的子節(jié)點放入到OPEN表的首部。第21頁，課件共54頁，創(chuàng)作于2023年2月深度優(yōu)先搜索過程把初始節(jié)點S0放入OPEN表。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。第22頁，課件共54頁，創(chuàng)作于2023年2月重排九宮的深度優(yōu)先搜索第23頁，課件共54頁，創(chuàng)作于2023年2月深度優(yōu)先搜索的特點在深度優(yōu)先搜索中，搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點恰好在此分支上，則可較快地得到解。但是，如果目標(biāo)節(jié)點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。本質(zhì)：以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照深度優(yōu)先的原則，生成一棵搜索樹。第24頁，課件共54頁，創(chuàng)作于2023年2月6.2.4有界深度優(yōu)先搜索基本思想：對深度優(yōu)先搜索引入搜索深度的界限（設(shè)為dm），當(dāng)搜索深度達到了深度界限，而仍未出現(xiàn)目標(biāo)節(jié)點時，就換一個分支進行搜索。搜索過程：把初始節(jié)點S0放入OPEN表中，置S0的深度d(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n的深度d(n)=dm，則轉(zhuǎn)第2步（此時節(jié)點n位于CLOSE表，但并未進行擴展）。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，為每一個子節(jié)點都配置指向父節(jié)點的指針，將每一個子節(jié)點的深度設(shè)置為d(n)+1，然后轉(zhuǎn)第2步。第25頁，課件共54頁，創(chuàng)作于2023年2月如果問題有解，且其路徑長度≤dm，則上述搜索過程一定能求得解。但是，若解的路徑長度>dm,則上述搜索過程就得不到解。這說明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。要恰當(dāng)?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。第26頁，課件共54頁，創(chuàng)作于2023年2月有界深度優(yōu)先搜索的一些改進方法先任意設(shè)定一個較小的數(shù)作為dm，然后進行上述的有界深度優(yōu)先搜索，當(dāng)搜索達到了指定的深度界限dm仍未發(fā)現(xiàn)目標(biāo)節(jié)點，并且CLOSE表中仍有待擴展節(jié)點時，就將這些節(jié)點送回OPEN表，同時增大深度界限dm，繼續(xù)向下搜索。如此不斷地增大dm，只要問題有解，就一定可以找到它。但此時找到的解不一定是最優(yōu)解。為了找到最優(yōu)解，可增設(shè)一個表R，每找到目標(biāo)節(jié)點Sg后，就把它放入到R的前面，并令dm等于該目標(biāo)節(jié)點所對應(yīng)的路徑長度，然后繼續(xù)搜索。由于后求得的解的路徑長度不會超過先求得的解的路徑長度，所以后求得的解一定是最優(yōu)解。第27頁，課件共54頁，創(chuàng)作于2023年2月重排九宮的有界深度優(yōu)先搜索設(shè)深度界限dm＝4第28頁，課件共54頁，創(chuàng)作于2023年2月6.2.5代價樹的廣度優(yōu)先搜索邊上標(biāo)有代價(或費用)的樹稱為代價樹。用g(x)表示從初始節(jié)點S0到節(jié)點x的代價，用c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價，則有：g(x2)=g(x1)+c(x1,x2)基本思想： 每次從OPEN表中選擇節(jié)點往CLOSE表傳送時，總是選擇其中代價最小的節(jié)點。也就是說，OPEN表中的節(jié)點在任一時刻都是按其代價從小到大排序的。代價小的節(jié)點排在前面，代價大的節(jié)點排在后面。如果問題有解，代價樹的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。該算法應(yīng)用的條件:該算法是針對代價樹的算法。為了采用該算法對圖進行搜索，必須先將圖轉(zhuǎn)換為代價樹。轉(zhuǎn)換方法見例6.7。第29頁，課件共54頁，創(chuàng)作于2023年2月代價樹廣度優(yōu)先搜索過程把初始節(jié)點S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，為每一個子節(jié)點都配置指向父節(jié)點的指針，計算各子節(jié)點的代價，并將各子節(jié)點放入OPEN表中。按各節(jié)點的代價對OPEN表中的全部節(jié)點進行排序(按從小到大的順序)，然后轉(zhuǎn)第2步。第30頁，課件共54頁，創(chuàng)作于2023年2月

代價樹示例(例6.7)第31頁，課件共54頁，創(chuàng)作于2023年2月6.2.6代價樹的深度優(yōu)先搜索搜索過程：把初始節(jié)點S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，將其子節(jié)點按代價從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。代價樹的深度有限搜索是不完備的。第32頁，課件共54頁，創(chuàng)作于2023年2月

總結(jié)1、上述各種搜索方法的本質(zhì)是，以初始節(jié)點為根節(jié)點，按照既定的策略對狀態(tài)空間圖進行遍歷，并希望能夠盡早發(fā)現(xiàn)目標(biāo)節(jié)點。

2、由于對狀態(tài)空間圖遍歷的策略是既定的，因此這些方法統(tǒng)稱為盲目搜索方法。第33頁，課件共54頁，創(chuàng)作于2023年2月有信息搜索搜索過程中利用與問題有關(guān)的經(jīng)驗信息（啟發(fā)式信息）引入估價函數(shù)來估計節(jié)點位于解路徑上的“希望”，函數(shù)值越小“希望”越大搜索過程中按照估價函數(shù)的大小對OPEN表排序每次選擇估價函數(shù)值最小的節(jié)點作為下一步考察的節(jié)點6.2.7啟發(fā)式搜索第34頁，課件共54頁，創(chuàng)作于2023年2月A算法在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)f(n)=g(n)+h(n)對Open表中的節(jié)點進行排序，則該搜索算法為A算法。由于估價函數(shù)中帶有問題自身的啟發(fā)性信息，因此，A算法又稱為啟發(fā)式搜索算法。對啟發(fā)式搜索算法，又可根據(jù)搜索過程中選擇擴展節(jié)點的范圍，將其分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。第35頁，課件共54頁，創(chuàng)作于2023年2月A算法估價函數(shù)

f(x)=g(x)+h(x)從起始狀態(tài)到當(dāng)前狀態(tài)x的代價從當(dāng)前狀態(tài)x到目標(biāo)狀態(tài)的估計代價（啟發(fā)函數(shù)）g(x)有利于搜索的完備性，但影響搜索的效率。h(x)有利于提高搜索的效率，但影響搜索的完備性。第36頁，課件共54頁，創(chuàng)作于2023年2月設(shè)有如下結(jié)構(gòu)的移動將牌游戲：該游戲規(guī)則：當(dāng)一個牌移入相鄰的空位置時，費用為一個單位。一個牌至多可跳過兩個牌進入空位置，其費用等于跳過的牌數(shù)加1。要求：把所有的B都移至W的右邊，請設(shè)計啟發(fā)函數(shù)h(x)。解：根據(jù)要求可知，W左邊的B越少越接近目標(biāo)，因此可用W左邊B的個數(shù)作為h(x),即h(x)=3×(每個W左邊B的個數(shù)的總和)這里乘以系數(shù)3是為了擴大h(x)在f(x)中的比重。啟發(fā)函數(shù)示例BBBWWWE第37頁，課件共54頁，創(chuàng)作于2023年2月局部擇優(yōu)搜索基本思想： 當(dāng)一個節(jié)點被擴展以后，按f(x)對每一個子節(jié)點計算估價值，并選擇最小者作為下一個要考察的節(jié)點。搜索過程：把初始節(jié)點S0放入OPEN表，計算f(S0)。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并按估價值從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。深度優(yōu)先搜索、代價樹的深度優(yōu)先搜索均為局部擇優(yōu)搜索的特例。第38頁，課件共54頁，創(chuàng)作于2023年2月全局擇優(yōu)搜索基本思想： 每當(dāng)要選擇下一個節(jié)點進行考察時，全局擇優(yōu)搜索每次總是從OPEN表的全體節(jié)點中選擇一個估價值最小的節(jié)點。搜索過程：把初始節(jié)點S0放入OPEN表，計算f(S0)。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉(zhuǎn)第2步。擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并為每一個子節(jié)點都配置指向父節(jié)點的指針。把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小至大的順序進行排序，然后轉(zhuǎn)第2步。廣度優(yōu)先搜索、代價樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的特例。第39頁，課件共54頁，創(chuàng)作于2023年2月1968年，彼得.哈特對A算法進行了很小的修改，并證明了當(dāng)估價函數(shù)滿足一定的限制條件時，算法一定可以找到最優(yōu)解估價函數(shù)滿足一定限制條件的算法稱為A*算法f(x)=g(x)+h(x)A*算法的限制條件大于0不大于x到目標(biāo)的實際代價彼得.哈特6.2.8A*算法第40頁，課件共54頁，創(chuàng)作于2023年2月利用A*算法求解八數(shù)碼問題估價函數(shù)的定義f(x)=g(x)+h(x)g(x)：從初始狀態(tài)到x需要進行的移動操作的次數(shù)h(x)：=x狀態(tài)下錯放的棋子數(shù)滿足限制條件123845671238456781324567h(x)=1h(x)=2h(x)=4第41頁，課件共54頁，創(chuàng)作于2023年2月45631238456712384567123845671+31+51+51238456712384567123845672+42+32+312384567123845673+2

3+412384567123845673+3

3+4123845674+181324567123845675+05+25711238460+4752OPEN表CLOSED表第42頁，課件共54頁，創(chuàng)作于2023年2月第43頁，課件共54頁，創(chuàng)作于2023年2月估價函數(shù)對算法的影響不同的估價函數(shù)對算法的效率可能產(chǎn)生極大的影響不同的估價函數(shù)甚至產(chǎn)生不同的算法 f(x)=g(x)+h(x)h(x)=0：Dijkstra算法，非啟發(fā)式算法g(x)=0：貪婪搜索，無法保證找到解即使采用同樣的形式f(x)=g(x)+h(x)，不同的定義和不同的值也會影響搜索過程第44頁，課件共54頁，創(chuàng)作于2023年2月估價函數(shù)對算法的影響示例例：八數(shù)碼問題f(x)=g(x)+h(x)g(x)：從初始狀態(tài)到x需要進行的移動操作的次數(shù)h(x)：所有棋子與目標(biāo)位置的曼哈頓距離之和曼哈頓距離：兩點之間水平距離和垂直距離之和仍滿足估價函數(shù)的限制條件12384567h(x)=2+1+1+2=6第45頁，課件共54頁，創(chuàng)作于2023年2月3451238456712384567123845671+41+61+61238456712384567123845672+52+52+312384567123845673+2

3+4123845674+181324567123845675+05+20+5571123846752第46頁，課件共54頁，創(chuàng)作于2023年2月例：路徑規(guī)劃SG4G4G56445566A*算法被廣泛應(yīng)用于靜態(tài)路網(wǎng)中的最短路徑規(guī)劃用距離表示代價每一步可以往相鄰的8個無障礙格子移動，移動距離為1g(x)：從出發(fā)點S到當(dāng)前點x的距離h(x)：從當(dāng)前點x到目標(biāo)點G的距離4G56455665644G564455666564G564466575675566777745564455666567567