ACM国际大学生程序设计竞赛系列讲座-通用搜索算法及实现.PPT

1、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(); pub

2、lic 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; numbound ,N皇后问题,public class Queens1 implements Mono int n, level

3、; int board; PrintWriter out; boolean column, d1, d2; public Queens1(int k, PrintWriter o) n=k; board=new intn; out=o; column=new booleann; d1=new boolean2*n-1; d2=new boolean2*n-1; public Node down(int i) Queens1 ans=null; if (leveln ,N皇后问题,public class Queens implements Mono int n, level; int boar

4、d; PrintWriter out; public Queens(int k, PrintWriter o) n=k; board=new intn; out=o; public Node down(int i) Queens ans=null; boolean norm=level=0; -k) norm = i!=boardk ,点着色问题,例(点着色问题)用n种颜色给无向图的顶点着色，要求相邻顶点颜色不同。求符合条件的一个着色方法。 public class ColorClass implements Mono int m, n, level; List graph; int perm

5、=new intm; public boolean target() return level=m; public int subnodenum() return level=level | permk!=i; if (ans) permlevel+=i; return this; else return null; public Node up() -level; return this; ,排列树的搜索,public interface PerNode int depth(); PerNode down(int i); void output(boolean cn); public int

6、erface PerMono extends PerNode PerNode up(); ,排列树的搜索,public class PerBacktracking PerMono prob; int perm; int dep, num, bound, level; public PerBacktracking(PerMono p, int b) prob=p; bound=b; dep=p.depth(); perm=new intdep; for (int i=0; idep; +i) permi=i; public void depthfirst() if (level=dep) pro

7、b.output(true); +num; else for (int i=level; num=rowx ,非递归的状态空间树的搜索,public class MonoSearch Mono prob; Link head; int path, wids; int num, wid, dep, level; static class Link public int cur, bound; public Link next; public Link(int c, int b, Link n) cur=c; bound=b; next=n; public void find(int k) whi

8、le (head!=null ,状态空间的有关定义,定义 （状态空间）一个状态空间是四元组ES=，其中V是非空有限的结点集，EV2是边集合，q0V是初始结点， TV是目标结点集，并且对每个vV，q0到v在中有一条有向路. 定义（展开树）设ES=为一个显式空间，令V=|为中由q0出发的有向路，E=|,V,是的前缀且Dom()+1= Dom()，T=|V tail()T, 则ES=构成一个树形显式空间，称为ES的展开树。 ,状态空间的有关定义,定义（隐式空间）一个隐式空间是五元组S =,其中V是非空有限的结点集, q0V是初始结点,T V是目标结点集,C,F是V上的函数，对于vV,C(v)是有限全

9、序集，称为v的子节点指针集，F(v)是C(v)到V的一一部分函数，称为v的子节点计算函数。如果每个节点的子节点指针集是作为有限序数的自然数，则称S为正规隐式空间。 定义1.3（导出空间）设S=为一个状态空间，令E=|u,vVvRng(F(u),为q0在中导出的单向连通分支，T=TV,则ES=构成一个状态空间，称为S的导出空间, ES中从q0出发到T中结点的有向路径称为S的一个解。 ,状态空间的有关定义,定义（展开空间）设S=为一个状态空间，令V=|V+(0)=q0m,nDom()mn(m)(n),C:VRng(C),对V, C()=C(tail(), F是V上的函数,对于V, F():C()V

10、,对xC()，若F(tail()(x)=或mDom()F(tail()(x)=(m),则F()(x)=,否则F()(x)=*F(tail()(x)（*表示并置运算），T=|V tail()T, 则S=构成一个状态空间，称为S的展开空间, S的展开空间的导出空间称为S的展开导出空间。 ,利用展开树的搜索,public class Back Link head; int num, bound, dep, level; private static class Link public Node prob; public Link next; public Link(Node p, Link n) p

11、rob=p; next=n; public void output(boolean b) if (next!=null) next.output(false); prob.output(b); public Back(Node p, int b) head=new Link(p, null); bound=b; public void depthfirst() Node p=head.prob, sub=null; int n=p.subnodenum(); if (p.target() if (head.next!=null) head.output(true); +num; for (in

12、t i=0; numbound ,N皇后问题,public class Queens2 implements Node static int n; static PrintWriter out; int level; int board; public Queens2(int k, PrintWriter o) n=k; board=new int1; out=o; public Queens2(int lev, int b) level=lev; board=new intlevel+1; System.arraycopy(b, 0, board, 0, level); public Nod

13、e down(int i) Queens2 ans=null; boolean norm=level=0; -k) norm=i!=boardk ,子集和数问题,例 (子集和数问题)设A是N个正整数组成的集合，sum，求A 的一个子集，使它的元素和为sum。 public class SubsetClass implements Node static int m, tarsum; static int data, sumarray; int name=-1, cursum; public boolean target() return cursum=tarsum; public int su

14、bnodenum() return m-name-1; public Node down(int i) SubsetClass ans=null; int k=name+i+1; if (cursum+datak=tarsum) ans=new SubsetClass(); ans.name=k; ans.cursum=cursum+dataans.name; return ans; ,状态空间的原地搜索,public class GraphBack private Link head; private int num, bound; private Set nodeset; private

15、static class Link public Node prob; public Link next; public Link(Node p, Link n) prob=p; next=n; public void output(boolean b) if (next!=null) next.output(false); prob.output(b); public GraphBack(Node p, int b, Set s) head=new Link(p, null); bound=b; nodeset=s; nodeset.add(p); public void depthfirs

16、t() Node p=head.prob, sub=null; int n=p.subnodenum(); if (p.target() head.output(true); +num; for (int i=0; numbound ,水杯问题,例 (水杯问题) 设有两个水杯A和B容量分别为M、N(0MN100,M,N)。有三种类型的动作：第一种是将一个水杯注满水；第二种是将水杯的水倒掉，第三种是将一个杯子中的水注到另一个杯子中，直到倒空或被注满。设开始是两个杯子都为空，目标状态是水杯B装有容积为K(K)的水，求一个符合要求的动作序列。,水杯问题,public class Cup implem

17、ents Node static int v1, v2, tar; int c1, c2; public boolean target() return c1=tar; public int subnodenum() return 6; public Node down(int i) int k=i=4 ? (c1v2-c2 ? c1 : v2-c2) : i=5 ? (c2v1-c1 ? c2 : v1-c1) : 0; Cup ans=new Cup(); ans.c1=i=0 ? v1 : i=2 ? 0 : i=4 ? c1-k : i=5 ? c1+k : c1; ans.c2=i=

18、1 ? v2 : i=3 ? 0 : i=4 ? c2+k : i=5 ? c2-k : c2; return ans; ,布线问题,例 (布线问题) 印刷电路板将布线区域划分成nm个方格阵列，要求确定连接方格a的中点到方格b的中点的布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布线了的方格作了封锁标记，其他线路不允许穿过被封锁的方格。,布线问题,public class Lining implements Node static int row, column, soux, souy, tarx, tary; static final int move=0, -1, 0,

19、 1, -1, 0, 1, 0; static boolean board; int x, y; public boolean target() return x=tarx ,用布尔函数实现集合,public interface Unary int tag(); public interface Pair int tag1(); int tag2(); public class Bvector implements Set private boolean set; public Bvector(int len) set=new booleanlen; public int size() int

20、 ans=0; for (int i=0; i=0 ,用布尔函数实现集合,public class Bmatrix implements Set private boolean set; public Bmatrix(int row, int column) set=new booleanrowcolumn; public int size() int ans=0; for (int i=0; iset.length; +i) for (int j=0; jseti.length; +j) if (setij) +ans; return ans; public boolean isEmpty(

21、) for (int i=0; iset.length; +i) for (int j=0; j=0 ,状态空间的展开搜索,public class LabelBack Link head; int num, bound, dep, wid, level; Set nodeset; Node probs; private static class Link public Node prob; public Link next; public Link(Node p, Link n) prob=p; next=n; public void output() if (next!=null) nex

22、t.output(); prob.output(false); public LabelBack(Node p, int b, Set s) head=new Link(p, null); bound=b; nodeset=s; nodeset.add(p); public void depthfirst() Node p=head.prob, sub=null; int n=p.subnodenum(); if (p.target() if (head.next!=null) head.next.output(); head.prob.output(true); +num; for (int

23、 i=0; numbound ,跳马问题,public class Knight3 implements Node, Pair static int move; static int m, n; static PrintWriter out; static int board; int level, x, y; public Knight3(int mm, int nn, int mov, PrintWriter o) m=mm; n=nn; out=o; move=mov; board=new intmm; level=1; public Knight3(int lev, int xx, i

24、nt yy) level=lev; x=xx; y=yy; public boolean target() return level=m*m; public int subnodenum() return level=0 ,矩阵图的搜索,public class Allpath implements Node, Unary static int m; static int g; int name; static PrintWriter out; public Allpath(int mm, int n, int gg, PrintWriter o) m=mm; name=n; g=gg; ou

25、t=o; public Allpath(int n) name=n; public boolean target() return true; public int subnodenum() return m; public void output(boolean cn) out.print(name+, ); if (cn) out.println(); public Node down(int i) return gnamei!=0 ? new Allpath(i) : null; public int tag() return name; ,矩阵图的Hamilton判定,public c

26、lass Hamilton extends Allpath private int level; public Hamilton(int mm, int gg, PrintWriter o) super(mm, 0, gg, o); public Hamilton(int n, int lev) super(n); level=lev; public boolean target() return level=m-1; public Node down(int i) return gnamei!=0 ? new Hamilton(i, level+1) : null; ,基于遍历器的回溯,pu

27、blic interface ItrNode ItrNode down(Object ob); void output(boolean cn); Iterator subnodes(); boolean target(); public interface ItrMono extends ItrNode ItrNode up(); public class ItrBacktracking private ItrMono prob; private int num, bound, dep, level; public ItrBacktracking(ItrMono p, int b) prob=

28、p; bound=b; if (p instanceof FixDepItrMono) dep=(FixDepItrMono)p).depth(); public void depthfirst() Iterator nodes=prob.subnodes(); if (prob.target() prob.output(true); +num; while (numbound ,Domino骨牌,Domino骨牌,Domino骨牌,public class DominoClass implements ItrMono int n, dep, level; int bone, allot, b

29、oard, ansboard; PrintWriter out; boolean set; LinkedList choice; public DominoClass(int nn, int b, PrintWriter o) n=nn; dep=n*(n+1)/2; board=b; out=o; ansboard=new intnn+1; allot=new intdep3; bone=new intnn; int num=0; for (int i=0; in; +i) for (int j=i; jn; +j) boneij=boneji=num+; set=new booleannn

30、+1; choice=new LinkedListdep+1; for (int i=0; i=dep; +i) choicei=new LinkedList(); for (int i=0; in; +i) for (int j=0; jn; +j) int k=boneboardijboardij+1; int node=new int3; node0=i; node1=j; node2=0; choicek.add(node); for (int i=0; in-1; +i) for (int j=0; j=dep; public Iterator subnodes() return c

31、hoicelevel.iterator(); public ItrNode down(Object o) int node=(int)o; int x=node0, y=node1; boolean horizon=node2=0; DominoClass ans=null; boolean norm=horizon ? !setxy ,0-1矩阵问题,public class Bitm implements ItrMono int m, n; int row, column; int data; int count; int level; public boolean target() re

32、turn level=m; public Iterator subnodes() return new Iterator() private boolean hasn=true; private int com=new introwlevel; for (int i=0; i=0; -i) q=comin-rowlevel+i; if (!q) hasn=false; else +comi+1; for (int j=i+2; jrowlevel; +j) comj=comj-1+1; return ans; public void remove() ; ,0-1矩阵问题,public Itr

33、Node down(Object o) boolean res=true; int cur=(int)o; Arrays.fill(datalevel, 0, n, 0); for (int j=0; jrowlevel; +j) datalevelcurj=1; for (int i=0; res ,基于遍历器的原地搜索,public class GraphItrBack Link head; int num, bound; Set nodeset; static class Link public ItrNode prob; public Link next; public Link(It

34、rNode p, Link n) prob=p; next=n; public void output() if (next!=null) next.output(); prob.output(false); public GraphItrBack(ItrNode p, int b, Set s) head=new Link(p, null); bound=b; nodeset=s; nodeset.add(p); public void depthfirst() ItrNode p=head.prob, sub=null; Iterator nodes=p.subnodes(); if (p

35、.target() if (head.next!=null) head.next.output(); head.prob.output(true); +num; while (numbound ,基于遍历器的展开搜索,public class LabelItrBack Link head; int num, bound, dep, level; Set nodeset; private static class Link public ItrNode prob; public Link next; public Link(ItrNode p, Link n) prob=p; next=n; p

36、ublic void output() if (next!=null) next.output(); prob.output(false); public LabelItrBack(ItrNode p, int b, Set s) head=new Link(p, null); bound=b; nodeset=s; nodeset.add(p); public void depthfirst() ItrNode p=head.prob, sub=null; Iterator nodes=p.subnodes(); if (p.target() if (head.next!=null) hea

37、d.next.output(); head.prob.output(true); +num; while (numbound ,邻接表图的搜索,public class Allpath1 implements ItrNode, Unary static int m; static LinkedList g; int name; static PrintWriter out; public Allpath1(int mm, int n, LinkedList gg, PrintWriter o) m=mm; name=n; g=gg; out=o; public Allpath1(int n)

38、name=n; public boolean target() return true; public Iterator subnodes() return gname.iterator(); public void output(boolean cn) out.print(name+, ); if (cn) out.println(); public ItrNode down(Object o) return new Allpath1(Integer)o).intValue(); public int tag() return name; ,加权状态空间树的搜索,public interfa

39、ce Node extends Comparable int subnodenum(); boolean target(); Node down(int i); void output(boolean cn); public interface Mono extends Node, Cloneable Node up(); Object clone(); public class Backtracking Mono prob, ans; int dep, level; public Backtracking(Mono p) prob=p; public void depthfirst() int n=prob.subnodenum(); if (prob.target() ,