不撞南墙不回头——树规总结
焦作一中信息学
oy
之所以这样命名树规,是因为树规的这一特殊性:没有环,
dfs
是不会重复,而且具有
明显而又严格的层数关系?/p>
利用这一特性,
我们可以很清晰地根据题目写出一个在?/p>
(型?/p>
构)上的记忆化搜索的程序。而深搜的特点,就是“不撞南墙不回头?/p>
。这一点在之后的文
章中会详细的介绍?/p>
首先是扫盲,
介绍几条名词的专业解释以显示我的高端
(大部分人可以略过,
因为学习
到树规的人一下应该都懂„„)
?/p>
动态规划:
问题可以分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决?/p>
是一个决策序列。要使整个活动的总体效果达到最优的问题,称为多阶段决策问题。动?/p>
规划就是解决多阶段决策最优化问题的一种思想方法?/p>
阶段?/p>
将所给问题的过程,按时间或空间(树归中是空间,即层数)特征分解成若干相互?/p>
系的阶段,以便按次序去求每阶段的解?/p>
状态:
各阶段开始时的客观条件叫做状态?/p>
决策?/p>
当各段的状态取定以后,就可以做出不同的决定,从而确定下一阶段的状态,这种?/p>
定称为决策?/p>
(即孩子节点和父亲节点的关系?/p>
策略?/p>
由开始到终点的全过程中,由每段决策组成的决策序列称为全过程策略,简称策略?/p>
状态转移方程:
前一阶段的终点就是后一阶段的起点,前一阶段的决策选择导出了后一阶段的状态,
这种关系描述了由
k
阶段?/p>
k+1
阶段(在树中是孩子节点和父亲节点)状态的演变规律?/p>
称为状态转移方程?/p>
目标函数与最优化概念?/p>
目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个?/p>
径,经过按题目具体性质所确定的运算以后,使全过程的总效益达到最优?/p>
树的特点与性质?/p>
1
?/p>
?/p>
n
个点?/p>
n-1
条边的无向图,任意两顶点间可?/p>
2
?/p>
无向图中任意两个点间有且只有一条路
3
?/p>
一个点至多有一个前趋,但可以有多个后继