为什么回溯法比穷举法效率高
来源:学生作业学帮网 编辑:学帮网 时间:2024/05/30 20:29:10
为什么回溯法比穷举法效率高
因为回溯法在搜索过程中一旦发现有冲突,它就及时“剪枝”,避免了大量无谓的搜索,所以大大提高了搜索效率.以8皇后问题为例:当第一行皇后放在第2列时,第二行的皇后只能从第4列开始尝试搜索,只用了3次判断就排除了第2个皇后在1,2,3列上时,后面剩余6个皇后所有可能的穷举方案3*8^6种.
收录互联网各类作业题目,免费共享学生作业习题
慧海网手机作业共收录了 千万级 学生作业题目
来源:学生作业学帮网 编辑:学帮网 时间:2024/05/30 20:29:10
为什么回溯法比穷举法效率高
因为回溯法在搜索过程中一旦发现有冲突,它就及时“剪枝”,避免了大量无谓的搜索,所以大大提高了搜索效率.以8皇后问题为例:当第一行皇后放在第2列时,第二行的皇后只能从第4列开始尝试搜索,只用了3次判断就排除了第2个皇后在1,2,3列上时,后面剩余6个皇后所有可能的穷举方案3*8^6种.