python 回溯法 子集树模板 系列 —— 15、总结

简介: 作者:hhh5460时间:2017年6月3日用回溯法子集树模板解决了这么多问题,这里总结一下使用回溯法子集树模板的步骤:1、确定元素及其状态空间(精髓)对每一个元素,遍历它的状态空间,其它的事情交给剪枝函数!!!(正是这一点,使得它无愧于“通用解题法”这个称号!)2、确定解的编码及解的长度是否固定若解的长度固定,那么x[k] = i若解的长度不固定,那么x.

作者:hhh5460
时间:2017年6月3日

用回溯法子集树模板解决了这么多问题,这里总结一下使用回溯法子集树模板的步骤:

1、确定元素及其状态空间(精髓)

对每一个元素,遍历它的状态空间,其它的事情交给剪枝函数!!!(正是这一点,使得它无愧于“通用解题法”这个称号!)

2、确定解的编码及解的长度是否固定

若解的长度固定,那么x[k] = i

若解的长度不固定,那么x.append(i) ... x.pop(i)

3、确定是求最优解,任一解,还是全部解

如果是求最优解,额外增加两个全局变量:best_x, best_value

4、问题是否有其特殊性

是的话,想法解决之

最后强调一下:

精髓 —— 元素-状态空间分析大法

  • 对每一个元素,遍历它的状态空间,其它的事情交给剪枝函数!
目录
相关文章
|
Python 机器学习/深度学习 安全
python 回溯法 子集树模板 系列 —— 19、野人与传教士问题
问题 在河的左岸有N个传教士、N个野人和一条船,传教士们想用这条船把所有人都运过河去,但有以下条件限制: (1)修道士和野人都会划船,但船每次最多只能运M个人; (2)在任何岸边以及船上,野人数目都不能超过修道士,否则修道士会被野人吃掉。
1357 0
|
Python 数据可视化
python 回溯法 子集树模板 系列 —— 1、8 皇后问题
问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0、1、2、...、7列,我们认为每一行的皇后有8种状态。
960 0
|
1天前
|
机器学习/深度学习 人工智能 数据可视化
Python比较适合哪些场景的编程?
Python比较适合哪些场景的编程?
14 7
|
6天前
|
数据挖掘 索引 Python
Python数据挖掘编程基础3
字典在数学上是一个映射,类似列表但使用自定义键而非数字索引,键在整个字典中必须唯一。可以通过直接赋值、`dict`函数或`dict.fromkeys`创建字典,并通过键访问元素。集合是一种不重复且无序的数据结构,可通过花括号或`set`函数创建,支持并集、交集、差集和对称差集等运算。
15 9
|
2天前
|
存储 数据处理 开发者
深入浅出:Python编程基础与实战技巧
【9月更文挑战第32天】本文将引导读者从零开始,掌握Python编程语言的核心概念,并通过实际代码示例深入理解。我们将逐步探索变量、数据结构、控制流、函数、类和异常处理等基本知识,并结合实用案例,如数据处理、文件操作和网络请求,提升编程技能。无论您是初学者还是有一定经验的开发者,这篇文章都能帮助您巩固基础,拓展视野。
|
1天前
|
大数据 Python
Python 高级编程:深入探索高级代码实践
本文深入探讨了Python的四大高级特性:装饰器、生成器、上下文管理器及并发与并行编程。通过装饰器,我们能够在不改动原函数的基础上增添功能;生成器允许按需生成值,优化处理大数据;上下文管理器确保资源被妥善管理和释放;多线程等技术则助力高效完成并发任务。本文通过具体代码实例详细解析这些特性的应用方法,帮助读者提升Python编程水平。
18 5
|
2天前
|
数据采集 机器学习/深度学习 人工智能
Python编程之旅:从基础到精通
【9月更文挑战第32天】本文将带你进入Python的世界,从基础语法到高级特性,再到实战项目,让你全面掌握Python编程技能。无论你是初学者还是有一定基础的开发者,都能在这篇文章中找到适合自己的学习路径和方法。让我们一起踏上Python编程之旅,开启一段充满挑战和乐趣的学习历程吧!
|
5天前
|
存储 开发者 Python
探索Python编程的奥秘
【9月更文挑战第29天】本文将带你走进Python的世界,通过深入浅出的方式,解析Python编程的基本概念和核心特性。我们将一起探讨变量、数据类型、控制结构、函数等基础知识,并通过实际代码示例,让你更好地理解和掌握Python编程。无论你是编程新手,还是有一定基础的开发者,都能在这篇文章中找到新的启示和收获。让我们一起探索Python编程的奥秘,开启编程之旅吧!
|
6天前
|
Python
Python编程的循环结构小示例(二)
Python编程的循环结构小示例(二)
|
6天前
|
算法 Python
Python编程的函数—内置函数
Python编程的函数—内置函数
10 0
下一篇
无影云桌面