引理2: a*結束前, open表中必存在f(n)<=f*(s)的節點(n是在最佳路徑上的節點)。
證明: 設從初始節點s到目標節點t的一條最佳路徑序列為
(n0 = s, n1, …, nk = t)
演算法初始化時, s在open中, 由於a*沒有結束, 在open中存在最佳路徑上的節點。設open表中的第乙個節點n是處在最佳路徑序列中(至少有乙個這樣的節點, 因s一開始是在open上), 顯然n的先輩節點np,已在closed中, 因此能找到s到np,的最佳路徑, 而n也在最佳路徑上, 因而s到n的最佳路徑也能找到, 因此有
f(n) = g(n) + h(n) = g*(n) + h(n) g*(n) + h*(n) = f*(n)
而最佳路徑上任一節點均有f* = f*(s) (f*(s)是最佳路徑的耗散值), 所以f(n)f*(s)。[證畢]
定理2: 對無限圖, 若從初始節點s到目標節點 t有路徑存在, 則a*也一定成功結束。
證明: 假定a*不結束, 由引理1有f(n) > f*(s), 或open表中最小的乙個f值也變成無界, 這與引理2的結論矛盾, 所以a*只能成功結束。[證畢]
推論1: open表上任一具有f(n) < f*(s)的節點n, 最終都將被 a*選作為擴充套件的節點。
定理3: 若存在初始節點s到目標節點t的路徑, 則a*必能找到最佳解結束。
證明: (1) 由定理1、2知a*一定會找到乙個目標節點結束。
(2) 設找到的乙個目標節點t結束, 而s→t不是一條最佳路徑, 即
f(t) = g(t) > f*(s)
而根據引理2知結束前open表上有節點n, 且處在最佳路徑上, 並有f(n) f*(s), 所以
f(n) f*(s) < f(t)
這時演算法a*應選n作為當前點擴充套件, 不可能選t, 從而也不會去測試目標節點t, 即這與假定a*選t結束矛盾, 所以a*只能結束在最佳路徑上。[證畢]
推論2: a*選作擴充套件的任一節點n, 有f(n) f*(s)
證明: 令n是由a*選作擴充套件的任一節點, 因此n不會是目標節點, 且搜尋沒有結束, 由引理2而知在open中有滿足f(n')f*(s)的節點n'。若n = n', 則f(n) f*(s), 否則選n擴充套件, 必有f(n)f(n'), 所以f(n) f*(s)成立。
[證畢]
人工智慧實驗報告
江蘇科技大學 實驗報告 2012 2013學年第2學期 課程名稱人工智慧 學生姓名陳嘉生 學生學號 1040501211 院系數理學院 專業 資訊與計算科學 2013年 5 月 18 日 一 實驗目的 狀態空間表示法是人工智慧領域最基本的知識表示方法之一，也是進一步學習狀態空間搜尋策略的基礎，本實驗...
人工智慧實驗報告
人工智慧 實驗指導及報告書 2011 2012 學年第 1 學期 姓名 張輔祥 學號 090509110 班級 09計科一 指導教師 電腦科學與工程學院 2011 一 實驗目的 1 理解人工智慧中產生式相關知識的基本原理和方法 二 實驗內容 如圖所示放置3根柱子，其中一根從上往下按由小到大順序串有若...
人工智慧實驗報告
南京資訊工程大學實驗 實習 報告 實驗 實習 名稱 matlab程式設計實驗日期得分指導教師 系計科專業年級班次 姓名學號 1 實驗目的 1 通過學習matlab程式設計來進一步了解人工智慧 2 通過上機實習編寫matlab程式，從而對matlab有所基本了解。為更好地學習人工智慧知識打下基礎。二 ...