六.回溯法

概念

回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件是，就"回溯"返回，尝试别的路径。

回溯法是一种优先搜索法，按优先条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为"回溯点"。许多复杂的，规模较大的问题都可以使用回溯法，有"通用解题方法"的美称。

思想策略

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根节点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先探索算法）。若用回溯法求问题的所有解时，要回溯到根，且根节点的所有可行的子树都要已被搜索遍才结束。

特征

• 1.针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
• 2.确定结点的扩展搜索规则。
• 3.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

适用回溯法求解的经典问题

• 八皇后问题
• 图的着色问题
• 装载问题
• 批处理作业调度问题
• 再再论背包问题
• 最大团问题
• 连续邮资问题
• 符号三角形问题

1.n 皇后问题

在一个 n*n 的棋盘上放置皇后，要求：一个皇后的同一行、同一列、同一条对角线上不允许出现其他皇后。请给出所有的放置方案。

<template>
  <table>
    <tr v-for="(item, index) in arr" :key="index">
      <th v-for="(data, i) in item" :key="i">{{ data }}</th>
    </tr>
  </table>
</template>
<script>
export default {
  data: () => ({
    arr: [
      ["", "", "", ""],
      ["", "", "", ""],
      ["", "", "", ""],
      ["", "", "", ""],
    ],
  }),
}
</script>

显示代码 复制代码 复制代码

89

<template>
  <div>
    <input style="width:100%" v-model="str" placeHolder="请输入值" />
    <br />
    <button @click="handleClick" style="margin-top:10px;text-align:center">
      确定
    </button>
    <div class="box-vue">{{ message }}</div>
  </div>
</template>
<script>
let targetArithmetic = (m) => {
  if (m === 1 || m === 2) return m
  return targetArithmetic(m - 1) + targetArithmetic(m - 2)
}
export default {
  data: () => ({
    str: "10",
    message: "",
  }),
  created() {
    this.handleClick()
  },
  methods: {
    handleClick() {
      this.message = targetArithmetic(+this.str)
      console.log(this.message)
    },
  },
}
</script>

显示代码 复制代码 复制代码