C++回溯法實例剖析。本站提示廣大學習愛好者:(C++回溯法實例剖析)文章只能為提供參考,不一定能成為您想要的結果。以下是C++回溯法實例剖析正文
本文實例講述了C++的回溯法,分享給年夜家供年夜家參考之用。詳細辦法剖析以下:
普通來講,回溯法是一種列舉狀況空間中一切能夠狀況的體系辦法,它是一個普通性的算法框架。
解向量a=(a1, a2, ..., an),個中每一個元素ai取自一個無限序列集Si,如許的解向量可以表現一個分列,個中ai是分列中的第i個元素,也能夠表現子集S,個中ai為真當且僅當選集中的第i個元素在S中;乃至可以表現游戲的行為序列或許圖中的途徑。
在回溯法的每步,我們從一個給定的部門解a={a1, a2, ..., ak}開端,測驗考試在最初添加元從來擴大這個部門解,擴大以後,我們必需測試它能否為一個完全解,假如是的話,就輸入這個解;假如不完全,我們必需檢討這個部門解能否仍有能夠擴大成完全解,假如有能夠,遞歸下去;假如沒能夠,從a中刪除新參加的最初一個元素,然後測驗考試該地位上的其他能夠性。
用一個全局變量來掌握回溯能否完成,這個變量設為finished,那末回溯框架以下,可謂是回溯年夜法之精華與神器
bool finished = false; void backTack(int input[], int inputSize, int index, int states[], int stateSize) { int candidates[MAXCANDIDATE]; int ncandidates; if (isSolution(input, inputSize, index) == true) { processSolution(input, inputSize, index); } else { constructCandidate(input, inputSize, index, candidates, &ncandidates); for (int i = 0; i < ncandidates; i++) { input[index] = candidates[i]; backTack(input, inputSize, index + 1); if (finished) return; } } }
不拘泥於框架的情勢,我們可以編寫出以下代碼:
#include <iostream> using namespace std; char str[] = "abc"; const int size = 3; int constructCandidate(bool *flag, int size = 2) { flag[0] = true; flag[1] = false; return 2; } void printCombine(const char *str, bool *flag, int pos, int size) { if (str == NULL || flag == NULL || size <= 0) return; if (pos == size) { cout << "{ "; for (int i = 0; i < size; i++) { if (flag[i] == true) cout << str[i] << " "; } cout << "}" << endl; } else { bool candidates[2]; int number = constructCandidate(candidates); for (int j = 0; j < number; j++) { flag[pos] = candidates[j]; printCombine(str, flag, pos + 1, size); } } } void main() { bool *flag = new bool[size]; if (flag == NULL) return; printCombine(str, flag, 0, size); delete []flag; }
采取回溯法框架來盤算字典序分列:
#include <iostream> using namespace std; char str[] = "abc"; const int size = 3; void constructCandidate(char *input, int inputSize, int index, char *states, char *candidates, int *ncandidates) { if (input == NULL || inputSize <= 0 || index < 0 || candidates == NULL || ncandidates == NULL) return; bool buff[256]; for (int i = 0; i < 256; i++) buff[i] = false; int count = 0; for (int i = 0; i < index; i++) { buff[states[i]] = true; } for (int i = 0; i < inputSize; i++) { if (buff[input[i]] == false) candidates[count++] = input[i]; } *ncandidates = count; return; } bool isSolution(int index, int inputSize) { if (index == inputSize) return true; else return false; } void processSolution(char *input, int inputSize) { if (input == NULL || inputSize <= 0) return; for (int i = 0; i < inputSize; i++) cout << input[i]; cout << endl; } void backTack(char *input, int inputSize, int index, char *states, int stateSize) { if (input == NULL || inputSize <= 0 || index < 0 || states == NULL || stateSize <= 0) return; char candidates[100]; int ncandidates; if (isSolution(index, inputSize) == true) { processSolution(states, inputSize); return; } else { constructCandidate(input, inputSize, index, states, candidates, &ncandidates); for (int i = 0; i < ncandidates; i++) { states[index] = candidates[i]; backTack(input, inputSize, index + 1, states, stateSize); } } } void main() { char *candidates = new char[size]; if (candidates == NULL) return; backTack(str, size, 0, candidates, size); delete []candidates; }
比較上述兩種情況,可以發明獨一的差別在於全分列對以後解向量沒有請求,而字典序對以後解向量是有請求的,須要曉得以後解的狀況!
八皇後回溯法求解:
#include <iostream> using namespace std; int position[8]; void constructCandidate(int *input, int inputSize, int index, int *states, int *candidates, int *ncandidates) { if (input == NULL || inputSize <= 0 || index < 0 || candidates == NULL || ncandidates == NULL) return; *ncandidates = 0; bool flag; for (int i = 0; i < inputSize; i++) { flag = true; for (int j = 0; j < index; j++) { if (abs(index - j) == abs(i - states[j])) flag = false; if (i == states[j]) flag = false; } if (flag == true) { candidates[*ncandidates] = i; *ncandidates = *ncandidates + 1; } } /* cout << "ncandidates = " << *ncandidates << endl; system("pause");*/ return; } bool isSolution(int index, int inputSize) { if (index == inputSize) return true; else return false; } void processSolution(int &count) { count++; } void backTack(int *input, int inputSize, int index, int *states, int stateSize, int &count) { if (input == NULL || inputSize <= 0 || index < 0 || states == NULL || stateSize <= 0) return; int candidates[8]; int ncandidates; if (isSolution(index, inputSize) == true) { processSolution(count); } else { constructCandidate(input, inputSize, index, states, candidates, &ncandidates); for (int i = 0; i < ncandidates; i++) { states[index] = candidates[i]; backTack(input, inputSize, index + 1, states, stateSize, count); } } } void main() { //初始化棋局 for (int i = 0; i < 8; i++) position[i] = i; int states[8]; int count = 0; backTack(position, 8, 0, states, 8, count); cout << "count = " << count << endl; }
願望本文所述對年夜家C++法式算法設計的進修有所贊助。