回溯算法實際上一個類似枚舉的搜尋嘗試過程,主要是在搜尋嘗試過程中尋找問題的解,當發現已不滿足求解條件時,就“回溯”返回,嘗試別的路徑。回溯法是一種選優搜尋法,按選優條件向前搜尋,以達到目標。但當探索到某一步時,發現原先選擇並不優或達不到目標,就退回一步重新選擇,這種走不通就退回再走的技術為回溯法,而滿足回溯條件的某個狀態的點稱為“回溯點”。許多複雜的,規模較大的問題都可以使用回溯法,有“通用解題方法”的美稱。
基本介紹
- 中文名:回溯算法
- 外文名:backtracking algorithm
- 其他名稱:試探法
- 方法:一種系統地搜尋問題的解
- 基本思想:能進則進
- 例題:八皇后問題
來源
基本思想
算法框架
procedure try(i:integer);varbeginif i>n then 輸出結果else for j:=下界 to 上界 dobeginx[i]:=h[j];if 可行{滿足限界函式和約束條件} then begin 置值;try(i+1); end;end;
#include<iostream>#include<cmath>#include<cstdio>using namespace std;int ans[21] = {0}, tot = 0;bool a[21] = {0};void print(){tot++;cout << "No." << tot << ':';for (int i = 1; i <= 20; i++)cout << ans[i] << ' ';cout << endl;}bool isprime(int x1, int x2){int i = x1 + x2,f;for (f = 2; f <= sqrt(i); f++)if (i % f == 0)return false;return true;}int search(int t){for (int i = 1; i <= 20; i++){if (a[i] == false && isprime(ans[t - 1], i)){ans[t] = i;a[i] = true;if (t == 20 && isprime(ans[1], ans[20]))print();elsesearch(t + 1);a[i] = false;}}}int main() {search(1);printf("The total is %d", tot);}
典型例題
問題描述
代碼
int g_number = 0; void EightQueen(){ const int queens = 8; int ColumnIndex[queens]; for(int i = 0; i < queens; ++ i) ColumnIndex[i] = i; Permutation(ColumnIndex, queens, 0);} void Permutation(int ColumnIndex[], int length, int index){ if(index == length) { if(Check(ColumnIndex, length)) { ++ g_number; PrintQueen(ColumnIndex, length); } } else { for(int i = index; i < length; ++ i) { int temp = ColumnIndex[i]; ColumnIndex[i] = ColumnIndex[index]; ColumnIndex[index] = temp; Permutation(ColumnIndex, length, index + 1); temp = ColumnIndex[index]; ColumnIndex[index] = ColumnIndex[i]; ColumnIndex[i] = temp; } }} bool Check(int ColumnIndex[], int length){ for(int i = 0; i < length; ++ i) { for(int j = i + 1; j < length; ++ j) { if((i - j == ColumnIndex[i] - ColumnIndex[j]) || (j - i == ColumnIndex[i] - ColumnIndex[j])) return false; } } return true;} void PrintQueen(int ColumnIndex[], int length){ printf("Solution %d\n", g_number); for(int i = 0; i < length; ++i) printf("%d\t", ColumnIndex[i]); printf("\n");}