?? idfs.cpp
字號:
#include "stdafx.h"
#include "idfs.h"
#include "bdfs.h"
extern HASH_BDFS tree_bdfs;
CString IDFS::getIntroduction(){
CString intro = "迭代加深深度優先搜索\r\n\r\n"
"搜索時優先搜索子樹,"
"在迭代步長為1時,保證為最優解。"
"可以在效率與解答之間找到平衡點。";
return intro;
}
int IDFS::search(int begin, int end, int &stop, int val){
if((getreverse(begin) & 1) != (getreverse(end) & 1) ){ //逆序數不一樣,無解
result = NOANSWER;
return -1;
}
std::vector<int> Q;
result = SUCCESS;
open[0].father = -1;
open[0].step = 0;
open[0].status = begin;
int index, tmp;
for(index = 0, tmp = begin; tmp % 10; ++index, tmp /= 10);
open[0].zero = index;
reset(begin, end) - 1; //初始轉換信息
totalnode = 0;
int limit = 0;
while(!stop){
limit ++;
tree_bdfs.reset();
tree_bdfs.add(begin, 0, 0);
Q.push_back(top = 0);
while(!stop && !Q.empty()){
index = Q.back();
Q.pop_back();
if(open[index].status == end){
last_index = index;
totalnode += top;
expanded = totalnode + 1 - Q.size();
inopen = Q.size();
return 1;
}
if(open[index].step >= limit) continue;
int zero = open[index].zero;
for(int i = 0; i < dir_count[zero]; i++){
int tmp = getnextstatus(open[index].status, zero, dir[zero][i]);
int newindex = tree_bdfs.add(tmp, top + 1, open[index].step + 1);
if(newindex == 0){
open[++top].father = index;
open[top].status = tmp;
open[top].step = open[index].step + 1;
open[top].zero = dir[zero][i];
Q.push_back(top);
}else if(newindex > 0){
open[newindex].father = index;
open[newindex].step = open[index].step + 1;
Q.push_back(newindex);
}
}
}
totalnode += top + 1;
}
expanded = top + 1 - Q.size();
inopen = Q.size();
if(stop){
result = STOP;
return -2;
}
result = CANTFIND;
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -