啟發式探索演算法

㈠ 啟發式搜索演算法一定能找到最優解嗎

看情況。具體演算法具體分析，有些可以，有些不一定。

㈡ 啟發式搜索演算法的產生背景

何謂啟發式搜索演算法
在說它之前先提狀態空間搜索。狀態空間搜索，如果按專業點的說法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程。通俗點說，兩點之間求一線路，這兩點是求解的開始和問題的結果，而這一線路不一定是直線，可以是曲折的。由於求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構成了一個圖，我們說這個圖就是狀態空間。問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果。這個尋找的過程就是狀態空間搜索。
常用的狀態空間搜索有深度優先和廣度優先。深度優先是從初始狀態一層一層向下找，直到找到目標為止。廣度優先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。這兩種演算法在數據結構書中都有描述，可以參看這些書得到更詳細的解釋。
前面說的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率實在太低，甚至不可完成。在這里就要用到啟發式搜索了。

㈢ 貪心演算法是不是啟發式搜索

使用網路Hi可以第一時間收到「提問有新回答」「回答被採納」「網友求助」的通知。查看詳情

您想在自己的網站上展示網路「知道」上的問答嗎？來獲取免費代碼吧！

投訴或舉報，請到網路知道投訴吧反饋。
功能意見建議，請到知道意見社吧反饋。

㈣ 什麼是啟發式演算法（轉）

啟發式方法（試探法）是一種幫你尋求答案的技術，但它給出的答案是具有偶然性的（subjecttochance），因為啟發式方法僅僅告訴你該如何去找，而沒有告訴你要找什麼。它並不告訴你該如何直接從A點到達B點，它甚至可能連A點和B點在哪裡都不知道。實際上，啟發式方法是穿著小丑兒外套的演算法：它的結果不太好預測，也更有趣，但不會給你什麼30
天無效退款的保證。
駕駛汽車到達某人的家，寫成演算法是這樣的：沿167
號高速公路往南行至Puyallup；從SouthHillMall出口出來後往山上開4.5
英里；在一個雜物店旁邊的紅綠燈路口右轉，接著在第一個路口左轉；從左邊褐色大房子的車道進去，就是NorthCedar路714號。
用啟發式方法來描述則可能是這樣：找出上一次我們寄給你的信，照著信上面的寄出地址開車到這個鎮；到了之後你問一下我們的房子在哪裡。這里每個人都認識我們——肯定有人會很願意幫助你的；如果你找不到人，那就找個公共電話亭給我們打電話，我們會出來接你。
從上面的啟發式演算法的解釋可以看出，啟發式演算法的難點是建立符合實際問題的一系列啟發式規則。啟發式演算法的優點在於它比盲目型的搜索法要高效，一個經過仔細設計的啟發函數，往往在很快的時間內就可得到一個搜索問題的最優解，對於NP問題，亦可在多項式時間內得到一個較優解。

㈤ 粒子群演算法屬於啟發式搜索演算法嗎

啟發式演算法實際上就是針對具體問題,加入了人的經驗的最優求解演算法.不同的問題,有不同的啟發規則.遺傳演算法、粒子群演算法這一類演算法某種程度上可以歸為啟發

㈥ 什麼是啟發式或探索法

什麼是啟發式或探索法(heuristic)

名詞解釋
Heuristics，我喜歡的翻譯是「探索法」 ，而不是「啟發式」，因為前者更親民一些，容易被理解。另外，導致理解困難的一個原因是該詞經常出現在一些本來就讓人迷糊的專業領域語境中，例如，經常看到某某殺毒軟體用啟發式方法查毒，普通民眾本來就對殺毒軟體很敬畏，看到「啟發式」就更摸不著北了。
實際上，這個詞的解釋十分簡單，例如，查詞典，可以看到：
The use of experience and practical efforts to find answers to questions or to improve performance
heuristic，將其定義為基於經驗的技巧（technique），用於解決問題、學習和探索。並對該詞進行了更詳盡的解釋並羅列了多個相關領域：
A heuristic method is used to rapidly come to a solution that is hoped to be close to the best possible answer, or 'optimal solution'. A heuristic is a "rule of thumb", an ecated guess, an intuitive judgment or simply common sense.
A heuristic is a general way of solving a problem. Heuristics as a noun is another name for heuristic methods.
Heuristic可以等同於：實際經驗估計（rule of thumb）、有依據的猜測（ecated guess, a guess beased on a certain amount of information, and therefore likely to be right）和常識（由經驗得來的判斷力）。

一個容易理解的解釋
人在解決問題時所採取的一種根據經驗規則進行發現的方法。其特點是在解決問題時,利用過去的經驗,選擇已經行之有效的方法，而不是系統地、以確定的步驟去尋求答案。啟發式解決問題的方法是與演算法相對立的。演算法是把各種可能性都一一進行嘗試，最終能找到問題的答案，但它是在很大的問題空間內，花費大量的時間和精力才能求得答案。啟發式方法則是在有限的搜索空間內，大大減少嘗試的數量，能迅速地達到問題的解決。但由於這種方法具有嘗試錯誤的特點，所以也有失敗的可能性。科學家的許多重大發現，常常是利用極為簡單的啟發式規則。

計算機科學和認知科學領域
上節內容很抽象，不知道這個heuristics能幹什麼，在網路上搜索關於heuristics的相關知識起源於某位朋友說我的一個系統設計是一種啟發式的。我真不知道他到底有何所指，暫時也沒有機會做深入溝通。在網路上搜索，看到一篇好文章，有關物理符號系統和啟發式搜索，可以看出該文作者是有自己的理解的，不是像我這樣在網路上surfing。
因為暫時沒有時間仔細閱讀和理解，看看這篇文章《什麼是啟發式（heuristic）?》也許能夠增加一點直觀印象，尤其它舉的例子（用以比較啟發式方法和演算法）
駕駛汽車到達某人的家，寫成演算法是這樣的：沿167 號高速公路往南行至Puyallup；從South Hill Mall 出口出來後往山上開 4.5 英里； 在一個雜物店旁邊的紅綠燈路口右轉，接著在第一個路口左轉；從左邊褐色大房子的車道進去，就是North Cedar 路714 號。

用啟發式方法來描述則可能是這樣：找出上一次我們寄給你的信，照著信上面的寄出地址開車到這個鎮；到了之後你問一下我們的房子在哪裡。 這里每個人都認識我們——肯定有人會很願意幫助你的；如果你找不到人，那就找個公共電話亭給我們打電話，我們會出來接你。

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

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

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

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

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

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

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

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



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

㈨ 誰能詳細介紹一下啟發式演算法的原理或者方法

整數規劃一般是不容易得到最優解的。啟發式演算法可以在合理的計算時間內得到較解。局域搜索啟發式演算法應用廣泛。局域搜索的一般步驟如下： 從一個初始可行解出發 找出相鄰的可行解 從相鄰的可行解中找出更好的可行解 地，局域搜索啟發式演算法會得到一個局部最優解，而這個局部最優解有時就是全局。演算法的好與壞都決定於步驟 3。 1.1 模擬退火方法 相鄰元素是隨機選擇的，選上的概率為pn ， pn= 1∑。移動的決策取n∈ N標成本和退火概率： c(y)?c(x)??py(x)?eTc(y)φ c(x) pxy= ? ?py(x)?Ct溫度梯度是根據一定的規則選擇的，比如T (t) =T t() = Calog t或， a π 1。

㈩ 啟發式搜索是什麼

啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。在啟發式搜索中，對位置的估價是十分重要的。採用了不同的估價可以有不同的效果。我們先看看估價是如何表示的。
啟發中的估價是用估價函數表示的，如：
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)，而提高效率。
啟發演算法有： 蟻群演算法，遺傳演算法、模擬退火演算法等
蟻群演算法是一種來自大自然的隨機搜索尋優方法，是生物界的群體啟發式行為，現己陸續應用到組合優化、人工智慧、通訊等多個領域。蟻群演算法的正反饋性和協同性使其可用於分布式系統，隱含的並行性更使之具有極強的發展潛力。從數值模擬結果來看，它比目前風行一時的遺傳演算法、模擬退火演算法等有更好的適應性。