C++回溯法实例分析
更新时间:2020年4月25日 17:40 点击:2145
本文实例讲述了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++程序算法设计的学习有所帮助。
上一篇: C++中的RAII机制详解
下一篇: C++设计模式之单例模式
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25