关于本章
本章给出backtracking算法的例子。
| 例子 | 解空间 | 说明 |
|---|---|---|
| 5.2装载问题 | 组合树 | 每个集装箱有两种选择：装入船1或者船2 |
| 5.3批处理作业调度 | 组合树 | 每个作业有两种选择：使用机器1或者机器2 |
| 5.4符号三角形问题 | 组合树 | 第一排的每个位置有两个选择：放置正号或者负号 |
| 5.5n后问题 | 组合树 | 每一行有n个选择：n个皇后之一 |
| 5.6 0-1背包问题 | 组合树 | 每个背包有两个选择：装入或者不装入 |
| 5.8图的m着色问题 | 组合树 | 每个点有m种选择：m种颜色之一 |
| 5.10 圆排列问题 | 排列树 | 非常典型的排列问题：第一个位置有n种选择，第二个位置有n-1种选择，......，最后一个位置只有一个选择 |
| 5.11电路板排列问题 | 排列树 | 非常典型的排列问题 |
| 5.9旅行售货员问题 | 排列树 | 不是非常典型的排列树问题 |