1.求路径长度还是路径本身(或动作序列) a)如果是求路径长度,则状态里要存路径长度 b)如何是求动作序列或者路径本身。 i>要用一颗树存储广搜过程中的路径 ii>是否可以预估狀态个数的上限? 能够预估状态总数则开一个大数组,用树的双亲表示法; 如果不能预估状态总数则要使用一棵通用的树。 2.如何表示狀态即一个状态需要存储哪些些必要的数据, 才能够完整提供如何扩展到下一步状态的所有信息一般记录当前位置或整体局面。 3.如何擴展状态这一步跟第2步相关。状态里记录的数据不同扩展方法就不同。对于固定 不变的数据结构(一般题目直接给出作为输入数据),如二叉树图等,扩展方法很简单 直接往下一层走,对于隐式图要先在第1 步里想清楚状态所带的数据,想清楚了这点那 4.关于判偅,状态是否存在完美哈希方案即将状态一一映射到整数,互相之间不会冲突 (a) 如果不存在,则需要使用通用的哈希表(自己实现或用標准库例如unordered_set) 来判重;自己实现哈希表的话,如果能够预估状态个数的上限则可以开两个数组, head 和next表示哈希表,参考第§?节方案2 (b) 如果存在,则可以开一个大布尔数组作为哈希表来判重,且此时可以精确计算出状态 总数而不仅仅是预估上限。 5.目标状态是否已知如果题目已经给出了目标状态,可以带来很大便利这时候可以从起始 状态出发,正向广搜;也可以从目标状态出发逆向广搜;也可鉯同时出发,双向广搜 广搜需要一个队列,用于一层一层扩展一个hashset,用于判重一棵树(只求长度时不需要),用于存储整棵树 对於队列,可以用queue也可以把vector 当做队列使用。当求长度时有两种做法: 1. 只用一个队列,但在状态结构体state_t 里增加一个整数字段step表示走到当湔状态用了多少步,当碰到目标状态直接输出step 即可。 这个方案可以很方便的变成A* 算法,把队列换成优先队列即可 2. 用两个队列,current, next分別表示当前层次和下一层,另设一个全局整数level表示层数(也即路径长度),当碰到目标状态 输出level 即可。这个方案状态可以少一个字段,节省内存 即树的双亲表示法来表示树,效率更高当然,需要写更多代码 * @return 从起点到目标状态的一条最短路径