1樓：blue
直觀理解：A*演算法每次按照估價函式最小的原則來選取節點。假設估價函式估計的代價等於實際代價，那麼我直接就選取到最優路徑上的各個節點了；而A*演算法中估價函式估計的代價總是比實際代價更小一點，並且隨著選取節點數量的增多，估價函式估計的代價越來越接近於實際代價，從而不存在選取了更長路徑的情況。
(因為如果存在更短的路徑，那麼它的估計代價應該更小，因此優先被選取)。
1. 引理：A*結束前的任何時刻，open表中總是存在節點n，它是初始節點s到目標節點t的最優路徑上的乙個節點，且滿足：
f(n) <= f*(s)。（其中f*(s)表示從初始節點到目標節點的最短路徑的實際代價）
說人話： 對於最優路徑上的點，A*演算法估計的代價總是比實際最小代價更小一點。
證明：由於n是最優路徑上的節點，所以從初始節點s到n的實際代價總是最小的：g(n)=g*(n) ① (其中g*(n)表示從初始節點到節點n的最短路徑的實際代價)
另一方面，由於A*演算法的估價函式滿足：h(n)<=h*(n) ②
由①+②，得到：f(n)=h(n)+g(n)<= g*(n)+ h*(n)=f*(n) ③ (其中f*(n)表示從初始節點到目標節點的經過節點n的最短路徑的實際代價)
顯然，對於最優路徑上的任意乙個節點，其f*值應該相等，因此：f*(n)=f*(s) ④
由③和④，得到：f(n) <= f*(s) ⑤
注：這裡的證明其實是不夠嚴謹的，因為沒有證明n為什麼一定存在。實際上這裡應該用到的是結構歸納法的思想，如果一開始open表中的節點滿足這個命題，之後經過每一步的迭代又都滿足這個命題，所以原命題成立。
2. 然後用反證法證明A*演算法一定能找到最優解。
證明：對於目標節點t，顯然f(t)=g(t). ⑥
假設從初始節點s到目標節點t的路徑不是最優路徑，那麼：f(t)>f*(s) ⑦
由⑤和⑦，得到：open表中存在乙個節點n，使得：f(n)因此，A*演算法應該先拓展節點n, 這與A*演算法先拓展節點t矛盾。
說人話：假設A*演算法走過乙個非最優路徑上的點（記作節點a），那麼對於這條路徑來說，一定有實際代價》實際最小代價；但由於對於終點或終點附近的點，代價估計一定是準確的，即估計代價=實際代價；因此對於終點附近的點，如果它並不是最優路徑上的點，那麼估計代價》實際最小代價。但是根據引理，A*演算法結束之前一定能在open set中找到乙個估計代價《實際最小代價的節點（記作節點b），因此就應該先拓展節點b，而這與假設先拓展節點b矛盾。
請教乙個演算法題，最優解應該怎麼做？
Yuanfei Bi 最優要看題目的具體情況。拓展下，如果是stream問題，即有新數字加入陣列的話，能不能很快找出新陣列的最大m個數？這時候可以用極小堆。 那羅延 先說結論，下面我要推薦的演算法，計算複雜度為 O n 這個計算複雜度可以秒殺排序演算法了，而且應該比select median要快 首...
既然分手後不一定能找到更好的，為什麼還有那麼多人要分手？
北源 親身經歷吧，自己初戀的時候分手總覺得是對方錯，自己可以找到更好的，然而等自己談多了，卻發現很多還不如初戀 這種感覺隨著你談過的奇葩越多越強烈 最後談戀愛千萬不要和大齡還沒談過初戀的女生談，你會覺得三觀都亂了 總結一句就是談的多了現實了，理解了人無完人大家在一起最重要的還是看忍耐和磨合 順帶更新...
讀了研究生，就一定能找到好工作嗎
木鐸師兄 從來就沒有什麼救世主！我個人覺得乙個人成熟的乙個基本標誌是 基本不再會使用諸如 一定 絕對 百分百 這種絕對化的詞語。如果不想加入求職大軍的話，有兩個方法 乙個是努力提公升自己的競爭力，讓自己變得更加的優秀 第二個方法就是祈求時光倒流，回到那個包分配的計畫經濟時代。個別的例子缺乏足夠的說服...