導航:首頁 > 源碼編譯 > 啟發式演算法例題

啟發式演算法例題

發布時間:2022-09-26 11:59:50

㈠ 經典的啟發式演算法包括哪些

蟻群,模擬退火,禁忌搜索,人工神經網路等。。。
推薦教材《現代優化計算方法》第二版 邢文訓,謝金星 清華大學出版社
另一本補充,《最優化理論與方法》 黃平 清華大學出版社

第一本教材網上有電子版,你自己搜下

㈡ 元啟發式演算法的演算法原理

1. 從一個或多個候選解開始作為初始值(pop(t))。
2. 根據初始值計算目標函數值
3. 基於已獲得的信息,通過個體變異、組合等方法不斷更新候選解域。
4. 新的候選解域進入下一輪迭代(pop(t+1))
如下圖:

例如它常能發現很不錯的解,但也沒辦法證明它不會得到較壞的解;它通常可在合理時間解出答案,但也沒辦法知道它是否每次都可以這樣的速度求解。有時候人們會發現在某些特殊情況下,啟發式演算法會得到很壞的答案或效率極差,然而造成那些特殊情況的數據結構,也許永遠不會在現實世界出現。因此現實世界中啟發式演算法常用來解決問題。啟發式演算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。有一類的通用啟發式策略稱為元啟發式演算法(metaheuristic algorithm) ,通常使用亂數搜尋技巧。他們可以應用在非常廣泛的問題上,但不能保證效率。

㈢ 節約里程法的典型例題有哪些

節約里程法基本原理是幾何學中三角形一邊之長必定小於另外兩邊之和。往返發貨與巡迴發貨車輛行走距離∆l=[2(l1+l2)]-(l1+l2+l3)=l1+l2-l3。

㈣ A*演算法——啟發式路徑搜索

A*是一種路徑搜索演算法,比如為游戲中的角色規劃行動路徑。

A* 演算法的輸入是, 起點(初始狀態) 終點(目標狀態) ,以及兩點間 所有可能的路徑 ,以及涉及到的 中間節點(中間狀態) ,每兩個節點間的路徑的 代價

一般還需要某種 啟發函數 ,即從任意節點到終點的近似代價,啟發函數能夠非常快速的估算出該代價值。

輸出是從 起點到終點的最優路徑 ,即代價最小。同時,好的啟發函數將使得這一搜索運算盡可能高效,即搜索盡量少的節點/可能的路徑。

f(n)=g(n)+h(n)

f(n) 是從初始狀態經由狀態n到目標狀態的代價估計

g(n) 是在狀態空間中從初始狀態到狀態n的實際代價

h(n) 是從狀態n到目標狀態的最佳路徑的估計代價

A*演算法是從起點開始,檢查所有可能的擴展點(它的相鄰點),對每個點計算g+h得到f,在所有可能的擴展點中,選擇f最小的那個點進行擴展,即計算該點的所有可能擴展點的f值,並將這些新的擴展點添加到擴展點列表(open list)。當然,忽略已經在列表中的點、已經考察過的點。

不斷從open list中選擇f值最小的點進行擴展,直到到達目標點(成功找到最優路徑),或者節點用完,路徑搜索失敗。

演算法步驟:

參考

A* 演算法步驟的詳細說明請參考 A*尋路演算法 ,它包含圖文案例清楚的解釋了A*演算法計算步驟的一些細節,本文不再詳細展開。

看一下上面參考文檔中的案例圖,最終搜索完成時,藍色邊框是close list中的節點,綠色邊框是open list中的節點,每個方格中三個數字,左上是f(=g+h),左下是g(已經過路徑的代價),右下是h(估計未經過路徑的代價)。藍色方格始終沿著f值最小的方向搜索前進,避免了對一些不好的路徑(f值較大)的搜索。(圖片來自 A*尋路演算法 )

現在我們可以理解,A*演算法中啟發函數是最重要的,它有幾種情況:

1) h(n) = 0
一種極端情況,如果h(n)是0,則只有g(n)起作用,此時A*演變成Dijkstra演算法,這保證能找到最短路徑。但效率不高,因為得不到啟發。

2) h(n) < 真實代價
如果h(n)經常都比從n移動到目標的實際代價小(或者相等),則A*保證能找到一條最短路徑。h(n)越小,A*擴展的結點越多,運行就得越慢。越接近Dijkstra演算法。

3) h(n) = 真實代價
如果h(n)精確地等於從n移動到目標的代價,則A*將會僅僅尋找最佳路徑而不擴展別的任何結點,這會運行得非常快。盡管這不可能在所有情況下發生,你仍可以在一些特殊情況下讓它們精確地相等(譯者:指讓h(n)精確地等於實際值)。只要提供完美的信息,A*會運行得很完美,認識這一點很好。

4) h(n) > 真實代價
如果h(n)有時比從n移動到目標的實際代價高,則A*不能保證找到一條最短路徑,但它運行得更快。

5) h(n) >> 真實代價
另一種極端情況,如果h(n)比g(n)大很多,則只有h(n)起作用,A*演變成BFS演算法。

關於啟發函數h、Dijkstra演算法、BFS(最佳優先搜索)演算法、路徑規劃情況下啟發函數的選擇、演算法實現時List的數據結構、演算法變種等等更多問題,請參考: A*演算法

㈤ 貪心演算法的例題分析

例題1、
[0-1背包問題]有一個背包,背包容量是M=150。有7個物品,物品不可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大,但不能超過總容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
價值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析:
目標函數:∑pi最大
約束條件是裝入的物品總重量不超過背包容量:∑wi<=M(M=150)
⑴根據貪心的策略,每次挑選價值最大的物品裝入背包,得到的結果是否最優?
⑵每次挑選所佔重量最小的物品裝入是否能得到最優解?
⑶每次選取單位重量價值最大的物品,成為解本題的策略。
值得注意的是,貪心演算法並不是完全不可以使用,貪心策略一旦經過證明成立後,它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一,這是由於它簡單易行,構造貪心策略不是很困難。
可惜的是,它需要證明後才能真正運用到題目的演算法中。
一般來說,貪心演算法的證明圍繞著:整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略,都是無法成立(無法被證明)的,解釋如下:
⑴貪心策略:選取價值最大者。
反例:
W=30
物品:A B C
重量:28 12 12
價值:30 20 20
根據策略,首先選取物品A,接下來就無法再選取了,可是,選取B、C則更好。
⑵貪心策略:選取重量最小。它的反例與第一種策略的反例差不多。
⑶貪心策略:選取單位重量價值最大的物品。
反例:
W=30
物品:A B C
重量:28 20 10
價值:28 20 10
根據策略,三種物品單位重量價值一樣,程序無法依據現有策略作出判斷,如果選擇A,則答案錯誤。
【注意:如果物品可以分割為任意大小,那麼策略3可得最優解】
對於選取單位重量價值最大的物品這個策略,可以再加一條優化的規則:對於單位重量價值一樣的,則優先選擇重量小的!這樣,上面的反例就解決了。
但是,如果題目是如下所示,這個策略就也不行了。
W=40
物品:A B C
重量:25 20 15
價值:25 20 15
附:本題是個DP問題,用貪心法並不一定可以求得最優解,以後了解了動態規劃演算法後本題就有了新的解法。
例題2、
馬踏棋盤的貪心演算法
123041-23 XX
【問題描述】
馬的遍歷問題。在8×8方格的棋盤上,從任意指定方格出發,為馬尋找一條走遍棋盤每一格並且只經過一次的一條路徑。
【初步設計】
首先這是一個搜索問題,運用深度優先搜索進行求解。演算法如下:
⒈ 輸入初始位置坐標x,y;
⒉ 步驟 c:
如果c> 64輸出一個解,返回上一步驟c--
(x,y) ← c
計算(x,y)的八個方位的子結點,選出那些可行的子結點
循環遍歷所有可行子結點,步驟c++重復2
顯然⑵是一個遞歸調用的過程,大致如下:
C++程序: #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//輸出一個解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八個方位子結點ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//遞歸調用s[tx][ty]=0;}}Pascal程序: ProgramYS;ConstFXx:array[1..8]of-2..2=(1,2,2,1,-1,-2,-2,-1);FXy:array[1..8]of-2..2=(2,1,-1,-2,-2,-1,1,2);VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8個方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{確定新坐標是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判斷是否走過}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐標}If(Nx=x1)and(Ny=y1)Theninc(total)elseFind(Nx,Ny);{遞歸}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{讀入開始坐標}Readln(x1,y1);{讀入結束坐標}If(x>10)or(y>10)or(x1>10)or(y1>10)Thenwriteln('Error'){判斷是否越界}ElseFind(x,y);Writeln('Total:',total){打出總數}END.這樣做是完全可行的,它輸入的是全部解,但是馬遍歷當8×8時解是非常之多的,用天文數字形容也不為過,這樣一來求解的過程就非常慢,並且出一個解也非常慢。
怎麼才能快速地得到部分解呢?
【貪心演算法】
其實馬踏棋盤的問題很早就有人提出,且早在1823年,J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時,優先選擇『出口』最小的進行搜索,『出口』的意思是在這些子結點中它們的可行子結點的個數,也就是『孫子』結點越少的越優先跳,為什麼要這樣選取,這是一種局部調整最優的做法,如果優先選擇出口多的子結點,那出口少的子結點就會越來越多,很可能出現『死』結點(顧名思義就是沒有出口又沒有跳過的結點),這樣對下面的搜索純粹是徒勞,這樣會浪費很多無用的時間,反過來如果每次都優先選擇出口少的結點跳,那出口少的結點就會越來越少,這樣跳成功的機會就更大一些。這種演算法稱為為貪心演算法,也叫貪婪演算法或啟發式演算法,它對整個求解過程的局部做最優調整,它只適用於求較優解或者部分解,而不能求最優解。這樣的調整方法叫貪心策略,至於什麼問題需要什麼樣的貪心策略是不確定的,具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高,如果只要求出一個解甚至不用回溯就可以完成,因為在這個演算法提出的時候世界上還沒有計算機,這種方法完全可以用手工求出解來,其效率可想而知。

㈥ 什麼是啟發式

這兩天在看關於民航調度的文章,很多文章中都提到「啟發式」演算法,感覺和智能演算法類似,那到底演算法呢?我找到如下的一些我認為比較好的解釋:------------------------------------------------------------------------------------------------------------------------A heuristic (hyu-'ris-tik) is the art and science of discovery and invention. The word comes from the same Greek root as "eureka" meaning "to find". A heuristic for a given problem is a way of directing your attention fruitfully to a solution. It is different from an algorithm in that a heuristic merely serves as a rule-of-thumb or guideline, as opposed to an invariant procere. Heuristics may not always achieve the desired outcome, but can be extremely valuable to problem-solving processes. Good heuristics can dramatically rece the time required to solve a problem by eliminating the need to consider unlikely possibilities or irrelevant states. As such, it is particularly useful to those in the process of discovery and the are constantly rethinking their strategies in the face of a stubborn unknown. --------------------------------------------------------------------------------------------------------------------------啟發式方法(試探法)是一種幫你尋求答案的技術,但它給出的答案是具有偶然性的(subject to chance),因為啟發式方法僅僅告訴你該如何去找,而沒有告訴你要找什麼。它並不告訴你該如何直接從A 點到達B 點,它甚至可能連A點和B點在哪裡都不知道。實際上,啟發式方法是穿著小丑兒外套的演算法:它的結果不太好預測,也更有趣,但不會給你什麼30 天無效退款的保證。 駕駛汽車到達某人的家,寫成演算法是這樣的:沿167 號高速公路往南行至Puyallup;從South Hill Mall 出口出來後往山上開4.5 英里;在一個雜物店旁邊的紅綠燈路口右轉,接著在第一個路口左轉;從左邊褐色大房子的車道進去,就是North Cedar 路714 號。用啟發式方法來描述則可能是這樣:找出上一次我們寄給你的信,照著信上面的寄出地址開車到這個鎮;到了之後你問一下我們的房子在哪裡。這里每個人都認識我們——肯定有人會很願意幫助你的;如果你找不到人,那就找個公共電話亭給我們打電話,我們會出來接你。演算法和啟發式方法之間的差別很微妙,兩個術語的意思也有一些重疊。就本書的目的而言,它們之間的差別就在於其距離最終解決辦法的間接程度:演算法直接給你解決問題的指導,而啟發式方法則告訴你該如何發現這些指導信息,或者至少到哪裡去尋找它們。----------------------------------------------------------------------------------------------------------------------------從上面的啟發式演算法的解釋可以看出,啟發式演算法的難點是建立符合實際問題的一系列啟發式規則。

㈦ 有關啟發式演算法(Heuristic Algorithm)的一些總結

節選自維基網路:

啟發法 ( heuristics ,源自古希臘語的εὑρίσκω,又譯作:策略法、助發現法、啟發力、捷思法)是指 依據有限的知識 (或「不完整的信息」)在短時間內找到問題解決方案的一種技術。

它是一種依據 關於系統的有限認知 和 假說 從而得到關於此系統的結論的分析行為。由此得到的解決方案有可能會偏離最佳方案。通過與最佳方案的對比,可以確保啟發法的質量。

計算機科學的兩大基礎目標,就是 發現可證明其運行效率良好 且可 得最佳解或次佳解 的演算法。

而啟發式演算法則 試圖一次提供一個或全部目標 。例如它常能發現很不錯的解, 但也沒辦法證明它不會得到較壞的解 ; 它通常可在合理時間解出答案,但也沒辦法知道它是否每次都可以這樣的速度求解。

有時候人們會發現在某些特殊情況下,啟發式演算法會得到很壞的答案或效率極差, 然而造成那些特殊情況的數據結構,也許永遠不會在現實世界出現

因此現實世界中啟發式演算法很常用來解決問題。啟發式演算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。

有一類的 通用啟發式策略稱為元啟發式演算法(metaheuristic) ,通常使用隨機數搜索技巧。他們可以應用在非常廣泛的問題上,但不能保證效率。

節選自網路:

啟發式演算法可以這樣定義:一個 基於直觀或經驗構造 的演算法, 在 可接受的花費(指計算時間和空間)下給出待解決組合優化問題每一個實例的一個可行解 , 該可行解與最優解的偏離程度一般不能被預計。 現階段,啟發式演算法以仿自然體演算法為主,主要有蟻群演算法、模擬退火法、神經網路等。

目前比較通用的啟發式演算法一般有模擬退火演算法(SA)、遺傳演算法(GA)、蟻群演算法(ACO)。

模擬退火演算法(Simulated Annealing, SA)的思想借鑒於固體的退火原理,當固體的溫度很高的時候,內能比較大,固體的內部粒子處於快速無序運動,當溫度慢慢降低的過程中,固體的內能減小,粒子的慢慢趨於有序,最終,當固體處於常溫時,內能達到最小,此時,粒子最為穩定。模擬退火演算法便是基於這樣的原理設計而成。

求解給定函數的最小值:其中,0<=x<=100,給定任意y的值,求解x為多少的時候,F(x)最小?

遺傳演算法(Genetic Algorithm, GA)起源於對生物系統所進行的計算機模擬研究。它是模仿自然界生物進化機制發展起來的隨機全局搜索和優化方法,借鑒了達爾文的進化論和孟德爾的遺傳學說。其本質是一種 高效、並行、全局搜索 的方法,能在搜索過程中自動獲取和積累有關搜索空間的知識,並 自適應 地控制搜索過程以求得最佳解。

給定一組五個基因,每一個基因可以保存一個二進制值 0 或 1。這里的適應度是基因組中 1 的數量。如果基因組內共有五個 1,則該個體適應度達到最大值。如果基因組內沒有 1,那麼個體的適應度達到最小值。該遺傳演算法希望 最大化適應度 ,並提供適應度達到最大的個體所組成的群體。

想像有一隻螞蟻找到了食物,那麼它就需要將這個食物待會螞蟻穴。對於這只螞蟻來說,它並不知道應該怎麼回到螞蟻穴。

這只螞蟻有可能會隨機選擇一條路線,這條路可能路程比較遠,但是這只螞蟻在這條路上留下了記號(一種化學物質,信息素)。如果這只螞蟻繼續不停地搬運食物的時候,有其它許多螞蟻一起搬運的話,它們總會有運氣好的時候走到更快返回螞蟻穴的路線。當螞蟻選擇的路線越優,相同時間內螞蟻往返的次數就會越多,這樣就在這條路上留下了更多的信息素。

這時候,螞蟻們就會選擇一些路徑上信息素越濃的,這些路徑就是較優的路徑。當螞蟻們不斷重復這個過程,螞蟻們就會更多地向更濃的信息素的路徑上偏移,這樣最終會確定一條路徑,這條路徑就是最優路徑。

㈧ 什麼是啟發式演算法

大自然是神奇的,它造就了很多巧妙的手段和運行機制。受大自然的啟發,人們從大自然的運行規律中找到了許多解決實際問題的方法。對於那些受大自然的運行規律或者面向具體問題的經驗、規則啟發出來的方法,人們常常稱之為啟發式演算法(Heuristic Algorithm)。現在的啟發式演算法也不是全部來自然的規律,也有來自人類積累的工作經驗。 駕駛汽車到達某人的家,寫成演算法是這樣的:沿167 號高速公路往南行至陽谷;從陽谷高速出口出來後往山上開4.5 英里;在一個雜物店旁邊的紅綠燈路口右轉,接著在第一個路口左轉;從左邊褐色大房子的車道進去,就是某人的家。 啟發式方法來描述則可能是這樣:找出上一次我們寄給你的信,照著信上面的寄出地址開車到這個鎮;到了之後你問一下我們的房子在哪裡。這里每個人都認識我們——肯定有人會很願意幫助你的;如果你找不到人,那就找個公共電話亭給我們打電話,我們會出來接你。

㈨ 什麼是啟發式搜索並以八數碼難題為例,說明其原理

啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估,得到最好的位置,再從這個位置進行搜索直到目標。這樣可以省略大量無謂的搜索路徑,提高了效率。在啟發式搜索中,對位置的估價是十分重要的。採用了不同的估價可以有不同的效果。我們先看看估價是如何表示的。
啟發中的估價是用估價函數表示的,如:
最佳優先搜索的最廣為人知的形式稱為A*搜索(發音為「A星搜索」).它把到達節點的耗散g(n)
和從該節點到目標節點的消耗h(n)結合起來對節點進行評價:f(n)=g(n)+h(n)
因為以g(n)給出了從起始節點到節點n的路徑耗散,而h(n)是從節點n到目標節點的最低耗散路徑的估計耗散值,因此f(n)=經過節點n的最低耗散解的估計耗散.這樣,如果我們想要找到最低耗散解,首先嘗試找到g(n)+h(n)值最小的節點是合理的。可以發現這個策略不只是合理的:倘若啟發函數h(n)滿足一定的條件,A*搜索既是完備的也是最優的。
如果把A*搜索用於Tree-Search,它的最優性是能夠直接分折的。在這種情況下,如果h(n)是一個可採納啟發式--也就是說,倘若h(n)從不會過高估計到達目標的耗散--A*演算法是最優的。可採納啟發式天生是最優的,因為他們認為求解問題的耗散是低於實際耗散的。因為g(n)是到達節點n的確切耗散,我們得到一個直接的結論:f(n)永遠不會高估經過節點n的解的實際耗散.
啟發演算法有:
蟻群演算法,遺傳演算法、模擬退火演算法等
蟻群演算法是一種來自大自然的隨機搜索尋優方法,是生物界的群體啟發式行為,現己陸續應用到組合優化、人工智慧、通訊等多個領域。蟻群演算法的正反饋性和協同性使其可用於分布式系統,隱含的並行性更使之具有極強的發展潛力。從數值模擬結果來看,它比目前風行一時的遺傳演算法、模擬退火演算法等有更好的適應性。

㈩ 啟發式演算法的最短路徑

所謂的最短路徑問題有很多種意思, 在這里啟發式指的是一個在一個搜尋樹的節點上定義的函數h(n),用於評估從此節點到目標節點最便宜的路徑。啟發式通常用於資訊充分的搜尋演算法,例如最好優先貪婪演算法與A*。最好優先貪婪演算法會為啟發式函數選擇最低代價的節點;A*則會為g(n) + h(n)選擇最低代價的節點,此g(n)是從起始節點到目前節點的路徑的確實代價。如果h(n)是可接受的(admissible)意即h(n)未曾付出超過達到目標的代價,則A*一定會找出最佳解。
最能感受到啟發式演算法好處的經典問題是n-puzzle。此問題在計算錯誤的拼圖圖形,與計算任兩塊拼圖的曼哈頓距離的總和以及它距離目的有多遠時,使用了本演算法。注意,上述兩條件都必須在可接受的范圍內。

閱讀全文

與啟發式演算法例題相關的資料

熱點內容
程序員節西安市 瀏覽:687
單片機的閃燈 瀏覽:965
phpmime映射 瀏覽:583
關鍵特徵分析python 瀏覽:992
linux粘滯位 瀏覽:137
安卓如何把備忘錄調成黑色 瀏覽:862
dhcp伺服器手動分配ip地址 瀏覽:308
阿里雲國內伺服器數量 瀏覽:455
壓縮機安全裕度 瀏覽:226
android交叉編譯環境 瀏覽:775
美團雲伺服器質量怎麼樣 瀏覽:396
蘋果手機游戲解壓包怎麼安裝 瀏覽:446
java程序員面試流程 瀏覽:681
遼寧圖片加密軟體地址 瀏覽:932
程序員35後應該學些啥技術 瀏覽:724
蘋果怎麼把app還原成ipa包 瀏覽:358
天正怎麼分解加密圖紙 瀏覽:829
你喜歡的大胸部電影 瀏覽:755
飛盧破解版網址 瀏覽:632
怎麼在米家app裡面找到小愛同學 瀏覽:208