动态规划的关键算法

动态规划的关键算法Mf1432075许耀峰组号：201.背景介绍1.1PostgresSQL中的动态规划算法所谓基于代价的动态规划算法，就是穷举所有可能的查询的可执行的方法，估算它们的代价，找出一个代价嘴角的来执行，这是物理层次的优化。在PostgresSQL中，基于代价的动态规划算法应用在物理查询优化阶段求解最优的多表连接路径。1.2物理查询优化在查询优化器实现的早期，使用的是逻辑优化技术，即使用关系代数规则和启发式规则对查询进行优化后，认为生成的执行计划就是最优的。在引入了基于代价的查询优化方式后，对查询执行计划做了定量的分析，对每一个可能的执行方式进行评估，挑出代价最小的作为最优的计划。目前，数据库的查询优化器通常融合了这两种方式。2.多表连接查询多表连接算法实现的是在查询路径生成的过程中，根据代价估算，从各种可能的候选路径中找出最优的路径（最优路径是代价最小的路径）。多表连接算法需要解决两个问题：（1）多表连接的顺序：表的不同的连接顺序，会产生许多不同的连接路径；不同的连接路径有不同的效率。（2）多表连接的搜索空间：因为多表连接的顺序不同，产生的连接组合会有多种，如果这个组合的数目巨大，连接次数会达到一个很高的数量级，最大可能的连接次数是N！（N的阶乘）2.1多表连接顺序多表间的连接顺序表示了查询计划树的基本形态。一棵树就是一种查询路径，SQL的语义可以由多棵这样的树表达，从中选择花费最少的树，就是最优查询计划形成的过程。而一棵树包括左深连接树、右深连接树、紧密树3种形态。另外，即使是同一种树的生成方式，也有细节需要考虑。在图3-1a中，{A，B}和{B，A}两种连接方式花费可能不同。比如最终连接结果是{A，B，C}，但是需要验证是{A，B，C}、{A，C，B}、{B，C，A}、{B，A，C}、{C，A，B}、{C，B，A}中哪一个连接方式得到的结果，这就要求无论是哪种结果，都需要计算这6种连接方式中每一种的花费，找出最优的一种作为下次和其他表连接的依据。人们针对以上树的形成、形成的树的花费代价最少的，提出了诸多算法。树的形成过程，主要有以下两种策略：（1）至顶向下。从SQL表达式树的树根开始，向下进行，估计每个结点可能的执行方法，计算每种组合的代价，从中挑选最优的。（2）自底向上。从SQL表达式树的树叶开始，向上进行，计算每个子表达式的所有实现方法的代价，从中挑选最优的，再和上层（靠近树根）的进行连接，周而复始直至树根。2.2常用的多表连接算法表与表进行连接，对多表连接进行搜索查找最优查询树，通常有多种算法，比如启发式、分枝界定计划枚举、爬山法、动态规划、SystemR优化方法等。3.动态规划算法3.1简介20世纪40年代，RichardBellman最早使用了动态规划这一概念，用以表述通过遍历寻找最优决策解问题。“动态规划”（dynamicprogramming）中的programming来自“数学规划”（mathematicalprogramming，又称规划），与“计算机编程”（computerprogramming）中的programming没有关系。规划的含义是指生成活动的优化策略，规划意味着找到一个可行的活动计划。动态规划，是指决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，这就是“动态”的含义。“动态规划”将待求解的问题分解为若干个子问题（子阶段），按顺序求解子问题，前一子问题的解为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。3.2动态规划的概念i.阶段。把求解问题的过程分成若干个相互联系的阶段，以便于求解。在多数情况下，阶段变量是离散的。ii.状态。表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。iii.无后效性。状态应该具有的性质，如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。iv.决策。一个阶段的状态确定后，从该状态演变到下一阶段某个状态的选择（行动）称为决策。v.策略。由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。vi.最优化原理。如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。最优化原理实际上是要求问题的最优策略的子策略也是最优的。3.3动态规划的具体实现在数据库领域，动态规划算法主要解决的是多表连接的问题。动态规划算法是从底向上进行的，即从叶子（单个表）开始算作一层，然后由底层开始对每层的关系做两两连接（如果满足内连接则两两连接，不满足内连接则不可对全部表进行两两连接操作），构造出上层，逐次递推到树根。下面介绍具体步骤。步骤1初始状态。构造第一层关系，即叶子结点，每个叶子对应一个单表，为每一个待连接的关系计算最优路径（单表的最优路径就是单表的最佳访问方式，通过评估不同的单表的数据扫描方式花费，找出代价最小的作为每个单表的局部最优路径）。步骤2归纳。当层数从第1到n-1，假设已经生成，则如何求解第n层的关系方法有：（1）左深树连接方式：将第n-1层的关系（有多个关系）与第一层中的每个关系连接，生成新的关系（对新关系的大小进行估算），放于第n层，且每一个新关系，均求解其最优路径。（2）紧密树连接方式：将第k层的关系每个关系，与第other_level层中的每个关系连接，生成新的关系（新的关系就存储着形成这个关系的多种局部路径，从中选出最优的一个局部路径）放于第n层，且每一个新的关系，均求解其最优路径。其中other_level=level–k，level为要连接的基表个数。以上虽然分为两步，但实际上步骤2多次执行，每一次执行后生成的结果被下一次使用，即每层（k层）路径的生成都是基于下层（k-1层）生成的最优路径的，这满足最优化原理的要求。动态规划算法与SystemR算法相比，增加了中间关系的大小估算。还有的改进算法，在生成第n层的时候，除了通过第n-1层和第一层连接外，还可以通过第n-2层和第2层连接，通过第n-3层和第3层连接……3.4紧密树处理流程4.遗传算法4.1概念遗传算法（GeneticAlgorithm，GA）是美国学者Holland于1975年首先提出来的。它是一种启发式的优化算法，是基于自然群体遗传演化机制的高效探索算法。遗传算法抛弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体（染色体），并将每一个个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（选择、交叉、变异），根据预定的目标适应度函数对每个个体进行评价，依据“适者生存，优胜劣汰”的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。遗传算法可以有效地利用已经有的信息处理来搜索那些有希望改善解质量的串，类似于自然进化，遗传算法通过作用于“染色体”上的“基因”，寻找好的“染色体”来求解问题（对算法所产生的每个“染色体”进行评价，并基于适应度值来改造“染色体”，使适用性好的“染色体”比适应性差的“染色体”有更多的“繁殖机会”）。4.2遗传算法的具体实现遗传算法主要步骤如下：1）随机初始化种群；2）评估初始的种群，即为种群计算每个个体的适应值且对所有个体排序；3）如果没有达到预定演化数（可以是一个确定的、与连接的表的个数无关的值，这样保证搜索空间一定不会因连接的表的个数增多导致搜索空间指数级增大），则继续下一步，否则结束算法；4）选择父体，随机挑选父体dad和母体mum；5）杂交，父体和母体杂交得到新个体child；6）变异，在某些个别条件下对新个体变异（不是大概率变异，不是每次都需要变异）；7）计算新个体的适应值，并把适应值排名插入到种群，种群中排名最后的则被淘汰；8）继续步骤3）。