啟發式搜尋法

我們可以將解決問題的過程描述為狀態空間之搜尋，狀態空間中的每一個狀態即代表相對應的解題狀況，搜尋是由初始狀態開始，經一系列之運算到達目標狀態為止。搜尋的方式可以分為基礎搜尋法和啟發式搜尋法兩大類。盲目搜尋的方式是指在搜尋的過程中，除了能夠分別目標狀態和非目標狀態之外，沒有其他參考資訊；而啟發式搜尋法則是在搜尋的過程中，可以知道目前狀態距離初始狀態多遠，同時可以藉由啟發函數估計目前狀態和目標狀態還有多少距離，進而增進搜尋的效率。

啟發法則的最大缺點是不能保證成功，但可大量節省時間是其優點，同時對問題愈了解便能夠設計出愈好的啟發函數。再者，啟發法則的執行效率是無法分析的，例如在對奕程式中使用啟發法則，我們只能藉由實驗觀察評估其效率，也許在贏了一百回合之後才發現其缺點，且對手一但發現了此缺點，程式的威力便會大減。

此外，並非每一種問題都適合啟發式搜尋法；例如：某些複雜的問題可以分解成幾個小問題再分別解決，問題狀態的改變只佔原狀態的一小部份，或問題本身在執行上無法回溯等。這些不適用啟發式搜尋法的問題，則可以改用規劃，規則庫，專家系統，學習等其他方法。

　　在此，我們討論三類的啟發式搜尋法：
　

最佳優先搜尋法 ( Best-First-Search )

命名為 " 最佳優先搜尋法 " 是一個令人可敬的稱呼,但其實有點名過其實 , 畢竟,假如我們每次都可得知哪一個點是最好的下一點 ,那就不用搜尋了.

在這個主題中,我們所要做的是從所有可以選擇的點中,經由估計函數的計算而選出其中最好的點,當成我們的下一點.如果估計函數是無所不知的,當然我們真的可以每次都走最佳的點 ,也就是我們所找到的路徑是成本最低的.但實際上估計函數通常無法做到這樣的程度. 因此,我們所選出的點可能不是最佳的點,但至少是眼前最好的.

因此簡單的說,最佳優先搜尋法就是由搜尋起點開始搜尋,然後對其作展開,並計算其展開點經由估計函數所得出的值 ,且選出其中最好的點作為我們的下一個搜尋點,再對其作展開並計算其展開點經由估計函數所得出的值,並選出其中最好的點作為我們的下一個搜尋點,依此類推..........直到到達我們的目標點.

當然用不同的估計函數將會有不同的搜尋路徑. 讓我們介紹最佳優先搜尋法兩個蠻好的應用:

貪心搜尋法 (Greedy Search )

A*搜尋法

記憶體限制搜尋法

　　搜尋演算法除了時間複雜度，記憶體的需求亦是必須考慮的一項重要因素。因為搜尋樹的節點個數是呈指數成長，若問題本身具有分支因數較多的特性，則執行搜尋演算法便很容易發生記憶體不足的情形，因此採用限制記憶體使用量的搜尋演算法便有其必要性。

　我們在此討論兩種記憶體限制搜尋法：

　１. 疊代加深Ａ*搜尋法(IDA*)。
２. 簡化記憶體限制Ａ*搜尋法(SMA*)。

疊代改進演算法

所謂的 "疊代改進演算法" 主要的觀念就是在搜尋的過程中每次只記得現在目前這個點的狀況卻不記得以前走過哪些點了 , 就像在霧裡爬山一樣 , 我們只知到目前所在的位置而只能對周圍的點作探測來決定下一步要往周圍的那一點走 , 如此 , 我們所在的狀態以此方法不斷的更新直到目標點為止 .

以下是有用到疊代改進演算法觀念的兩個搜尋方法:

1.登山搜尋法 2. 模擬退火法

啟發式搜尋法相關資料

1. Bagchi, A., and Mahanti, A. 1983. Search algorithms under different kinds of heuristics-A comparative study. JACM 30(1):1-21.

2. Bellmore, M., and Nemhauser, G. L. 1968. The traveling salesman problem: A survey. Operations Research 16:538-58.

3. Berliner, H. J. 1979. The B* tree search algorithm: A best-first proof procedure. Artificial Intelligence 12(1):23-40.

4. Chang, C. L., and Slagle, J. R. 1971. An admissible and optimal algorithm for searching AND/OR graphs. Artificial Intelligence 2(2):117-128.

5. Chakrabarti, P. P., Ghose, S., and DeSarkar, S. C. 1968. Heuristic Search through Islands. Artificial Intelligence 29: 339-347.

6. de Champeaux, B., and Sint, L. 1977. An improved bi-directional heuristic search algorithm. JACM 24:177-191.

7. Gelperin, D. 1977. On the optimality of A*. Artificial Intelligence 8(1):69-76.

8. Harris, L. R. 1974. The heuristic search under conditions of error. Artificial Intelligence 5(3):217-34.

9. Held, M., and Karp, R. M. 1970. The traveling salesman problem and minimum spanning trees. Operations Research 18:1138-1162.

10. Huyn, N., Dechter, R., and Pearl, J. 1980. Probabilistic analysis of the complexity of A*. Artificial Intelligence 15:241-251.

11. Karp, R. M. and Pearl, J. 1983. Searching for an optimal path in a tree with random cost. Artificial Intelligence 21(1-2):99-117.

12. Korf, R. E. 1985. Depth-first iterative-deepening: an optimal admissible tree search. Artificial Intelligence 27:97-109.

13. Korf, R. E. 1990. Real-time heuristic search. Artificial Intelligence 42:189-211.

14. Korf, R. E. 1993. Liner-space best-first search. Artificial Intelligence 62:41-78.

15. Kumar, V., and Kanal, L. 1983. A general branch and bound formulation for understanding and synthesizing AND/OR tree search procedures. Artificial Intelligence 21(1-2): 179-198.

16. Kwa, J. B. H. 1989. BS*: An admissible bidirecitonal staged heuristic search algorithm. Artificial Intelligence 38:95-109.

17. Lawler, E. L., and Wood, D. E. 1966. Branch-and-Bound methods: A survey. Operation Research 14(4):699-719.

18. Manzini, Giovanni. 1995. BIDA*: an improved perimeter search algorithm. Artificial Intelligence 75:347-360.

19. Martelli, A. 1977. On the complexity of admissible search algorithms. Artificial Intelligence 8(1):1-13.

20. Montanari, U. 1970. Heuristically guided search and chromosome matching. Artificial Intelligence 1(4):227-245.

map-coloring prlblem

著色定理

定理1 ﹙Brook定理﹚若圖不是一個奇回路或一個完全圖，則x﹙G﹚≦d，其中d是G頂點中的最大度數。

對於大多數的圖來說，最大度數是x﹙G﹚的一個弱的上界。在之前的例子中x﹙G﹚和最大的完全子圖緊密相關。因此似乎該有一個x﹙G﹚依賴於最大完全子圖大小的較強的界限。下面的定理說明了這種處理失效。

定理2 對於任何一個正整數k，存在不包含三角形而具有x﹙G﹚=k的圖G。

若不著色頂點而著色邊，使得具有公共頂點的邊取不同的顏色，則依據度數的圖的邊著色數的一個非常好的界限是存在的，關聯於給定的一個頂點的所有邊一定有不同的顏色，所以圖中的一個頂點的最大度數是邊著色數的一個下界，而且能更好地證明：

定理3 若圖G的頂點中的最大度數是d，則G的邊著色數為d或d+1。

有一種圖的頂點著色問題，能很好地表為涉及兩種顏色可著色的圖。這種圖的頂點能分為兩個集合使所有邊都能在一個集合中的一個頂點和另一個集合中的一個頂點之間。

定理4 一個圖能用兩種顏色著色唯且唯若當它不包含奇長度的回路。

兩種顏色可著色的圖也稱為二分圖。這個定理給出了為什麼例2中的輪形圖不能是3種顏色著色的圖。3種顏色著色這個輪形圖等價於兩種顏色著色外層的回路，但是定理4指出由於此回路是奇長度，所以它不能是兩種顏色著色的。

最後給出且證明一個關於著色平面圖的定理。正如前面所提到的那樣Appel和Haken已證明了所有平面圖是能用四種顏色著色的。但是他們的證明非常長且要求用計算機對每一種情形加以分析，所以，以下證明一個較容易的定理。

定理5 每一個平面圖是能用5種顏色來著色的。

證明僅需考慮連通的平面圖，因為能用五種顏色著色每個連通分支而完成用5種顏色著色不連通的的平面圖。對平面圖G的頂點個數p進行歸納來證明這個定理。

當p=5時，結論顯然成立。
假設對p=n-1的平面圖，結論成立。觀察p=n的平面圖G，我們說G中一定有一個度數不超過5的頂點x。因為平面圖的每個區域至少被3條邊圍成，所以，3r≦2e，r≦2e/3﹙其中r為G的區域數﹚。如果任意一個頂點均有deg﹙x﹚≧6，則2e=Σd﹙x﹚≧6ν，於是ν≦e/3。由歐拉定理2=ν-e+r≦e/3-e+2e/3=0，此矛盾說明在G中必存在頂點x使deg﹙x﹚≦5。

將G中的這個頂點x及與點x相關聯的邊捨棄後得到G′，由歸納假設x﹙G′﹚≦5。

只需考慮x﹙G′﹚=5的情形，設G′的頂點分別被塗上1，2，3，4，5等5種顏色，且每兩個相鄰頂點的顏色不同。

如果deg﹙x﹚＜5時，則將x塗上與相鄰各頂點﹙至多4個﹚均不相同的那一種顏色，就完成了G的適當著色。

如果deg﹙x﹚=5時，即x有5個相鄰接的頂點a，b，c，d，e。這裡可分為兩種情形家以分析：

第一種情況是a，b，c，d，e這5個結點的顏色不是全不相同，只塗了5種顏色中的一部分顏色，因而只需將x點塗上其他顏色即可。

第2種情況是a，b，c，d，e的顏色互不相同，不妨設a，b，c，d，e分別塗上顏色1，2，3，4，5，見圖。首先考慮從a起頂點被著色1和3的所有路徑。假設從a到c沒有1和3頂點組成的路徑。則能將a的顏色從1改成3，著色3的a的鄰接點改成1，等等，把沿著從a發出的所有1和3頂點組成的路徑都作這樣的改變。這個1和3交換都不影響c，因為從a到c沒有1和3頂點的路徑。從a起作這種1和3交換之後，a和c都為顏色3，x能被適當地著色1。另一方面，從a到c有一條1和3的路徑，則考慮從b發出的所有2和4著色頂點的路徑。從a到c的1和3的路徑以及邊﹙x，a﹚，﹙x，c﹚一起形成一個回路，它阻止了從b到d的任何2和4路徑存在的可能性。於是我們能沿著從b發出的所有2和4路徑作2和4的交換而不改變d的顏色。在這個2和4的交換之後，b和d都是顏色4，x能被適當地著色2。

這樣就完成歸納的證明，故任何n個頂點的連通平面圖能被5種顏色適當地著色。