ACM 国际大学生程序设计竞赛系列讲座
-------------- 通用搜索算法及实现
王岩冰
目录
1. 组合问题的通用搜索算法
1.1 状态空间树的搜索
1.2 状态空间的原地搜索和展开搜索
1.3 基于遍历器的搜索
2. 优化问题的通用搜索算法
2.1 加权状态空间树的搜索
2.2 加权状态空间的原地搜索和展开搜索
状态空间树的搜索
public interface Node { int subnodenum(); boolean target();
Node down(int i); void output(boolean cn); }
public interface Mono extends Node { Node up(); }
public class Backtracking {Mono prob; int num, bound, dep, level;
public Backtracking(Mono p, int b, int d){ prob=p; bound=b; dep=d; }
public void depthfirst(){ int n=prob.subnodenum();
if (prob.target()){ prob.output(true); ++num; }
for (int i=0; num<bound && i<n; ++i)
if (prob.down(i)!=null){ depthfirst(); prob.up(); } }
}
N 皇后问题
public class Queens1 implements Mono { int n, level; int[] board;
PrintWriter out; boolean[] column, d1, d2;
public Queens1(int k, PrintWriter o){ n=k; board=new int[n]; out=o;
column=new boolean[n]; d1=new boolean[2*n-1]; d2=new boolean[2*n-1]; }
public Node down(int i){ Queens1 ans=null;
if (level<n && !column[i] && !d1[level+i] && !d2[level-i+n-1]){
column[i]=d1[level+i]=d2[level-i+n-1]=true; board[level++]=i; ans=this; }
return ans; }
public Node up(){ int i=board[--level]; column[i]=d1[level+i]=d2[level-i+n-1]
=false; return this; }
public int subnodenum(){ return level<n ? n : 0; }
public boolean target(){ return level==n; }
}
N 皇后问题
public class Queens implements Mono {int n, level; int[] board;
PrintWriter out;
public Queens(int k, PrintWriter o){ n=k; board=new int[n]; out=o; }
public Node down(int i){ Queens ans=null; boolean norm=level<n;
for (int k=level-1; norm && k>=0; --k) norm = i!=board[k] &&
i+level-k!=board[k] && i-level+k!=board[k];
if (norm){ board[level++]=i; ans=this; } return ans; }
public Node up(){ --level; return this; }
public int subnodenum(){ return level<n ? n : 0; }
public boolean target(){ return level==n; }
}
