admin管理员组文章数量:1621657
以下是我个人对回溯的理解。
回溯,是尝试列举出所有解决问题的方法。
即按照问题所给的操作方法,进行模拟,当在寻找解的过程中,发现不符合题意的解,返回至上一步,如此重复,直到寻找到满足问题的解的过程。
由于回溯过程会产生解空间树,可以将求解过程,看作是对树的遍历操作。在遍历的同时,判断是否在当前结点处继续往子树遍历的过程。
接着是对ZOJ上的代码的整理:
/*
*ZOJ 1002
*judge status: Accepted
*language: C++
*run time(ms): 0
*rum Memory(kb): 276
*/
#include <iostream>
using namespace std;
const int MAXN = 4;//矩阵的维度
int n;
char Map[MAXN][MAXN];//存储题目中的数据
bool isPass[MAXN][MAXN];//标记矩阵中的位置是否经过
void Search(int i, int j, int &Max, int cnt);
bool isInside(int i, int j);
bool isSafe(int row, int col);
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(0);
while(cin>>n && n) {
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
cin>>Map[i][j], isPass[i][j] = false;
int Max = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
Search(i, j, Max, 0);
cout<<Max<<endl;
}
return 0;
}
/*以下对Search方法进行介绍:
*其中的Max是所求的解,即最大值;cnt是在当前求解过程中记录的当前最大值;
*其中的isSafe方法是判断继续遍历子树的条件是否满足;
*该方法的编写思路是:
*按照题目所给的要求,
*1)在'.'处可放置Gun,则尝试放入Gun,并用isSafe方法判断是否可以放置;
*2)无论是否可以放置当前的Gun,都在当前状态下,往四周尝试放置一把Gun;
*3)将以上对当前状态的处理还原,避免对之后操作的影响
*4)并返回上一状态。
*
*
*
*/
void Search(int i, int j, int &Max, int cnt)
{
isPass[i][j] = true;
if(Map[i][j] == '.' && isSafe(i, j)) {
Map[i][j] = 'G';
cnt++;
Max = Max > cnt? Max: cnt;
}
if(!isPass[i][j + 1] && isInside(i, j + 1)) {
Search(i, j + 1, Max, cnt);
}
if(!isPass[i + 1][j] && isInside(i + 1, j)) {
Search(i + 1, j, Max, cnt);
}
if(!isPass[i][j - 1] && isInside(i, j - 1)) {
Search(i, j - 1, Max, cnt);
}
if(!isPass[i - 1][j] && isInside(i - 1, j)) {
Search(i - 1, j, Max, cnt);
}
if(Map[i][j] == 'G') {
Map[i][j] = '.';
cnt--;
}
isPass[i][j] = false;
}
bool isInside(int i, int j)
{
if(i < 0 || i >= n) return false;
if(j < 0 || j >= n) return false;
return true;
}
bool isSafe(int row, int col)
{
bool rowOk = true, colOk = true;
for(int i = 1; row - i >= 0 || row + i < n; ++i)
{
if(row - i >= 0) {
if(Map[row - i][col] == 'G') {
rowOk = false;
break;
}
if(Map[row - i][col] == 'X') break;
}
if(row + i < n) {
if(Map[row + i][col] == 'G') {
rowOk = false;
break;
}
if(Map[row + i][col] == 'X') break;
}
}
for(int i = 1; col - i >= 0 || col + i < n; ++i)
{
if(col - i >= 0) {
if(Map[row][col - i] == 'G') {
colOk = false;
break;
}
if(Map[row][col - i] == 'X') break;
}
if(col + i < n) {
if(Map[row][col + i] == 'G') {
colOk = false;
break;
}
if(Map[row][col + i] == 'X') break;
}
}
return rowOk && colOk;
}
/*
*ZOJ 1003
*参考博客:
*http://blog.csdn/hackdevil/article/details/9190359
*/
/*
*judge status: Accepted
*language: C++
*run time(ms): 10
*run memory(kb): 276
*/
#include <iostream>
using namespace std;
void whichOne(int n, int m, bool &AWin, bool &BWin, int div);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
while(cin>>n>>m) {
if(n < m) {//exchange value
n = n^m;
m = n^m;
n = n^m;
}
bool AWin = false, BWin = false;
whichOne(n, m, AWin, BWin, 2);
if(!AWin && BWin) cout<<m<<endl;
else cout<<n<<endl;
}
return 0;
}
/*以下对whichOne方法进行介绍:
*其中的div是n,m的分解因子
*题目要求可以理解为,n分解得到的任意一个分解因子都不包含在m的分解因子中;
*也就是需要将所有的分解等式列举出来,这通过回溯实现。
*1)如果两者都能分解,则A胜,否则只要B能分解,则B胜;
*2)for循环就是尝试对n, m用div进行分解,并将分解的结果,继续分解;
*3)之后用div+1继续尝试分解,直到超过分解范围
*4)并返回上一步
*
*
*
*/
void whichOne(int n, int m, bool &AWin, bool &BWin, int div)
{
if(n == 1 && m == 1) {
AWin = true;
return;
}
if(m == 1) BWin = true;
for(int x = div; (n >= x || m >= x) && x < 101; ++x) {
if(m % x == 0) {
whichOne(n, m / x, AWin, BWin, x + 1);
if(AWin) return;
}
if(n % x == 0) {
whichOne(n / x, m, AWin, BWin, x + 1);
if(AWin) return;
}
}
}
/*
*ZOJ 1004
*judge status: Accepted
*language: C++
*run time(ms): 0
*run memory(kb): 276
*/
#include <iostream>
#include <string>
#include <iterator>
#include <stack>
#include <vector>
using namespace std;
string s1, s2;
stack<char> s;
vector<char> vOfSta;
void backtrack(int subscr1, int subsrc2, int len);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
while(cin>>s1>>s2) {
int len = s1.size();
cout<<'['<<endl;
backtrack(0, 0, len);
cout<<']'<<endl;
vOfSta.clear();
}
return 0;
}
/*以下对backtrack方法的进行介绍:
*subscr1是对字符串1下标的表示;subscr2同理;
*该backtrack方法是,对栈进栈出栈的模拟,即模拟栈对一个元素的进栈或出栈的操作;
*1)当字符串下标小于字符长度时,先将字符串push到栈中,并继续调用该方法;
*2)当字符串全部压入栈中后,尝试pop元素,如果符合条件,则输出结果;
*3)并将栈还原到原来的状态;
*4)如果字符串下标大于等于字符长度时,继续弹出多余的字符;
*5)将当前的字符尝试弹出,并调用backtrack方法;
*6)如果字符弹出,则将栈的状态进行还原;
*7)弹出进栈的元素并返回上一步;
*以下注释的backtrack方法,只是一个草稿。
*
*
*
*/
void backtrack(int subsrc1, int subsrc2, int len)
{
int index = subsrc2;
if(subsrc1 < len) {
s.push(s1[subsrc1]);
vOfSta.push_back('i');
backtrack(subsrc1 + 1, subsrc2, len);
} else {
while(!s.empty()) {
if(s.top() != s2[subsrc2]) break;
s.pop();
vOfSta.push_back('o');
subsrc2++;
}
if(s.empty()) {
vector<char>::iterator itOfS = vOfSta.begin();
vector<char>::iterator itOfE = vOfSta.end();
for( ; itOfS != itOfE; ++itOfS) cout<<*itOfS<<' ';
cout<<endl;
}
while(index < subsrc2) {
s.push(s2[subsrc2 - 1]);
vOfSta.pop_back();
subsrc2--;
}
return ;
}
if(subsrc1 + 1 == len) {
s.pop();
vOfSta.pop_back();
return ;
}
while(!s.empty() && s.top() == s2[subsrc2]) {
s.pop();
vOfSta.push_back('o');
backtrack(subsrc1 + 1, subsrc2 + 1, len);
subsrc2++;
}
while(index < subsrc2) {
s.push(s2[subsrc2 - 1]);
vOfSta.pop_back();
subsrc2--;
}
s.pop();
vOfSta.pop_back();
}
/*
void backtrack(int subsrc, int len)
{
int size = s.size();
if(subsrc < len) {
s.push(s1[subsrc]);
vOfSta.push_back('i');
backtrack(subsrc + 1, len);
} else {
for(int i = 0; i < (int)vOfSta.size(); ++i) cout<<vOfSta[i]<<'_';
for(int i= 0; i < size; ++i) cout<<"o_";
cout<<endl;
return ;
}
if(subsrc + 1 == len) {
s.pop();
vOfSta.pop_back();
return ;
}
stack<char> tmp;
while(!s.empty()) {
tmp.push(s.top());
s.pop();
vOfSta.push_back('o');
backtrack(subsrc + 1, len);
}
while(!tmp.empty()) {
s.push(tmp.top());
tmp.pop();
vOfSta.pop_back();
}
s.pop();
vOfSta.pop_back();
}
*/
/*
*ZOJ 1005
*judge status: Accepted
*language: C++
*run time(ms): 10
*rum Memory(kb): 1388
*/
#include <iostream>
#include <stack>
#include <string>
using namespace std;
const int MAXN = 1002;
bool status[MAXN][MAXN];
stack<string> ans;
bool backtrack(int cA, int cB, int wA, int wB, int n);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int cA, cB, n;
for(int i = 0; i < MAXN; ++i)
for(int j = 0; j < MAXN; ++j)
status[i][j] = false;
while(cin>>cA>>cB>>n) {
if(backtrack(cA, cB, 0, 0, n)){
while(!ans.empty()) {
cout<<ans.top()<<endl;
ans.pop();
}
}
}
return 0;
}
/*以下是对backtrack方法的介绍:
*其中的cA, cB, wA, wB分别表示Jug A的容量,Jug B的容量,Jug A的水量,Jug B的水量;
*其中的status是标记是否遍历过
*1)分别对题中fill A、fill B、empty A、empty B、pour A B、pour B A进行模拟
*2)还原原来的状态
*
*
*
*/
bool backtrack(int cA, int cB, int wA, int wB, int n)
{
if(wA == 0 && wB == n) {
ans.push("success");
return true;
}
if(status[wA][wB]) return false;
status[wA][wB] = true;
if(cA > 0) {
if(backtrack(0, cB, wA + cA, wB, n)) {
ans.push("fill A"), status[wA][wB] = false;
return true;
}
}
if(cB > 0) {
if(backtrack(cA, 0, wA, wB + cB, n)) {
ans.push("fill B"), status[wA][wB] = false;
return true;
}
}
if(wA > 0) {
if(backtrack(cA + wA, cB, 0, wB, n)) {
ans.push("empty A"), status[wA][wB] = false;
return true;
}
}
if(wB > 0) {
if(backtrack(cA, cB + wB, wA, 0, n)) {
ans.push("empty B"), status[wA][wB] = false;
return true;
}
}
if(wA > cB) {
if(backtrack(cA + cB, 0, wA - cB, wB + cB, n)) {
ans.push("pour A B"), status[wA][wB] = false;
return true;
}
}
else if(wA <= cB) {
if(backtrack(cA + wA, cB - wA, 0, wB + wA, n)) {
ans.push("pour A B"), status[wA][wB] = false;
return true;
}
}
if(wB > cA) {
if(backtrack(0, cB + cA, wA + cA, wB - cA, n)) {
ans.push("pour B A"), status[wA][wB] = false;
return true;
}
}
else if(wB <= cA) {
if(backtrack(cA - wB, cB + wB, wA + wB, 0, n)) {
ans.push("pour B A"), status[wA][wB] = false;
return true;
}
}
status[wA][wB] = false;
return false;
}
对于一种思想的描述,我现在只能做到这里了(我也很绝望呀)。
本文标签: Backtracking
版权声明:本文标题:回溯(Backtracking) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728850988a1176676.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论