"一、何謂螞蟻演算法？
　　螞蟻演算法Ant Colony Optimization，ACO(也有人稱Ant Colony System，ACS；或者再更簡稱AC)，是一種用來在圖中尋找優化路徑的機率型技術。在1992年Dorigo等人利用了螞蟻群體合作尋找食物的行為，設計出一個用於處理最佳化問題的螞蟻演算法。1996年Dorigo 將ACS演算法與GA、SA等啟發式演算法以TSPLIB國際列題進行比較，其結果皆優於其他的演算法，其結果與最佳解誤差皆小於3.5%。
 [@more@]

二、簡介
　　有看過家裡常常會有螞蟻在牆壁上或是角落，排成一排，比值的從巢穴朝著食物而去？螞蟻依賴的不是視力，更不可能是他們的智慧，螞蟻們所憑藉的是牠們身上獨特的費洛蒙，靠著費洛蒙，讓許多螞蟻可以選擇到相對來說較好的路徑來行走。

    現實生活中我們不可能去預測螞蟻的複雜行為，那我們該如何利用螞蟻的特性去研究這項演算法？其實我們可以利用訂定幾項規則出來，藉以突顯螞蟻這些複雜行為中的規律，所以我們可以由這些規則，撰寫出簡單的程式碼，來控制螞蟻的行為。畢竟，我們不需要模擬螞蟻的所有行為，我們只是需要他們找尋出問題的最佳解出來罷了。

　　三、訂定規則
　　上面提到我們可以藉由制定一些規則來突顯、加強螞蟻行為的特色，然後就可以利用這些特徵，來撰寫出程式，那基本上我們制定規則分為兩大類。

? 路徑的選擇規則：『Pseudo－Random-Proportional Rule』
? 費洛蒙更新規則：『Online Update』、『Offline Update』

　　1. 路徑的選擇規則
　　在Dorigo於1997年提出的螞蟻演算法尋路規中，利用路徑選擇規則選擇路徑以縮短計算時間，而且只在最好的解增加費洛蒙的痕跡，經實驗證明，只在最好的解上增加費洛蒙的設計，確實有助於螞蟻能最快搜尋到最佳解。

　　2. 費洛蒙更新規則
　　螞蟻演算法中的費洛蒙更新規則也分為兩大類，一類是費洛蒙及時更新，另一類則是費洛蒙離線更新，前者用在每隻人工螞蟻走過該路徑後，後者是在該回合結束後，針對費洛蒙值做一些適度的變更。當然，這個機制不僅僅影響了接下來螞蟻做路徑選擇的決策，還對最後路徑解的好壞有著緊密的相關。

　　(1)費洛蒙即時更新(Online Update)規則
　　費洛蒙的濃度，顧名思義，跟路徑上的螞蟻數量成正比與此路徑的距離長度成反比。這項規則所著重的是路徑的熱門程度，也就是費洛蒙濃度對螞蟻做出選擇時的影響，並不把距離因素考慮進去。

　　(2)費洛蒙離線更新(Offline Update)規則
　　在該流程結束後，對於最佳路徑解，最一些費洛蒙濃度的調整、變更，這就稱為費洛蒙離線更新。同時，對其餘非最佳路徑之解做費洛蒙蒸發的動作，如此一來，在下次行程執行時，最佳路徑解被選擇的機率就會大大的增加。

　　在完成規則的制定之後，螞蟻們之間都沒有什麼直接的關聯性，牠們處在這個大環境下利用散發費洛蒙來溝通。如果有一隻螞蟻找到了食物，那牠就利用走過的路徑上殘留的費洛蒙來告知他的親朋好友說『嘿！這有食物！』，那等到其他的螞蟻經過附近，發現費洛蒙的存在後，自然就會聚集在一起，想當然的，費洛蒙的濃度也就會越來越高。
　　到目前為止我們都是屬於利用費洛蒙來判斷該路徑是否為最佳路徑解，那有沒有想過，第一個發現食物的螞蟻，牠是如何找到食物的呢？這隻小螞蟻從蟻穴出發時，所有路徑費洛蒙的濃度都是一樣的，也就是說，這隻螞蟻選擇任何一條路經的機率都是相同的，既然沒有外部因素的影響，那螞蟻就基於自身本能做移動了。小螞蟻會朝著一個方向前進，但是並不是保持直線，可能會走的歪歪扭扭，有一定的隨機性，使得螞蟻運動起來具有了一定的目的性，儘量保持原來的方向，但是卻又有新的試探，尤其當碰到障礙物的時候它會立刻改變方向，這可以看成一種選擇的過程，也就是環境的障礙物讓螞蟻的某個方向正確，而其他方向則不對。這就解釋了為什麼這隻小螞蟻在複雜像迷宮的現實世界中仍然能找到隱蔽的食物。
　　螞蟻演算法也可以用來解決網狀網路跳點問題，當網路流量或基地站負載改變時，透過此規劃模式背後的改良式蟻群演算機制搜尋優化路由組合，可預見的，其能力將會優於目前WiMax所使用的傳統跳點規劃方法。ACO也被應用來解許多困難的尋優問題(NP- Hard problems), 如 Traveling salesman problem, quadratic assignment problem，等…

　　四、螞蟻演算法範例
　　1. Initialize:
　　　　Set t:=0　　　　　　　　　　　　　 {t is the time counter}
　　　　Set NC:=0 　　　　　　　　　　　　{NC is the cycles counter}
　　　　For every edge (i,j) set an initial value ?ij(t)=c for trail intensity and ??ij= 0
　　　　Place the m ants on the n nodes

　　2. Set s:=1 {s is the tabu list index}
　　　For k:=1 to m do
　　　　Place the starting town of the k-th ant in tabuk(s)
　　3. Repeat until tabu list is full 　　{this step will be repeated (n-1) times}
　　　　Set s:=s+1
　　　　For k:=1 to m do
　　　　　Choose the town j to move to, with probability pijk (t) given by equation (4)
　　　　　　　　　　　　　　　　　　　{at time t the k-th ant is on town i=tabuk(s-1)}
　　　　Move the k-th ant to the town j
　　　　Insert town j in tabuk(s)

　　4. For k:=1 to m do
　　　　Move the k-th ant from tabuk(n) to tabuk(1)
　　　　Compute the length Lk of the tour described by the k-th ant
　　　　Update the shortest tour found
　　　For every edge (i,j)
　　　　For k:=1 to m do
　　　　　??ki , j ?　Q/ Lk ，if (i, j) ??tour described by tabuk
　　　　　　　　　　　0　，otherwise
　　　　　??k ij : ????ij ????ij

　　5. For every edge (i,j) compute ?ij(t+n) according to equation ?ij(t+n)=?.?ij(t)+??ij
　　　Set t:=t+n
　　　Set NC:=NC+1
　　　For every edge (i,j) set ??ij:=0

　　6. If (NC < NCMAX)
　　　then
　　　　Empty all tabu lists
　　　　Goto step 2
　　　else
　　　　Print shortest tour
　　　　Stop

　　　　若在該演算法執行NC圈後停止，這個演算法的時間複雜度會為O(NC．n２m)，事實上，步驟1 is O(n2+m)，步驟2 is O(m)，步驟3 is O(n2.m)，步驟4 is O(n2.m)，步驟5 is O(n2)，步驟6 is O(n.m)。既然已經利用實驗找到蟻穴跟螞蟻數量的線性關係，所以該演算法的時間複雜度為??NC.n3)。

　　旅行推銷員問題 (TSP)
　　一地區有若干的城市，城市之間都有道路相連，但卻有長短之分，有一位推銷員從某一城市出發，途中須經過所有城市，最後回到原點，問這位推銷員要怎麼走，才能讓這條路徑最短？
　　Loop
  　　randomly position num_ants on nun_city cities
    　　 for step=1 to run  city
     　　   for k=1 to run ant
      　　     Choose the next city to move to applying
       　　    a probabilistic state transition rule
    　　    end for
   　　  end for
 　　 Up date pheromone trails
　　Until End_condition

　　五、結論與心得
　　這次演算法的期末專題，我選擇『螞蟻演算法』作為題目，了解了這個演算法的名字的由來、它是如何執行、它可以解決哪些問題，等…讓我對演算法這門課也多了解一點，雖然這學期以來，在小考以及作業部分大家還是互相cover的機會比較多。等到過了這學期之後，至少大家也都有了trace程式碼、解決問題的能力。我們也知道，演算法課程學到的許多方法，不僅僅只是應用在程式方面，現實生活中也可以利用演算法來幫你解決問題。
　　這份報告真的事千呼萬喚始出來，其實我在前一天就已經把這份報告完成的差不多了，只剩後面一點點的心得跟程式碼的部分，經過兩小時我完成之後，我開開心新的整理桌面，刪除我的參考資料，我不曉得是眼花還是手殘，我竟然把我的成品直接用shift + delete刪掉了，我又花了很長的時間去找拯救檔案的軟體來試，final data和Drive Rescue不過竟然只找的到我的暫存檔，十分的不甘願下，我只好重做一份了。所以我對螞蟻演算法真的是有很深的體驗啊！

　　六、參考資料
　　http://eca2.mis.au.edu.tw/check/paper/GA3/GA3_5.doc
　　http://en.wikipedia.org/wiki/Ant_colony_optimization
　　http://iridia.ulb.ac.be/~mdorigo/ACO/about.html
　　螞蟻演算法.pdf
　　好用的google & yahoo知識+

"

"前言:    這次演算法Term Project,我選擇了螞蟻演算法.然而,我之所以選擇它,理由有三: 其一,是因為老師在課程上不會教到,符合老師的要求; 其二,是因為網路上關於螞蟻演算法的資料相當豐富.爾後,在查找資料時,會比較便利;其三,是因為我對螞蟻與演算法之間到底有什麼關聯有極大的好奇心.引發我有一股想專研它的衝勁.綜合以上所述,驅使我一頭栽進了螞蟻與演算法的交界地帶.    雖然,這學期在時間上可能沒那麼充裕,但我仍想盡我所能,努力去完成這次的Term Project,讓自己能夠從中汲取更多的知識,甚至希望藉由這次的機會,讓我對演算法有更深成的了解,而進一步去創造一個新的且比螞蟻演算法更優良的改版演算法.[@more@]緣起與原理:    螞蟻演算法最早是由一位博士M. Dorigo 在他的論文中所提出,u, 也稱為Ant Algorithms Ant Colony System (ACS),其理念是來自於螞 蟻的行為與習性.螞蟻在覓食時,會在尋找食物的路途中留下一種稱為 費洛蒙(Pheromone)之賀爾蒙,然而長時間之後,只要是留下很多費洛蒙 的路徑上,就吸引越多螞蟻走過.因此,當螞蟻遇到兩條以上路途時, 螞 蟻們都爭相往費洛蒙較多的路途.而費洛蒙越多的路途總是最短路徑. 經由這行為,導出了一個關係:螞蟻行徑某一路程的機率跟費洛蒙的多 寡成正比,且這路途通常是最短的.由此可知,螞蟻演算法主要是在模仿螞蟻的行為,以進一步去求得最佳解.

應用:

     螞蟻演算法可應用在最短路徑、旅行推銷員問題( TSP )、生產 排程、水庫最低水位...等最佳化問題上，以求得各問題之最佳解為目 標。 分析:舉TSP為例.TSP定義:一位銷售旅行員,從任一城市出發,拜訪需要的N個城市各一次後,又回到起始出發城市.其目標是求得最短拜訪路徑為何.ACS的Pseudo-code:for(each path from city i to city j)//初始化費洛蒙數量{τij= C;}do{for(each ant ){            place this ant on an arbitrary starting node;            do(for each move)

            {

                   the ant applies state transition rule to choose next node;                //決定第k隻螞蟻從node i移至node j的機率值            }while(this ant hasn’t built a complete tour);}A global pheromone updating rule is applied;//當螞蟻走到終點時,將各路徑的費洛蒙濃度最更新}while(a maximal number of cycles isn’t reached);               解決TSP之N個城市演進表:Year       Research Team              Size of Instance  Name 1954  G. Dantzig, R. Fulkerson, and S. Johnson   49 cities   dantzig42 1971  M. Held and R.M. Karp                64 cities   64 random points 1975  P.M. Camerini, L. Fratta, and F. Maffioli   67 cities   67 random points 1977  M. Grötschel                         120 cities   gr120 1980  H. Crowder and M.W. Padberg           318 cities   lin318 1987  M. Padberg and G. Rinaldi               532 cities  att532 1987  M. Grötschel and O. Holland             666 cities  gr666 1987  M. Padberg and G. Rinaldi               2,392 cities  pr2392 1994  D. Applegate, R. Bixby, V. Chvátal, and W. Cook  7,397 cities  pla7397 1998  D. Applegate, R. Bixby, V. Chvátal, and W. Cook  13,509 cities  usa13509 2001  D. Applegate, R. Bixby, V. Chvátal, and W. Cook   15,112 cities  d15112 2004  D. Applegate, R. Bixby, V. Chvátal, W. Cook, and K. Helsgaun 24,978 cities sw24798註：資料來源：http://www.tsp.gatech.edu//history/milestone.html     根據上表我們可知目前最多只能解決24798個城市數量的TSP.因此,我們應該瞭解到TSP其實不是個容易解的問題,然而,事實上它已被證實是屬於NP-Complete的問題,所以我們不難理解為什麼表格所呈現的數據,成長速度不快了吧！結語：     螞蟻演算法在求解效果上其實已有滿不錯的成效,可是我在查詢資料過程中能發現有許多專家學者在研究如何改良螞蟻演算法,使其更加完善.由此,我想他們其實都跟我一樣,想突破目前可解最大的城市數和些限制條件等,以達到更大的求解效率.雖然這次project不像一些學者有著深闢的見解與實際的模擬演練,但我依然認為,做完project後,收穫仍是有的,只是沒有我他們專家學者來的大,畢竟我跟他們之間的level還是有很大的差距,不是我一蹴可及的.總而言之,透過這次作業,我又瞭解到一個新的Algorithm：ACS.參考資料來源：http://www.orstw.org.tw/Conference2004/C/154.pdfhttp://www.tsp.gatech.edu//index.htmlhttp://mail.im.tku.edu.tw/~duck.yu/Paper/%A4w%BF%C2%C3%C6%B8s%BBE%B3%CC%A8%CE%A4%C6%BE%E3%A6X%BE%B8%AD%B5%C2Z%B0%CA%AAk%A8D%B8%D1TSP%B0%DD%C3D.pdf

"1.前言:    相傳數獨源起於拉丁方陣(Latin Square),1970代在美國發展，改名為數字拼圖(Number Place)、之後流傳至日本並發揚光大，以數學智力遊戲智力拼圖遊戲發表。在1984年一本遊戲雜誌正式把它命名為數獨，意思是在每一格只有一個數字。後來一位前任香港高等法院的紐西蘭籍法官高樂德（Wayne Gould）在1997年3月到日本東京旅遊時，無意中發現了。他首先在英國的某報紙上發表，不久其他報紙也發表，很快便風靡全英國，之後他用了6年時間編寫了電腦程式，並將它放在網站上，使這個遊戲很快在全世界流行。[@more@]2.簡述:    在9×9的大九宮格中有9個3×3的小九宮格，已經有一些數字在裡面了(但也不一定採用數字，例如採用字母a,b,c...)，根據這些數字，運用邏輯和推理,在其他的空格上填入1到9的數字，但每個數字在每個小九宮格內不能重複，每個數字在大九宮格的每行、每列也不能出現一樣的數字。這種遊戲只需要邏輯思維能力，與數字運算無關。雖然玩法簡單，但數字排列方式卻千變萬化，是個可讓人動動腦筋的小遊戲　　 3.數獨的組合:    利用暴力法和一些邏輯可以計算出數獨的組合，一共有9! × 72 ² × 2⁷ ×27,704,267,971=66,7090,3752,0210,7293,6960總組合但若不包含重複，那只剩下5,472,730,538個組合。 ４.數獨的解題方法：　　數獨的解題方法又分為三種：　１.直觀式:

      1基礎屏除法

          此方法是最簡易的方法，如果使用此方法夠仔細時，幾乎一 般的數獨題都可以解出來。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　尋找宮屏餘解：找到某數再某個九宮格可填入的位置只剩一個數可填的情形，意即找到了該數在九宮格的填入位置。　　尋找列摒餘解：找到某數再某列可填入的位置只剩一個數可填的情形，意即找到了該數在該列的填入位置。　　尋找行摒餘解：找到某數再某行可填入的位置只剩一個數可填的情形，意即找到了該數在該行的填入位置。

　 2唯一解法

        當數獨謎題中的某宮個因為所楚的列、行或九宮格已填入數字到達８個時，所以最後可填入的數字，就只剩下還沒出現過的數字。

       3唯餘解法  

　　當數獨中的某一個宮格，因所處的列、行及九宮格中，合計已出現過不同的８個數字，使得這個宮格所能填入的數字，只剩下還沒出現過的數字時，稱此宮格有唯餘解。   2 .候選法:

      1唯一候選數法

　　如果在候選數表中發現某一個宮格的候選數僅有 1 個數字，那就是表示：不必再考慮了！這個宮格就是 只能填入這個數字啦！如果填入別的數字，就會違反數獨的填製規則的。找出候選數表中，候選數僅有 1 個數字的宮格來，並填入該候選數。

      2 區塊刪減法

　　當某個數字只出現在某行或者某列的某一區塊候選數中時，就可把該數字從包含該區塊的九宮格之其他區塊候選數中刪減掉。當某個數字只出現在某個九宮格的某個區塊候選數中時，就以把該數字從包含該區塊的行或列之其他區塊候選數中刪減掉。找出某行、某列或某個九宮格各個區塊候選數中只出現一次的數字來，並將該數字自包含該區塊的另一個行、列或九宮格的其他區塊候選數中刪減掉。

       3數對刪減法

　　找出某行、某列或某個九宮格各個區塊候選數中只出現一次的數字來，並將該數字自包含該區塊的另一個行、列或九宮格的　　　　　　其他區塊候選數中刪減掉。

　  4 隱性數對刪減法

　　找出某個數對僅出現在某行、某列或某個九宮格的某兩個宮格候選數中的情形，進而將這兩個宮格的候選數刪減成該數對。

       5三鏈數刪減法

　　找出某列、某行或某個九宮格中的某三個宮格候選數中，相異的數字不超過３個的情形，進而將這３個數字自其他宮格的候選數中刪減掉。

       6矩形頂點刪減法

　　找出某個數字在某兩列僅出現在相同兩行的情形，進而將該數字自這兩行其他宮格候選數中刪減掉，或者找出某個數字在某兩行僅出現在相同兩列的情形，進而將該數字自這兩列其他宮格候選數中刪減掉。

       7三鏈列刪減法

　　找出某個數字在某三列僅出現在相同三行的情形，進而將該數字自這三行其他宮格候選數中刪減掉，或者找出某個數字在某三行僅出現在相同三列的情形，進而將該數字自這三列其他宮格候選數中刪減掉。

       8關鍵數刪減法

　　以關鍵數的關係找出矛盾的組合，或者找出確切可進行刪減的宮格，進而將該數字自宮格候選數中刪減掉。   三.暴力法:   寫出一個可填入9*9方格所有數字組合的程式,再對兆原來題目,自然會有個解是正確的。 ５.結論:     數獨在這幾年才真正的流行起來，之所以可以在短時間內造成一股風潮，就在於他強調了人性化及樂趣化，每個數獨題都可用簡單的邏輯、推理的方式來解決。不好的數獨題會是不只一個解的，因此必定會讓我們用到猜測或帶入等不是邏輯的方法，相對的一個好的數獨題只有一個解才是好的。希望藉由這些介紹能夠讓對於數獨的人更加了解數獨！   參考資料：http://zh.wikipedia.org/w/index.php?title=%E6%95%B8%E7%8D%A8&variant=zh-twhttp://cmusic.idv.tw/suona/forum/topic.asp?TOPIC_ID=8544http://paulsin.blogspot.com/2005/11/sudoku.html  "

"

        文件在現代中無所不在，它們用來傳遞並發布訊息。從演算法設計的角度來看，這類的文件可視為簡單的字串。也就是說，它們可以抽象地看成一連串構成內容的字元。因此，要在這類資料上進行有趣的搜尋與處理，我們需要有效率的發法來處理字串。

         字串搜尋本身不難，使用暴力法也可以求解，但如何快速搜尋字串就不簡單了，傳統的字串搜尋是從關鍵字與字串的開頭開始比對。

[@more@]

Boyer-Moore 演算法

Boyer-Moore字串核對關鍵字的後面開始核對字串，並製作前進表，如果比對不符合則依前進表中的值前進至下一個核對處，假設是p好了，然後比對字串中p-n+1至p的值是否與關鍵字相同。

那麼前進表該如何前進，舉個實際的例子，如果要在字串中搜尋JUST這個字串，則可能遇到的幾個情況如下所示：

依照這個例子，可以決定出我們的前進值表如下：

如果關鍵字中有重複出現的字元，則前進值就會有兩個以上的值，此時則取前進值較小的值，如此就不會跳過可能的位置，例如texture這個關鍵字，t的前 進值應該取後面的3而不是取前面的7。

 我們將last(c)定義如下：

如果P包含c，則last(c)就是c出現在P之中最後一個位置(最右方)的索引值。否則，我們直接定義last(c) = -1。

 Algorithm BMMatch(T,P)：   Input：Strings T (text) with n characters and P (pattern) with m characters   Output︰Strings index of the first substring of T matching P , or an indication that P is not a substring of T

   compute function last

   i ← m-1   j ← m-1   repeat      if P[j] = T[i] then         if j = 0 then            return i                   //a match!         else            i ← i-1            j ← j-1      else         i ← i+m-min( j,1+last(T[i]) )                        //jump step         j ← m-1   until i ﹥n-1   return “There is no substring of T matching P.” 

Knuth-Morris-Pratt 演算法

KMP演算法是拿來處理字串是否相符。換句話說，給你兩個字串，你需要回答，B字串是否是A字串的子字串（A字串是否包含B字串）。比如，字串A="I'm matrix67"，字串B="matrix"，我們就說B是A的子字串。  解決這類問題，通常我們的方法是枚舉從A字串的什麼位置起開始與B字串比對，然後驗證是否相符。假如A字串長度為n，B字串長度為m，那麼這種方法的複雜度是O (mn)。雖然很多時候複雜度達不到mn（驗證時只看頭一兩個字母就發現不相符了），但我們有許多「最壞情況」，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我們將介紹的是一種最壞情況下O(n)的算法（這裡假設 m<=n），即KMP演算法之所以叫做KMP，是因為這個算法是由Knuth、Morris、Pratt三個提出來的，取了這三個人的名字的頭一個字母.假如，A="abababaababacb"，B="ababacb"。我們用i和j分別表示，A[i-j+ 1..i]與B[1..j]完全相等。也就是說，i是不斷增加的，隨著i的增加j相應地變化，且j滿足以A[i]結尾的長度為j的字串正好相對於B字串的前 j個字元（j當然越大越好），現在需要檢驗A[i+1]和B[j+1]的關係。當A[i+1]=B[j+1]時，i和j各加一；什麼時候j=m了，我們就說B是A的子字串，並且可以根據這時的i值算出相對的位置。當A[i+1]≠B[j+1]，KMP的策略是調整j的位置 （減小j值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配（從而使得i和j能繼續增加）。我們看一看當 i=j=5時的情況。

       i = 1 2 3 4 5 6 7 8 9 ……
       A = a b a b a b a a b a b …
       B = a b a b a c b
       j = 1 2 3 4 5 6 7       此時，A[6]≠B[6]。這表明，此時j不能等於5了，我們要把j改成比它小的值j'。j'可能是多少呢？仔細想一下，我們發現，j'必須要使得B[1..j]中的頭j'個字母和末j'個字母完全相等（這樣j變成了j'後才能繼續保持i和j的性質）。這個j'當然要越大越好。在這裡，B [1..5]="ababa"，頭3個字母和末3個字母都是"aba"。而當新的j為3時，A[6]恰好和B[4]相等。於是，i變成了6，而j則變成了 4：

       i = 1 2 3 4 5 6 7 8 9 ……
       A = a b a b a b a a b a b …
       B =           a b a b a c b
       j =           1 2 3 4 5 6 7        從上面的這個例子，我們可以看到，新的j可以取多少與i無關，只與B字串有關。我們完全可以預處理出這樣一個數組P[j]，表示當匹配到B數組的第j個字母而第j+1個字母不能匹配了時，新的j最大是多少。P[j]應該是所有B[1..P[j]]=B[j-P[j]+1..j]的最大值。再後來，A[7]=B[5]，i和j又各增加1。這時，又出現了A[i+1]≠B[j+1]的情況：       i = 1 2 3 4 5 6 7 8 9 ……       A = a b a b a b a a b a b …       B =           a b a b a c b       j =           1 2 3 4 5 6 7      由於P[5]=3，因此新的j=3：        i = 1 2 3 4 5 6 7 8 9 ……       A = a b a b a b a a b a b …       B =                  a b a b a c b       j =                  1 2 3 4 5 6 7      這時，新的j=3仍然不能滿足A[i+1]=B[j+1]，此時我們再次減小j值，將j再次更新為P[3]：        i = 1 2 3 4 5 6 7 8 9 ……       A = a b a b a b a a b a b …       B =                   a b a b a c b       j =                    1 2 3 4 5 6 7       現在，i還是7，j已經變成1了。而此時A[8]居然仍然不等於B[j+1]。這樣，j必須減小到B[1]，即0：        i = 1 2 3 4 5 6 7 8 9 ……
       A = a b a b a b a a b a b …
       B =                            a b a b a c b
       j =                     0 1 2 3 4 5 6 7       終於，A[8]=B[1]，i變為8，j為1。事實上，有可能j到了0仍然不能滿足A[i+1]=B[j+1]（比如A[8]="d"時）。因此，準確的說法是，當j=0了時，我們增加i值但忽略j直到出現A[i]=B[1]為止。      這個過程的代碼，我們在這裡列出：程式代碼j:=0;
for i:=1 to n do
begin
      while (j>0) and (B[j+1]≠A[i]) do j:=P[j];
      if B[j+1]=A[i] then j:=j+1;
      if j=m then
      begin
         writeln('Pattern occurs with shift ',i-m);
         j:=B[j];
      end;
end;
最後的j:=P[j]是為了讓程式繼續做下去，因為我們有可能找到多處相符。    這個程式或許比想像中的要簡單，因為對於i值的不斷增加，程式碼用的是for迴圈。因此，這個程式虛擬碼可以這樣形象地理解：掃瞄字串A，並更新可以相對到B的什麼位置。       為什麼這個程式是O(n)的？其實，主要的爭議在於，while迴圈使得執行次數出現了不確定因素。我們將用到時間複雜度的攤還分析中的主要策略，簡單地說就是通過觀察某一個變量或函數值的變化來對零散的、雜亂的、不規則的執行次數進行累計。KMP的時間複雜度分析可謂攤還分析的典型。 我們從上述程式的j值入手。每一次執行while迴圈都會使j減小（但不能減成負的），而另外的改變j值的地方只有第五行。每次執行了這一行，j都只能加1；因此，整個過程中j最多加了n個1。於是，j最多只有n次減小的機會（j值減小的次數當然不能超過n，因為j永遠是非負整數）。這告訴我們，while迴圈總共最多執行 了n次。按照攤還分析的說法，平攤到每次for迴圈中後，一次for迴圈的複雜度為O(1)。整個過程顯然是O(n)的。這樣的分析對於後面P數組預備處理的過程同樣有效，同樣可以得到預處理過程的複雜度為O(m)。      預備處理不需要按照P的定義寫成O(m^2)甚至O(m^3)的。 我們可以P[1],P[2],...,P[j-1]的值來獲得P[j]的值。對於剛才的B="ababacb"，假如我們已經求出了P[1],P[2],P[3]和P[4]，我們應該怎麼求出P[5]和P[6]？P[4]=2，那麼P [5]顯然等於P[4]+1，因為由P[4]可以知道，B[1,2]已經和B[3,4]相等了，現在又有B[3]=B[5]，所以P[5]可以由P[4] 後面加一個字元得到。P[6]也等於P[5]+1嗎？顯然不是，因為B[ P[5]+1 ]≠B[6]。那麼，我們要考慮「退一步」了。我們考慮P[6]是否有可能由P[5]的情況所包含的子字串得到，即是否P[6]=P[ P[5] ]+1。下面為簡易說明：               1 2 3 4 5 6 7
       B = a b a b a c b
       P = 0 0 1 2 3 ?       P[5]=3是因為B[1..3]和B[3...5]都是"aba"；而P[3]=1則告訴我們，B[1]和B[5]都是"a"。既然P[6]不能由P[5]得到，或許可以由P[3]得到（如果B[2]恰好和B[6]相等的話，P[6]就等於P[3]+1了）。顯然，P[6]也不能通過P[3]得到，因為B[2]≠B[6]。事實上，這樣一直推到P[1]也不行，最後，我們得到，P[6]=0。      怎麼這個預先處理過程跟前面的KMP主程式這麼像呢？其實，KMP的預先處理本身就是一個B字串「自我配對」的過程。  它的代碼和上面的代碼神似：程式代碼P[1]:=0;
j:=0;
for i:=2 to m do
begin
      while (j>0) and (B[j+1] ≠B[i]) do j:=P[j];
      if B[j+1]=B[i] then j:=j+1;
      P[i]:=j;
end;       最後補充一點：由於KMP算法只預先處理B字串，因此這種算法很適合這樣的問題：給定一個B字串和一群不同的A字串，問B是哪些A字串的子字串。"

"1. 前言 為什麼會選擇黑白棋做我的專題呢?恩…因為這是好玩的遊戲阿XD 中間有一度想換個主題，後來想想算了，還是繼續做好了XD 也有懷疑了一下這個主題到底跟演算法有沒有關係…不過遊戲的的電腦AI應該都跟演算法有相當程度的關係吧，畢竟演算法就是要解決問題的阿，對一個遊戲來說解決問題就是要獲勝阿XD 2. 黑白棋簡介 黑白棋，又叫翻轉棋、蘋果棋或奧賽羅棋（Othello）。 3. 命名 一般棋子雙面為黑白兩色，故稱「黑白棋」。因為行棋之時將對方棋子翻轉， 變為己方棋子，故又稱「翻轉棋」。棋子雙面為紅、綠色的稱為「蘋果棋」。 4. 黑白棋(othello)遊戲是由二個玩家下棋，一方各執特定顏色的棋子，而最終勝負的認定則是視何種顏色棋子較多，多的一方為勝者，而其簡要的規則如下： 1.棋局最初時，雙方各持兩子，至於棋盤中心的對角線上。 2.雙方輪流下，只有當無合法位置可下時，才可 pass，將下子權交給對方。 3.雙方皆無合法位址可下時，則結束比賽。 4.合法位置的定義為下子後能吃掉對方一子以上的所有空白位置。 5.吃子的規則為：所有被新下棋子與己方棋子在縱、橫、對角等方向所包圍的敵方棋子，皆會被我方吃掉。吃子後，對方的棋子變成已方之顏色，即變成已方所有。 5. 開局(Opennings) 棋局最初階段，約為開始的二十步，白棋在第一步開始時可選的三種開步方式。 (見對角開局、平衡開局、及垂直開局 ) 開局的方法共有三種，視乎白棋採取何等策略應付黑棋的開步方法(黑棋向四邊開步永遠是一樣的)。在以下的例子中，黑棋的開步方法遠是 c4；若黑棋採用其他的開步方法，黑白兩棋接著也會走出對應的步法。 對角開局(Diagonal Opennings) 是一種開局方式，當黑棋第一步走到 c4 時，白棋接著走 c3 在一般的情況下，接著的會是 d3c5 或 e6c5。 平衡開局(Parallel Opennings) 一種開局的方式，當黑棋開步走到 c4 時，白棋接著走 c5 一般來說，接著的會是 d6e3 或 c6e3。 垂直開局(Perpendicular Opennings) 一種開局方式，當黑棋開步走到 c4時，白棋接著走到 e3 在一般的情況下，接著的幾步為 f6f5 或 f5e6 或 f4c5。 6. 黑白棋的由來 Reversi是由英國人再19世紀末發明的一個棋版遊戲，當時由於兩位英國人--John W. Mollet及Lewis Waterman，都爭著做這個遊戲的名人，這個爭拗卻使這個棋版遊戲流行起來。 到了1971年，日本人Goro Hasegawa 以Reversi為藍本再加上一些新的棋力，並借用莎士比亞寺大悲劇之一""Othello""位這個遊戲重新命名及註冊，就變成今時今日的黑白棋了。 Othello 是莎士比亞同名小說的男主角。他是一個黑人，妻子是個白人，因受小人挑撥離間，懷疑妻子不忠以致情海翻波，最後把妻子殺死。但其後真相大白，Othello懊悔不已，自殺而死。黑白棋就是借用這個黑人白人鬥爭的故事來命名，頗有文化氣息。 7. 黑白棋使用之相關演算法 遊戲樹演算法 搜尋遊戲樹（min-max search tree）的原理，取自於我們平常玩競爭性遊戲的想法，以下我們就舉大家熟悉的棋類為例子：當我們要下棋時，總會考慮到對手可能對已方的傷害，而我們也因 此必須選擇對已方最有利的下一步，也就是對已方傷害最少的下一步，不知不覺得已經講出遊戲樹的基本精神，在最大層就好比是對手的選擇，他總是選擇對已方最 不利的下一步，而在最小層就好比是已方的選擇，選擇對已方傷害最少的下一步。 Alpha-Beta Pruning 目的: 減少搜尋樹的所必須經過的節點數，即刪除部分分枝， 而被刪除的節點，代表此一節點對結果沒有影響 特徵擷取 以下舉出黑白棋可能的特徵 a. 每一棋盤上位置的重要性質，如四個角落的重要性較高,左圖即為每個位置的參考權值。 b. 我方目前子數與對方子數的差。 c. 我方可下之子數。 d. 對方可下之子數。 e. 穩定度。 f. 移動性。 g. 對手的穩定度。 演化的運算子非常多，但是大部分都是取自於大自然的現像，以下只舉出二個常見的例子 染色體運算 染色體交配 : 即兩個染色體之間的某些基因互換，讓染色體之間 有機會能學到別人的長處。染色體突變 : 染色體中的某些基因值自主的改變，主要 用來產生異於一般情況的染色體，以免讓學習的結果落入區域最小值中。 演化流程 此一演化環境，一開始隨機產生一些染色體， 以形成一群體，接著評估每一染色體的適存度， 適合生存的染色體，可複製本身，接下來就是 進行染色體之間的交配，及染色體本身的突變， 當此一動作完成之後，也就形成了新的子代。 依此原則，不斷的重複此一演化法則，而最終 就產生了最適合生存的世代。 8. 下棋技巧 我平常就只是偶爾跟電腦玩而已，也沒有特別的專研，不過根據遊戲的規則來看 2.圍住對方連續的棋子兩端時，被圍住的棋子會翻轉成我方棋子(直橫斜向均可)。 整個棋盤唯一不會被兩面圍的點是哪裡?就在四個角落，所以我下棋的步驟就是引誘電腦在角落的四周下棋，然後再想盡辦法拿下角落!!! 黑白棋要贏很簡單，佔滿角落四周就不會輸了，不過也是有看過神人可以把整個白子吃光讓他提早結束的(驚!!) (開局時，上面先放好兩黑兩白旗子) (和電腦下到一半的畫面) (險勝…我果然只是純玩玩而已…) 在上面這個圖的網站上有找到部分的黑白棋演算法程式，不過因為未跟作者告知，所以不便貿然取用。 參考資料: 1. http://nadiainochi.myweb.hinet.net/othello/index.htm 2. http://www.disco.com.hk/ 3. http://www.33wg.com/33wg/read.php?tid=552075 4. http://zh.wikipedia.org/wiki/%E9%BB%91%E7%99%BD%E6%A3%8B 5. http://delphi.ktop.com.tw/board.php?cid=169&fid=963&tid=20684[@more@]"

"1. 前言 為什麼會選擇黑白棋做我的專題呢?恩…因為這是好玩的遊戲阿XD 中間有一度想換個主題，後來想想算了，還是繼續做好了XD 也有懷疑了一下這個主題到底跟演算法有沒有關係…不過遊戲的的電腦AI應該都跟演算法有相當程度的關係吧，畢竟演算法就是要解決問題的阿，對一個遊戲來說解決問題就是要獲勝阿XD 2. 黑白棋簡介 黑白棋，又叫翻轉棋、蘋果棋或奧賽羅棋（Othello）。 3. 命名 一般棋子雙面為黑白兩色，故稱「黑白棋」。因為行棋之時將對方棋子翻轉， 變為己方棋子，故又稱「翻轉棋」。棋子雙面為紅、綠色的稱為「蘋果棋」。 4. 黑白棋(othello)遊戲是由二個玩家下棋，一方各執特定顏色的棋子，而最終勝負的認定則是視何種顏色棋子較多，多的一方為勝者，而其簡要的規則如下： 1.棋局最初時，雙方各持兩子，至於棋盤中心的對角線上。 2.雙方輪流下，只有當無合法位置可下時，才可 pass，將下子權交給對方。 3.雙方皆無合法位址可下時，則結束比賽。 4.合法位置的定義為下子後能吃掉對方一子以上的所有空白位置。 5.吃子的規則為：所有被新下棋子與己方棋子在縱、橫、對角等方向所包圍的敵方棋子，皆會被我方吃掉。吃子後，對方的棋子變成已方之顏色，即變成已方所有。 5. 開局(Opennings) 棋局最初階段，約為開始的二十步，白棋在第一步開始時可選的三種開步方式。 (見對角開局、平衡開局、及垂直開局 ) 開局的方法共有三種，視乎白棋採取何等策略應付黑棋的開步方法(黑棋向四邊開步永遠是一樣的)。在以下的例子中，黑棋的開步方法遠是 c4；若黑棋採用其他的開步方法，黑白兩棋接著也會走出對應的步法。 對角開局(Diagonal Opennings) 是一種開局方式，當黑棋第一步走到 c4 時，白棋接著走 c3 在一般的情況下，接著的會是 d3c5 或 e6c5。 平衡開局(Parallel Opennings) 一種開局的方式，當黑棋開步走到 c4 時，白棋接著走 c5 一般來說，接著的會是 d6e3 或 c6e3。 垂直開局(Perpendicular Opennings) 一種開局方式，當黑棋開步走到 c4時，白棋接著走到 e3 在一般的情況下，接著的幾步為 f6f5 或 f5e6 或 f4c5。 6. 黑白棋的由來 Reversi是由英國人再19世紀末發明的一個棋版遊戲，當時由於兩位英國人--John W. Mollet及Lewis Waterman，都爭著做這個遊戲的名人，這個爭拗卻使這個棋版遊戲流行起來。 到了1971年，日本人Goro Hasegawa 以Reversi為藍本再加上一些新的棋力，並借用莎士比亞寺大悲劇之一""Othello""位這個遊戲重新命名及註冊，就變成今時今日的黑白棋了。 Othello 是莎士比亞同名小說的男主角。他是一個黑人，妻子是個白人，因受小人挑撥離間，懷疑妻子不忠以致情海翻波，最後把妻子殺死。但其後真相大白，Othello懊悔不已，自殺而死。黑白棋就是借用這個黑人白人鬥爭的故事來命名，頗有文化氣息。 7. 黑白棋使用之相關演算法 遊戲樹演算法 搜尋遊戲樹（min-max search tree）的原理，取自於我們平常玩競爭性遊戲的想法，以下我們就舉大家熟悉的棋類為例子：當我們要下棋時，總會考慮到對手可能對已方的傷害，而我們也因 此必須選擇對已方最有利的下一步，也就是對已方傷害最少的下一步，不知不覺得已經講出遊戲樹的基本精神，在最大層就好比是對手的選擇，他總是選擇對已方最 不利的下一步，而在最小層就好比是已方的選擇，選擇對已方傷害最少的下一步。 Alpha-Beta Pruning 目的: 減少搜尋樹的所必須經過的節點數，即刪除部分分枝， 而被刪除的節點，代表此一節點對結果沒有影響 特徵擷取 以下舉出黑白棋可能的特徵 a. 每一棋盤上位置的重要性質，如四個角落的重要性較高,左圖即為每個位置的參考權值。 b. 我方目前子數與對方子數的差。 c. 我方可下之子數。 d. 對方可下之子數。 e. 穩定度。 f. 移動性。 g. 對手的穩定度。 演化的運算子非常多，但是大部分都是取自於大自然的現像，以下只舉出二個常見的例子 染色體運算 染色體交配 : 即兩個染色體之間的某些基因互換，讓染色體之間 有機會能學到別人的長處。染色體突變 : 染色體中的某些基因值自主的改變，主要 用來產生異於一般情況的染色體，以免讓學習的結果落入區域最小值中。 演化流程 此一演化環境，一開始隨機產生一些染色體， 以形成一群體，接著評估每一染色體的適存度， 適合生存的染色體，可複製本身，接下來就是 進行染色體之間的交配，及染色體本身的突變， 當此一動作完成之後，也就形成了新的子代。 依此原則，不斷的重複此一演化法則，而最終 就產生了最適合生存的世代。 8. 下棋技巧 我平常就只是偶爾跟電腦玩而已，也沒有特別的專研，不過根據遊戲的規則來看 2.圍住對方連續的棋子兩端時，被圍住的棋子會翻轉成我方棋子(直橫斜向均可)。 整個棋盤唯一不會被兩面圍的點是哪裡?就在四個角落，所以我下棋的步驟就是引誘電腦在角落的四周下棋，然後再想盡辦法拿下角落!!! 黑白棋要贏很簡單，佔滿角落四周就不會輸了，不過也是有看過神人可以把整個白子吃光讓他提早結束的(驚!!) (開局時，上面先放好兩黑兩白旗子) (和電腦下到一半的畫面) (險勝…我果然只是純玩玩而已…) 在上面這個圖的網站上有找到部分的黑白棋演算法程式，不過因為未跟作者告知，所以不便貿然取用。 參考資料: 1. http://nadiainochi.myweb.hinet.net/othello/index.htm 2. http://www.disco.com.hk/ 3. http://www.33wg.com/33wg/read.php?tid=552075 4. http://zh.wikipedia.org/wiki/%E9%BB%91%E7%99%BD%E6%A3%8B 5. http://delphi.ktop.com.tw/board.php?cid=169&fid=963&tid=20684[@more@]"

"Algorithm Project for convex hull[@more@]

資工二甲 494511689

賴家偉

什麼是convex hull? 中文翻成 “凸包”基本上，翻的非常爛，從字面上還是不知道是啥

但在這之前我們先來了解凸多邊型的定義:

凸多邊型，直觀的來說，就是不凹，沒有凹的部份。像 凹 、凸這兩個字都不算凸多邊型。 而像正方形長方形三角形這種形狀就是凸多邊型。可是上述這一定義很不嚴密，究竟何謂「凹陷位」？實在難以說清楚。因此在數學上，凸多邊形有另一個嚴格 的定義。假設我們在一個多邊形上(包括多邊形的邊界及邊界圍封的範圍)任意取兩點並以一條線段連結該兩點 ，如果線段上的每一點均在該多邊形上，那麼我們便說這個多邊形是凸的。根據以上定義，我們便可判斷「凸 」字形的確不是凸的。例如，在下圖中，連結A、B兩點的線段有一部分並不在該多邊形上。

而以下是wiki對convex hull 的定義

在一個實數向量空間V中，對於給定集合X，所有包含X的凸集的交集S被稱為X的凸包。

X的凸包可以用X內所有點 的線性組合來構造。

在二維歐幾裡得空間中，凸包可想像為一條剛好包著所有點的橡皮圈。

乍看之下，似乎很複雜，但簡單來說，就是給妳ㄧ堆點，然後將連起來是最大面積的點找出來，也就是最外面的點。

What is the convex hull of a set of points? 以下的兩點說明

• Formally: It is the smallest convex set containing the points.
• Informally: It is a rubber band wrapped around the "outside" points.

而常見用來找出convex hull的演算法有下列五種

1.      Incremental

The incremental algorithm is an algorithm for computing the convex hull of a set of points in two or more dimensions.

The basic idea is to add points one at a time updating the hull as we proceed.

 If the new point (shown in red) is inside the hull there is nothing to do. Otherwise, we must delete all the edges (shown in yellow) that the new point can see.

Add two edges to connect the new point to the remainder of the old hull

Repeat for the next point outside the hull.

2.      Gift wrap(Jarvis' march)

此演算法或許是對於解決convex hull來說最簡單的一種演算法, 而且在某些情況中它可以非常的快。它的基本概念如下：

• Start at some extreme point, which is guaranteed to be on the hull.
• At each step, test each of the points, and find the one which makes the largest right-hand turn. That point has to be the next one on the hull.

Because this process marches around the hull in counter-clockwise order, like a ribbon wrapping itself around the points, this algorithm also called the "gift-wrapping" algorithm.

當用程式來跑的話，若點為30個，且是亂數的話，需要run 247次。 就像我們看到的。並不快 quick hull快多了。

事實上 若 有N個點排成圓形的話Jarvis' march 花的次數則會是N^2 次數

If you think about it, Jarvis' march takes time proportional to nh, where n is the number of input points, and h is the number of points on the hull. In other words, Jarvis' march is output-sensitive. The algorithm works best such as the following, where h is 3:

則只需要run 85次

3. Graham's Scan

Given a set of points on the plane, Graham's scan 可以算出它們 convex hull.

這個演算法主要為列三個步驟

1. Find an extreme point. This point will be the pivot, is guaranteed to be on the hull, and is chosen to be the point with largest y coordinate.

2. Sort the points in order of increasing angle about the pivot. We end up with a star-shaped polygon (one in which one special point, in this case the pivot, can "see" the whole polygon).

3. Build the hull, by marching around the star-shaped poly, adding edges when we make a left turn, and back-tracking when we make a right turn.

而此演算法剛好跟第4個quick hull相反 在點是整齊排列時速度較快，而在點是亂數排列是較慢

用程式來跑的話，若點為50個，且是亂數的話，需要run201次。

若50個點排成圓形的話，則只需要run117次即可執行完畢

4.      Quick hull

就如他的名字， Quick 。它是一種很快地方法用來計算convex hull的演算法當有一群點集合在圖上時。I基本上它跟 quick-sort:  有許多類似之處。

以下的四個步驟為它的過程基本概念。

1. We are given a some points, and line segment AB which we know is a chord of the convex hull (IE, it's endpoints are known to be on the convex hull). A good chord to start the algorithm goes from the leftmost to the rightmost point in the set.
2. Among the given points, find the one which is farthest from AB. Let's call this point C.
3. The points inside the triangle ABC cannot be on the hull. Put them in set s0.
4. Put the points which lie outside edge AC in set s1, and points outside edge BC in set s2.

當partition做完了以後我們可以迴歸到s1 s2 這個演算法在當點是亂數排列的時是最快速的 但當點是很整齊的排列是就較差because step 3 of the partition typically discards a large fraction of the points.

用程式來跑的話，若點為50個，且是亂數的話，只需要run 124次。

若50個點排成圓形的話，則需要run318次!

剛好跟第3個成對比。

1. Divide and Conquer

Divide the points into two equal sized sets L and R such that all points of L are to the left of the most leftmost points in R.

Recursively find the convex hull of L (shown in light blue) and R (shown in purple).

To merge the left hull and the right hull it is necessary to find the two red edges shown on the left (the upper and lower common tangents).

The upper common tangent can be found in linear time by scanning around the left hull in a clockwise direction and around the right hull in an anti-clockwise direction.

The two tangents divide each hull into two pieces. The edges belonging to one of thse pieces must be deleted (shown in yellow).

The final hull.

以另一個程式來跑的話

見下表:

PS: In circle 代表最終的convex hull 為近似圓的圖形

   On circle 代表點為一個圓形

   In square 代表最終的 convex hull 為近似正方形的圖形

以此可以得到結論

Gift wrap 在 in circle and on circle, in square  是最快的

Quick hull 沒有意外的在 on circle 大幅落後對手最慢

總結來說 那一種演算法都各有好處也各有各的缺點 所以必須看情況來使用才是對正確的方法

Reference:

http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

http://zh.wikipedia.org/wiki/%E5%87%B8%E5%8C%85

http://www.cs.princeton.edu/~ah/alg_anim/version1/ConvexHull.html

http://www.geocities.com/kfzhouy/Hull.html

"

"

一、前言：

為何選擇A* Algorithm做為這次的Term Project題目？其實原本是想介紹有關遊戲方面的演算法，想想覺得即時戰略的遊戲，為何遊戲角色會知道我要怎走才是最短的路徑？(雖然有些還是在繞路…)，是如何避開那些障礙物找到正確的路徑？也因此在上網查了相關資訊後決定研究最小路徑的演算法A* Algorithm。

[@more@]

二、A* Algorithm介紹：

1.      A* Algorithm一個重要的核心就是開啟列表 (Open List)和關閉列表 (Closed List)的使用。開啟列表存放著你目前節點可能接下來會經過的節點。

2.      A* Algorithm其中一個最重要的核心部分就是在其路徑評估的公式，其公式為：F= G + H，G代表從起點，沿著產生的路徑，移動到你所相鄰節點的移動代價；H為從所選擇的相鄰節點移動到所指定終點的移動代價，又稱為錯誤嘗試(Heuristic)的方法，因為此路徑的做法為猜測的方法，在移動的過程中會碰到不同的障礙物(例如：樹林、牆壁、湖泊…等)，所以我們對於路徑的長度只能猜測，但這大多都是錯誤的路徑長度；F則為G和H的和。H的計算方式有許多種，比較常用的方法有：

A.      曼哈頓法 (Manhattan Method)：此方法計算目前節點到終點節點之間水瓶和垂直的方格總數和，並將其和 * 10 (對角線方格並不在此討論中)，並忽略所有的障礙物，因此此結果為一估計值，而非其實際值。(這有點像是在城市間的街角行進，對角線將被視為建築物而無法穿越)。

B.      Diagonal Shortcut Method：此方法會計算兩點x軸和y軸的實際距離，若x軸的距離 > y軸的距離，則將H計算為：H = 14 * y軸距離 + 10 * (x軸距離 – y軸距離)；若x軸距離 < y軸距離，則將H計算為H = 14 * x軸距離 + 10 * (y軸距離 – x軸距離)。

其他還有不同的方法，不過在此我們就不多做討論。

有了以上的準備，接下來我們就可以介紹A* Algorithm是怎麼算出最短路徑的。

A* Algorthm的Pseudo Code如下：

Add START to OPEN listwhile OPEN not emptyget node n from OPEN that has the lowest f(n)if n is GOAL then return pathmove n to CLOSEDfor each n' = CanMove(n, direction)g(n') = g(n) + 1calculate h(n')if n' in OPEN list and new n' is not better, continueif n' in CLOSED list and new n' is not better, continueremove any n' from OPEN and CLOSEDadd n as n's parentadd n' to OPENend forend while

if we get to here, then there is No Solution

三、心得：A* Algorithm的原理並不難，研究起來也非常的有趣，大概是因為跟遊戲有關係吧?!只是實做時還會有更多額外的外在因素會影響到A* Algorithm的結果。

例如：

1.      其他元素：如果碰到的障礙物並不是靜止的，而是移動的，那麼A* Algorithm設計起來將會非常的複雜，網路上的資料就有提到：不妨只考慮靜止或那些在計算路徑時臨近而來的元素，將其當前位置的標誌設為可通過的，而對於鄰近的運動中的元素，則使用懲罰她們各自路徑上的節點來鼓勵這些路徑搜尋程是找到不同的路徑。

2.      不同地形的耗損：在遊戲中，一定會有不同地形的路徑，如果將地形的耗損也考慮進去，那麼有時候距離最短的路徑不一定是最快的，不過其設計起來並不困難，只需在公式中一併計算地形耗損的值即可。

3.      其他因素：像是遊戲中可能會考慮到物種的相剋、敵人的多寡、任務目標…等，進而影響最短路徑的計算，所以各個遊戲在使用A* Algorithm時都需考慮到其自身影響的因素而加以改良。

其實原本還想將A* Algorithm和Dijkstra Algorithm拿來做比較的，因為兩者均為尋找最短路徑的演算法(不過在查了資料後，發現A* Algorithm似乎比Dijkstra Algorithm要來的好點?!) 只可惜畫圖畫了太久，實在沒有其餘心力再去將A* Algorithm和Dijkstra Algorithm做一番比較。不過還是希望下次有機會可以將A* Algorithm研究的更為透徹。

 四、參考資料：

http://swf.com.tw/?p=67

http://www.policyalmanac.org/games/heuristics.htm

http://en.wikipedia.org/wiki/A%2A_algorithm

http://blog.minstrel.idv.tw/2004/12/star-algorithm.html

http://www.geocities.com/jheyesjones/astar.html

http://www.edenwaith.com/products/pige/tutorials/a-star.php

"

493511369 資工三甲 陳建良

　引言一般來說，最佳化的設計法可以分為兩類，第一類是特定行最佳化法則，由於是針對特定函數發展，所以目標函數必須滿足某些特性。第二類是廣義型最佳化化法則，無論目標函數的特性為何，都不用修改設計法則，這篇要研究的基因演算法就屬此類，雖然效率較低但應用的層面較廣，但效率較低。[@more@]基因演算法則基因演算法的理論最先提倡的人是1975年一位叫Holland的先生，是基於選擇過程的一種最佳化搜尋機構，其基本精神在於仿效生物界中物競天擇、優劣勝敗的自然進化法則，他能夠選擇物種中比較具較有好特性的上一母代、並且隨機性的彼此交換基因資訊，以期望可以得到比上一母代好的子代，如此重複下去以產生適應性最強的最佳物種。基因演算法的三個主要運算子為複製、交配、以及突變。應用基因演算法來解決最佳化問題的基本精神為:將所要搜尋的所有參數編碼為染色體的離散/二元字串，例如說我們可以用五個位元的字串-11010來代表參數值，如此隨機的重複產生N個初始物種(字串)，然後依據求解之條件來設計適應函數(fitness function)，適應函數值高的物種將被挑選至交配池(mating pool)中，此即複製過程，再依交配及突變過程的運算，即完成一代的基因演算法則，如此重複下去已產生適應性最強的物種，其演化流程圖如下圖所示：複製 (reproduction)複製是依據每一物種的適應程度來決定其在下一子代中應被淘汰或複製的個數多寡的一種運算過程，適應程度高的物種再下一子代中將被大量複製；適應程度低的物種在下一子代中則被淘汰，其中適應程度的良策是由適應函數來反應。複製過程有兩種型式：(a)輪盤式選擇 (b)競爭式選擇                                                                                (a) 輪盤式選擇 (roulette wheel selection)在每一代的演化過程中，首先依每個物種(字串)的適應函數值分割輪盤上的位置，適應函數值越大則在輪盤上佔有的面積也越大，每個物種在輪盤上所佔有的面積比例也就代表其被挑選至交配池的機率，然後隨機地選取輪盤上的一點，其所對應的物種即被選中送至交配池中。假設交配池有Ｎ個物種，fi代表第i個物種的適應函數值。那麼，理論上此物種應該會有 個被複製至交配池中，其中 代表所有物種的平均適應函數值。                                                                                (b) 競爭式選擇 (tournament selection)在每一代的演化過程中，首先隨機地選取兩個或更多個物種(字串)，具有最大適應函數值的物種即被選中送至交配池中。 基本上輪盤式選擇及競爭式選擇皆能達到複製過程中適者生存的要求，由於競爭式選擇所需的計算量較少、且可以藉由一次選取物種個數的多寡來控制競爭者的速度，因此建議是採用競爭式選擇。                                                                                                                                                                                                                                                交配 (crossover)交配過程是隨機地選取交配池中的兩個母代物種字串，並且彼此交換位元資訊，進而組成另外兩個新的物種，藉著累積前代的優秀位元資訊一期望能產生更優秀的子代。交配過程發生的機率由交配機率所控制。而交配過程有三種型式：(a) 單點交配 (b) 兩點交配 (c)字罩交配                                                                                (a) 單點交配在所選出的兩字串中，隨機地選取一交配點，並交換兩字串中此交配點後的所有位元。示意圖如下：(b) 兩點交配在所選取的兩字串中，隨機地選取兩個交配點，並交換兩字串中兩個交配點間的所有位元示意圖如下：                                                                                                                                                                                                                                                (c) 字罩交配首先產生與物種字串長度相同的字罩當作交配時的位元指標器，其中字罩是隨機地由0與1所組成，字罩中為1的位元即是兩物種字串彼此交換位元資訊的位置。示意圖如下：突變 (mutation)突變過程是隨機地選取一物種字串，並且隨機地選取突變點，然後改變物種字串裡的位元資訊。突變過程發生的機率由突變機率所控制。突變過程可以針對單一位元、或對整個字串進行突變運算、或以字罩突變方式為之。對於二進制的位元字串而言就是將字串中的0變成1，1變成0。單點突變的過程示意圖如下：基因演算法則的主要特性                                                                                基因演算法則有別於傳統的搜尋方式的主要特性：                                                                                一、基因演算法則是以參數集合之編碼進行運算而不是參數本身，因此可以跳脫搜尋空間分析上的限制。                                                                                二、基因演算法則同時考慮搜尋空間上多個點而不是單一個點，因此可以較快地獲得整體最佳解(global optimum)，同時也可以避免陷入區域最佳值(local optimum)的機會，此特性是基因演算法的最大優點！　三、基因演算法則只使用適應函數的資訊而不需要其他輔助的資訊，因此可以使用各種型態的適應函數，並可以計算資源避免繁複的數學運算。                                                                                四、基因演算法則使用機率規則方式去引導搜尋方向，而不適用明確的規則，因此較能符合各種不同類型的最佳化問題。 基因演算法則的細部探討1.參數設定應用基因宰算法則在為佳化之設計上，參數的設定往往是最困難的地方，因為這些設定將影響，最後搜尋之結果，且參數之間互相關聯，彼此相依。重要參數包括：編碼範圍字串長度族群大小交配機率突變機率適應函數之設計2.編碼及解碼過程假設受控系統中有三個參數要編碼，三個參數值均介於[0,1]之間，且每個參數使用五個位元加以編碼，則二進制字串編碼流程如下：3.字串長度字串編碼的長度越長則精準度越高，但所需的編碼、解碼運算也相對增加。由於一個物種字串，代表一組可能的參數解，在每代的演化過程中，適應函數的計算都需要對物種字串進行解碼運算，因此對於較複雜且具有多參數的系統，在編碼及解碼上需要不少的浮點數運算，因此相當的耗時且耗費計算機資源。字串位元長度的選擇主要是依據問題所要求的精確度而定，定的太低可能會導致搜尋不到系統的整體最佳解，定的太高則耗費太多計算機資源於編碼、解碼運算。4.交配機率交配的頻率視交配交配機率的大小而定。交配率越高，則新物種進入族群的速度越快，整個搜尋最佳值的速度也越快。但是如果交配率太高，則優良的物種從族群中被取走的速度可能會比交配出新物種所產生的進化來的快，而使得交配的原意喪失；相反地，若交配率太低，則會使搜尋的過程停滯下來。雖然交配過程中充滿許多隨機性，但是由於交配的物種來源已經事先經過複製過程的篩選，所留下的物種軍事是硬性較強的物種，因此，基因演算法比一般的隨機搜尋有效率。5.突變機率突變是一項必須的運算過程，因為在複製及交配過程中可能使得整個族群裡，所有字串中的某一特定位元皆一樣。舉例如下：假設有四個字串Ａ、Ｂ、Ｃ、Ｄ分別為：A：00110B：01111C：10110D：11111其中第三個與第四個位元在四個字串中皆為相同的位元值，因此不管是經過複製或交配的過程都不會改變到第三及第四位元的位元值，因而限制了某些新物種進入族群的機會，造成基因演算法在搜尋過程中有可能陷入區域最佳值，而無法搜尋到整體最佳值，因此必須要做少量的突變，以求所有的物種均能被考慮到；一般說來，突變機率都定的很低，因為如果定的太高則與隨機搜尋無異。6.避免陷入區域最佳值由於族群大小、交配機率，以及突變機率控制著基因演算法收斂速度的快慢；若定的太低則收斂得太快，容易陷入區域最佳值；若定的太高則可能需要很長時間才能收歛，需視所搜尋空間的維度及參數範圍大小與編碼時所採用的精確度(字串長度)，一起考量。為避免交配及突變機率的起始設定值太高，我們可以分別訂定交配及突變機率的最大值及最小值，交配及突變機率於起始時設定為其最大值並且隨著演化代數的增加而遞減至其最小值。另一個彈性的作法是採用浮動式交配機率及浮動式突變機率；其基本精神是當物種進化的速度停滯不前時，可以視為系統已經收斂至區域最佳值，此時加入一些人為擾動可以刺激新的物種產生；其作法是當每代的最佳適應函數值維持若干代不變時，則提高交配及複製機率以增加新物種產生速度，當最佳適應值增加時，再恢復為原先的交配及突變機率。7.適應函數之設計原則原則上，適應函數須能反映出不同物種間適應程度的差異即可，但為了能增加新物種進入族群的機會，適應函數須能將次佳物種快速地淘汰，以加速搜尋過程。8.搜尋終止之條件基因演算法搜尋終止的條件是當所有物種字串均趨一致，亦即不再有更好的適應函數值出現時予以中止；而對於某些線上即時系統而言；為了節省時間，當適應函數值到達系統要求後即可終止搜尋程序。 　結語基因眼演算法是一種無需梯度(gradient)資訊的最佳化工具，由於只要有合適的適應函數之後，經過多次的疊代，就能提供一組令人滿意的答案，因此，基因演算法有很高的實用價值。                         "