几个回溯算法的例子

几个回溯算法的例子

1. n后放置

由题意可知，其解为四维向量

其搜索空间为：

4叉树

2. 0-1背包

一定要注意对搜索空间的了解：

为什么只有两个方块呢，因为回溯发现，其他分支内的解没有这两个解好。

3. 货郎问题

这里的min函数表示走一圈的距离，d(ck1,ck2)+d(ck2,ck3)+d(ck3,ck4),d(ckn-1,ckn)+d(ckn,ck1)

在此特别强调，解的形式和约束条件是建模中最重要的东西。

对于货郎问题的实例，首先要给出所有的城市两辆之间的距离。
同时易知解向量形式为四维向量（怎么走）

都是可行解，选其中的最优解。在这里假设是从一号城市开始的。所以一开始是一分叉的

总结

1. 解都是向量
2. 搜索空间都是树结构，货郎问题为排列树，0-1背包问题是子集树、n皇后问题是n叉树，其差别在于分叉的规则不一样。n叉树，每次分n个叉，子集树： 当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间称为子集树，分叉规则视具体情况确定，0-1背包问题就是分2叉。
例如，那个物品的0-1背包问题所相应的解空间树就是一颗子集树。这类子集问题通常有2^{n个叶节点，其节点总个数为2}(n+1)-1。遍历子集树的任何算法均需要O(2^n)的计算时间。
排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶子节点。
4. 树的节点是向量的前部分，可行解在叶节点，最优解在可行解中找
5. 搜索算法有：深度优先、宽度优先、…跳跃式遍历搜索算法从而找到解