（讀書報告、研究報告
考核科目 :人工智慧
學生所在院（系）:計算機學院
學生所在學科 :計學生姓名 : 學號 : 學生類別 :學考
核結果算機術科學與技術閱卷人
人工智慧讀書報告
——基於動態加權的a*搜尋演算法研究
1. 啟發式搜尋
啟發式搜尋就是在狀態空間中對每乙個搜尋的位置進行評估，選擇最好的位置，再從這個位置進行搜尋直到目標。在啟發式搜尋中，對位置的估價是十分重要的。採用了不同的評估方法可以有不同的效果。
最佳優先搜尋的最廣為人知的形式稱為a*搜尋.它把到達節點的耗散g(n)和從該節點到目標節點的消耗h(n)結合起來對節點進行評價：d(n)=g(n)+h(n)，因為以g(n)給出了從起始節點到節點n的路徑耗散，而h(n)是從節點n到目標節點的最低耗散路徑的估計耗散值，因此d(n)=經過節點n的最低耗散解的估計耗散.
這樣，如果我們想要找到最低耗散解，首先嘗試找到g(n)+h(n)值最小的節點是合理的。由a*定義可以發現這個策略不只是合理的:倘若啟發函式h(n)滿足一定的條件，搜尋既是完備的也是最優的。
如果把a*搜尋用於tree-search,它的最優性是能夠直接分析的。在這種情況下，如果h(n)是乙個可採納啟發式--也就是說，倘若h(n)從不會過高估計到達目標的耗散--a*演算法是最優的。可採納啟發式天生是最優的，因為他們認為求解問題的耗散是低於實際耗散的。
因為g(n)是到達節點n的確切耗散，我們得到乙個直接的結論：d(n)永遠不會高估經過節點n的解的實際耗散。常用的啟發演算法有：
蟻群演算法，遺傳演算法、模擬退火演算法等
greedy search on d outperforms search on h
2. 動態加權啟發式搜尋演算法
應用啟發式搜尋中的加權技術, 其主要目的是調整搜尋中深度優先與寬度優先的比值, 以提高搜尋效率。通常有兩種加權技術, 即常數加權與動態加權技術。由於在常數加權中, 同樣的加權量毫無區別地施用在每乙個節點上, 加權的作用取決於各單一節點。
而在動態加權中, 則會動態地對不同層上的節點施以不同的加權量。故一般地, 採用動態加權技術的啟發式搜尋效率要比靜態( 即常數) 加權好
定義一. 乙個搜尋演算法是ε可採納的, 如果該演算法總能找到一條求解路徑, 其耗散值至少為??ft*(s)。
這裡ft*(s)表示從初始節點s出發至目標節點的最佳路徑的耗散值，ε∈(0,1) 。根據加權技術的基本思想, 啟發式評價函式的動態加權應達到這樣的效果: 在搜尋樹的淺層, 搜尋應呈現深度優先搜尋的特性; 而隨著搜尋樹的層次越來越深, 應逐步呈現出寬度優先搜尋的特性。
據此, 我們可以定義動態加權的啟發式評價函式為:ft(n)?t(gt(n),??
(1?d(n)/n)?ht(n)) 其中d(n) 表示節點n在搜尋樹中的深度, n 表示預期的目標節點在搜尋樹中的深度
定義二. 若演算法ra?採用上述的啟發式評價函式ft, 且ht≥ht*,則稱演算法raε為演算法ra
若模t滿足t(??a,??b)???
t(a,b),這裡ε∈(0,1)，屬於最佳路徑上的且在open表中屬於最淺層的任意節點n，仍然有gt(n)=gt*(n) ，最後經過推導可以得到：ft(n)?t(gt(n),??
(1?d(n)/n)?ht(n
=t(gt*(n),??(1?d(n)/n)?
ht(n)) ≥t(gt*(n),??(1?d(n)/n)?
ht*(n)) ≥t(gt*(n),??ht*(n)) ≥t(??gt*(n),??
ht*(n)) ≥??ft*(s
3. 動態加權不能克服指數**問題
martelli已經證明了，在最壞情況下，演算法a*的時間複雜度為o(2n) 這裡m是圖的節點數。使用動態加權技術的本質在於提高搜尋效率，但是動態加權技術很難消除指數**現象
定義三. 啟發式評價函式ht』被稱為引導了乙個?(n)的標準化誤差，若對於b元樹上的所有節點，存在兩個固定的正數β和γ和乙個正交函式
ht(n)?ht*(n)ht(n)?ht*(n
b , γ>1和p[||??]??/b ?<1 使得p
?(ht*(n))?(ht*(n
1定理二.若ht(n) 引出?(n)=n的標準化誤差，則當0<?0 <1 1
d(n時，啟發式評價函式為aht(n)???(1?)?ht(n) 引出同樣的?(n)?n 的n
數學讀書報告
讀 數學中的美 吳振奎 吳旻著 五月中旬我閱讀了吳振奎 吳旻兩位先生所著的 數學中的美 一書，書中從簡潔 和諧 奇異三個方面記述了數學的各個分支中的美。書中包含了從初等數學到高等數學的各方面知識。此書從哲學範疇出發，配以數學例項去解釋數學潛在規律，探索運用美學原理指導數學創造 發現的途徑，這對數學的...
《日出》讀書報告
對人物的刻畫，可以說是 日出 這部三幕劇的最成功之處。作者根據每個人物身份和經歷的不同，分別採取不同的描述方式，以塑造鮮明的人物形象。例如，對於作品的主人公之一陳白露和李石清，作者主要是描述他們性格的複雜性 內心的激烈衝突及其被窒息被毒化的心靈歷程，而對胡 四 顧八奶奶 張喬治 福生等形象的刻畫，則...
活著讀書報告
許多的不幸主要是針對底層的人民，他們弱小，缺乏保護自己的基本力量 他們甚至是作為上層建築的某些犧牲品。像螞蟻一樣，逆來順受，經受著生活的歷練和折磨，卻無能無力。他們既不能像鬥士或者英雄那樣直面慘淡的人生，奮起反抗 也不能爬到食物鏈的上層，改變自己的現狀，有的只是煎熬，逆來順受。但是從文中我們並沒有過...