回溯huisu

搜索算法中的一种控制策略.如图所示，画出了一个树结构，每个结点是一个房间，房间之间的连通关系由枝来表示.对外界而言，假定只有A房间有入口，G房间有出口.让一个生人走进这座建筑物，再走出这座建筑物，得有策略.从入口进入A房间后，遇到两条通道，先选左面的通道进入B房间，又遇到三条通道，还是先左，再中，再右试走，分别走进D,E,F房间，都没有出口，返回B，再返回A.从房间A寻找另外的出路.这一过程叫回溯.形象点说，不识路的人走进了死胡同，再从中退出来去试走另一条路，称之为回溯法.

本例的试探搜索的步骤用虚线加箭头标在图上.结点B,D,E,F构成以A为根的树的一个枝杈，开始先走这个枝杈(从第1,2，…，到第7步)，走不通了，由第8步返回A，再走另一枝杈(由C,G,H组成)，经第9,10步就可觅到出口.许多问题的求解过程都会用到这种回溯探索的控制策略.