VNS演算法中局部搜索用什麼方式

1. 什麼是局部搜索演算法

局部搜索演算法是從爬山法改進而來的。
簡單來說，局部搜索演算法是一種簡單的貪心搜索演算法，該演算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。
在計算機科學中，局部搜索是解決最優化問題的一種元啟發式演算法。局部搜索從一個初始解出發，然後搜索解的鄰域，如有更優的解則移動至該解並繼續執行搜索，否則返回當前解。
1、局部搜索演算法的基本思想：
在搜索過程中，始終選擇當前點的鄰居中與離目標最近者的方向搜索。
2、局部搜索的優點：
簡單、靈活及易於實現，缺點是容易陷入局部最優且解的質量與初始解和鄰域的結構密切相關。常見的改進方法有模擬退火、禁忌搜索等。
3、局部搜索廣泛應用：
計算機科學（主要是人工智慧）、數學、運籌學、工程學、生物信息學中各種很難找到全局最優解的計算問題。

2. 局部搜索與經典搜索有什麼不同

局部搜索與經典搜索的不同分別是：

1、局部搜索：局部搜索不關心路徑代價，但是關註解狀態。比如八皇後問題，不關心是怎麼到目的狀態的，只關心最終布局對不對，許多重要應用都有這樣的性質，如作業空間調度，自動程序設計等。

局部搜索有兩個關鍵優點：1、通常只用常數級的內存；2、通常能在系逗緩首統化演算法不適用的很大或無限的（連續的）狀態山數空間中找到合理的解。

此外，局部搜索演算法對於解決純粹的最優化問題十分有用，其目標是根據目標函數找到最佳狀態。

2、經典搜索：通過形式化的定義搜索問題，則搜索問題的解描述為一組讓初始狀態轉變為目標狀態的行動序列，而搜索問題的最優解描述為使得路徑代價最小的一組讓初始狀態轉變為目標狀態的行動序列。

經典搜索的種類主要是：

1、樹搜索：例如在羅馬尼亞問題中，從父結點In(Arad)出發得到三個子節點：In(Sibiu)，In(Timisoara)和In(Zerind)，接下來需要繼續從這三種子結點中選擇其一繼續考慮，假設我們選擇In(Sibiu)，則檢查它是否是目標狀態。

如果不是目標狀態，則繼續擴展它得到四個狀態：In(Arad)，In(Fagaras)，In(Oradea)，In(Rimnicu Vikea)。繼續按此方式拓展In(Timisoara)和In(Zerind)。如果未找到目標狀態，則繼續對葉子結點作同樣的操作。

2、圖搜索演算法：在圖搜索演算法中，在擴展的時候如果遇到已經在 explored 集合中的結點或已經在 frontier 集合中的結點，則不將該結點哪局拓展進 frontier 集合，這也是其與樹搜索演算法的主要區別。

3. 啟發式搜索全局擇優搜索和局部擇優搜索的區別是什麼

根據問題的實際情況不斷尋找可利用的知識，從而構造成一條代價較少的推理路線，使問題得到圓滿解決的過程稱為搜索。

尋找問題的解的一種可靠的方法是首先列出所有候選解，然後依次檢查每一個解，即可以找到所需要的問題的答案。這是一種「萬能」的方法，理論上，當候選解的數量可以窮盡並且通過檢查所有或部分候選解能夠得到所需解時，問題就能得到解決。

但是，在實際應用中，因為候選解的數量通常都非常大（比如指數級），並且計算機的速度和內存都有限制，因此對問題不加分析的窮盡演算法通常只能解決規模很小的問題。

在實際運用中常採用回溯和分枝定界法對問題進行求解。按照這兩種方法對候選解進行系統檢查通常會使問題的求解時間大大減少（無論對於最壞情形還是對於一般情形）。這二種方法由於都是按規定的路線進行，基本沒有使用與問題有關的啟發性信息，屬於盲目搜索策略。在涉及人工職能的有些問題如博弈問題時，還會用到啟發是搜索策略，如A*演算法等。

一、回溯法和分枝限界法

問題的表示

狀態空間表示法是表示問題及其搜索過程的一種形式表示方法。可以用解空間樹來表示問題的結構。 對於一棵樹，樹中的每一個結點確定所求問題的一個問題狀態，由根結點到其它結點的所有路徑確定了這個問題的狀態空間。解狀態是一些問題狀態S，對於這些問題狀態，由根到S的那條路徑確定了這解空間的一個元組。答案狀態則是由解狀態到根的路徑。

對於一種狀態空間樹，可以先系統地生成問題的狀態，接著確定問題狀態的解狀態，最後確定那些解狀態是答案狀態從而將這些問題解出。

從根結點開始解問題，如果已經生成一個結點而它的所有兒子結點還沒有全部生成，則這個結點叫做活結點。當前正在生成其兒子的活結點叫E結點，不再進一步擴展或者其兒子結點已經全部生成的生成結點就是死結點。

回溯演算法使用深度優先方法搜索樹結構，而分枝定界一般用寬度優先方法來搜索這些樹。

回溯方法的步驟如下：

1) 定義一個解空間，它包含問題的解。

2) 用適於搜索的方式組織該空間。

3) 用深度優先法搜索該空間，利用限界函數避免移動到不可能產生解的子空間。

回溯演算法的特性是在搜索執行的同時產生解空間。在搜索期間的任何時刻，僅保留從開始節點到當前E -節點的路徑。因此，回溯演算法的空間需求為O（從開始節點起最長路徑的長度）。

分枝限界法的步驟和回溯的唯一區別是採用了寬度優先的方法來搜索樹，因此分枝法消耗的空間比回溯法要多。

這二種搜索策略從本質上來講都是屬於窮盡法的搜索，由於在搜索路徑上的不同也造成這二種方法各自都有其優缺點、適用的求解問題也就不同。

寬度優先佔有優勢的問題：

九宮重排問題

九宮重排問題是一個可以回溯法和分枝法都能解決的問題。但是，對於這個問題運用分枝法是有利的。

九宮重排問題，在3*3的方格棋盤上放置標由數字1、2、3、4、5、6、7、8共8個棋子，初始狀態為S 0 ，目標狀態為Sg ，當找到一個解時結束搜索。

從根結點到葉子結點的路徑即為解，演算法為空格左移，空格上移，空格右移，空格下移。

S0

Sg

2
8
3

1
2
3

1

4

8

4

7
6
5

7
6
5

用寬度優先搜索，如下圖：

f'(x) = g(x) + h(x)

2 8 3

14

7 6 5

2 8 3

1 4

7 6 5

23

1 8 4

7 6 5

3 8 2

1 6 4

75

3 8 2

1 4

7 6 5

8 3

2 1 4

7 6 5

3 8 2

14

7 6 5

82

2 1 4

7 6 5

2 3 4

1 8

7 6 5

1 2 3

8 4

7 6 5

2 3

1 8 4

7 6 5

2 3

1 8 4

7 6 5

2 8 3

1 6 4

7 5

2 8 3

1 6 4

7 5

3 8 2

14

7 6 5

2 8 3

1 6

7 5 4

2 8 3

6 4

1 7 5

2 8 3

1 4 5

76

28

1 4 3

7 6 5

2 8 3

1 4 5

7 6

28

1 4 3

7 6 5

2 8 3

7 1 4

6 5

2 8 3

74

6 1 5

8 1 3

24

7 6 5

8 3 2

2 1 4

7 6 5

1 2 3

84

7 6 5

16

26

9

8

7

6

2

1

S0

4

3

5

Sg

圖示解的路徑是 S0-3-8-16-26(Sg)

寬度優先搜索的盲目性較大，當目標結點距離初始結點較遠時將會產生許多無用結點，空間浪費較大，搜索效率低，但是只要問題有解，用寬度優先搜索總可以得到解，而且得到的路徑最短的解。

用深度優先策略搜索，如下圖：

2 8 3

14

7 6 5

2 8 3

1 4

7 6 5

23

1 8 4

7 6 5

3 8 2

1 6 4

7 5

3 8 2

1 4

7 6 5

2 8 3

1 6 4

7 5

2 8 3

1 6 4

7 5

2 8 3

1 6

7 5 4

1

S0

2

2 8

1 6 3

7 5 4

2 8 1 6 3

7 5 4

2 8

1 6 3

7 5 4

3

4

5

6

在深度優先搜索中，搜索一旦進入某個分枝，就將沿著該分枝一直向下搜索，如果該節點恰好在此分支上，則可較快地得到解。但是，如果目標節電不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。

顯然該問題用寬度優先搜索的策略是較好的。

經典的N皇後問題

N皇後問題要求求出N個皇後在棋盤上的所有擺法，（該問題很多書籍上都有詳細介紹，這兒圖表省略），該問題是適合用回溯法來描述和解決的問題，通過深度優先搜索至多需要檢索N!個元組，而如果用分枝法，因為要生成所有問題的解，則必須儲存檢索過程中的E結點，造成儲存空間的極度膨脹，這類問題明顯是用回溯法佔優勢的。

回溯法和分枝法是基本的搜索策略，大多數情況下如果找不到更好的解決方案，總是可以用這二種方法嘗試。

但是它們有一個很大的缺陷就是都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分大，且不預測的情況下就不可取了。它的效率實在太低，甚至不可完成。



二、啟發式搜索演算法
通常在搜索中能直接運用回溯、分枝法的問題並不多，回溯和分枝的過程中，施加一定的條件，對搜索過程中出現的結點進行判斷，可以提高效率。

啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。在啟發式搜索中，對位置的估價是關鍵。採用了不同的估價可以有不同的效果。

啟發式搜索有很多的演算法，如：局部擇優搜索法、最好優先搜索法等等。A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。

局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。

局部擇優搜索法它是對深度優先搜索方法的一種改進。

全局擇優搜索是 局部擇優搜索的一種改進，試圖克服局部擇優搜索的的局限性。再搜索時，每次總是從全體的活結點中選取一個估價值最小的節點，

在搜索過程中，啟發式搜索的關鍵是要確定下一個要考察的節點，用於估價節點重要性的函數稱為估價函數

f'(x) = g(x) + h(x)

其中g(x)為從初始節點So到節點X已經實際付出的代價；h(x)是從節點X到節點Sg的最優路徑的估計代價。h(x)稱為啟發函數。

九宮重排

當用全局擇優搜索求解該問題時，可以設估價函數為 f'(x) = d(x) + h(x)

d(x)表示節點x的深度，h(x)表示節點x的棋局與目標節點棋局位置不相同的棋子數。

2 8 3

14

7 6 5

2 8 3

1 4

7 6 5

23

1 8 4

7 6 5

3 8 2

1 6 4

75

3 8 2

1 4

7 6 5

8 3

2 1 4

7 6 5

3 8 2

14

7 6 5

1 2 3

8 4

7 6 5

2 3

1 8 4

7 6 5

2 3

1 8 4

7 6 5

1 2 3

84

7 6 5

4

6

4

6

6

4

1

S0

4

4

5

Sg

1 2 3

7 8 4

6 5

5

5

S3

S2

S1

圖中節點旁標明的數字是該節點的估價函數值。

該問題的解路徑為： So-S1-S2-S3-Sg

以上論述一些樹型問題基本的搜索的策略，當問題的狀態空間是有向圖時，節點的重復將導致大量冗餘的搜索，甚至時搜索過程陷入無效的循環而無法找到解，這時就需要對估價函數進行限制，A*演算法就是針對圖的有序搜索的演算法。



問題的求解可以有很多方法，而如何建立數學模型，選擇問題的求解方式是十分重要的，方法的好壞是面向一個具體的問題的，需要具體問題具體分析

4. 局部搜索到底是什麼

簡單地說，就是根據已有的條件減小搜索范圍的搜索思想，不再全局搜索了。。。比如你想知道你班裡有多少有錢人，但由於你班上人太多了不可能一一調查，所以你可以根據「物以類聚」的假設減小搜索范圍，有錢人和有錢人走得更近些，就從某個有錢人的圈子進行排查。。。

5. A*演算法現實應用的實際意義

A*演算法在人工智慧中是一種典型的啟發式搜索演算法，為了說清楚A*演算法，我看還是先說說何謂啟發式演算法。

一、何謂啟發式搜索演算法

在說它之前先提提狀態空間搜索。狀態空間搜索，如果按專業點的說法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程。通俗點說，就是在解一個問題時，找到一條解題的過程可以從求解的開始到問題的結果（好象並不通俗哦）。由於求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構成了一個圖，我們說這個圖就是狀態空間。問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果。這個尋找的過程就是狀態空間搜索。

常用的狀態空間搜索有深度優先和廣度優先。廣度優先是從初始狀態一層一層向下找，直到找到目標為止。深度優先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。這兩種演算法在數據結構書中都有描述，可以參看這些書得到更詳細的解釋。

前面說的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率實在太低，甚至不可完成。在這里就要用到啟發式搜索了。

啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。在啟發式搜索中，對位置的估價是十分重要的。採用了不同的估價可以有不同的效果。我們先看看估價是如何表示的。

啟發中的估價是用估價函數表示的，如：

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

其中f(n)是節點n的估價函數，g(n)實在狀態空間中從初始節點到n節點的實際代價，h(n)是從n到目標節點最佳路徑的估計代價。在這里主要是h(n)體現了搜索的啟發信息，因為g(n)是已知的。如果說詳細點，g(n)代表了搜索的廣度的優先趨勢。但是當h(n)>>g(n)時，可以省略g(n),而提高效率。這些就深了，不懂也不影響啦！我們繼續看看何謂A*演算法。

二、初識A*演算法

啟發式搜索其實有很多的演算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼A*演算法又是一種什麼樣的演算法呢？其實A*演算法也是一種最好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：

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

這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈！你懂了嗎？肯定沒懂！接著看！

舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是。當然它是一種最臭的A*演算法。

再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。

6. 二分搜索演算法是利用什麼實現的演算法

根據分治策略來實現