Posted on 2013-06-14 20:30
happyac 阅读(1137)
评论(0) 编辑 收藏 引用 所属分类:
uva
总结
搜索问题,按深度优先的思路可以顺利通过。
分析
要求按字母序输出所有可能的解。思路如下:
- 假设最后的输出保存在 $order[0\dots n]$ 的数组中,第 $n$ 层迭代确定数组的第 $n$ 个元素,全部确定之后就输出,然后回溯。
- 进入第 $k$ 层迭代,假设当前元素为 $S = \{a,b,c,d,e\}$,当前规则为 $R = \{a<b, c<d\}$。有两个步骤:
- 选择第 $k$ 个元素。除当前出现在规则右边的元素之外,依字母选择。可选的元素是 $S^\prime = \{a,c\}$。
- 依次从 $S^\prime$ 中选取元素,例如 $a$,从 $S$ 中去掉已经选择的元素,然后去掉 $a$ 对应的规则,即 $R=\{c<d\}$,然后进行下一层迭代