算法目录

算法目录

算法分支

一、分治算法

可以将一个大问题分解成若干个小问题解决的问题

二、动态规划算法

根据子问题求解原问题的解(子问题不独立)

贪心法

  关键词:局部最优(较好的近似最优解,贪心)、简单、根据当前信息最选择,且不改变、

  使用环境:
  1.最优子结构。一个问题的最优解包含了其子问题的最优解。
  2.贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择(贪心选择)来得到

  示例:活动选择问题、背包问题、多机调度问题

  • 回溯法

    关键词:通用的解题法、解空间树(深度优先遍历)、界限函数、所有解(找出满足条件的所有解)

  步骤:

  1.针对所给问题,定义问题的解空间。问题的解空间应至少包含问题的一个(最优)解

  2.确定易于搜索的解空间结构。通常将解空间表示为树、图;解空间树的第i层到第i+1层边上的标号给出了变量的值;从树根到叶子的任一路径表示解空间的一个元素。

  3.以深度优先的方式搜索整个解空间。如果当前宽展节点处为死节点,则回溯至最近的一个活节点处。(以此方式递归搜索)

  算法框架:非递归、递归

  界限函数:回溯法的核心。尽可能多、尽可能早地“杀掉”不可能产生最优解的活节点。好的界限函数可以大大减少问题的搜索空间,大大提高算法的效率。

  示例:0-1背包、N皇后问题

  • 分支界限法

  关键字:解空间(广度优先、最小耗费优先)、界限函数(队列式、优先队列式)

  步骤:

  1.针对所给问题,定义问题的解空间。问题的解空间应至少包含问题的一个(最优)解

  2.确定易于搜索的解空间结构。通常将解空间表示为树、图;解空间树的第i层到第i+1层边上的标号给出了变量的值;从树根到叶子的任一路径表示解空间的一个元素。

  3.以广度优先或最小耗费优先的方式搜索整个解空间。每个活节点只有一次机会成为扩展节点,活节点一旦成为扩展节点,其余儿子节点被加入活节点表中。(以此方式递归搜索)

  界限函数:分支界限法的核心。尽可能多、尽可能早地“杀掉”不可能产生最优解的活节点。好的界限函数可以大大减少问题的搜索空间,大大提高算法的效率。

  1.队列式(FIFO)分支界限法。先进先出

  2.优先队列式分支界限法。组织一个优先队列,按优先级选取。通常用最大堆来实现最大优先队列,最小堆来实现最小优先队列。

  • 概率算法

  关键词:随机性选择、小概率错误(运行时间大幅减少)、不同解(对同一问题求解两次,可能得到完全不同的解,且所需时间、结果可能会有相当大的差别)

  基本特征:

  1.输入包括两部分。一,原问题的输入;二,供算法进行随机选择的随机数序列
  2.运行过程中,包括一处或多处随机选择,根据随机值来决定算法的运行
  3.结果不能保证一定是正确的,但可以限制出错率。
  4.不同的运行过程中,对于相同的输入实例可以有不同的结果,执行时间也可能不同。

  分类:
  1.数值概率算法。常用于数值问题的求解。近似解,近似解的精度随计算时间的增加不断提高。

  2.蒙特卡罗(Monte Carlo)算法。精确解,解未必是正确的,正确的概率依赖于算法所用的时间。一般情况下,无法有效地判定所得到的解是否肯定正确。

  3.拉斯维加斯(LasVegas)算法。一旦找到解,一定是正确解。找到的概率随计算时间的增加而提高。对实例求解足够多次,使求解失效的概率任意小。

  4.舍伍德(Sherwood)算法。总能求得问题的一个解,且所求得的解总是正确的。设法消除最坏情形与特定实例之间的关联性。多用于最快情况下的计算复杂度与其在平均情况下的计算复杂度差别较大。

  • 近似算法
      关键词:近似解、解的容错界限(近似最优解与最优解之间相差的程度)、不存在多项式时间算法

  基本思想:放弃求最优解,用近似最优解替代最优解。使算法简化,时间复杂度降低

  衡量性能的标准:

  1.算法的时间复杂度。时间复杂度必须是多项式阶的
  2.解的近似程度。与近似算法本身、问题规模、不同的输入实例有关。

  示例:NP问题、定点覆盖问题、TSP、子集和数问题、

  • 遗传算法(进化算法)

  • 鸟群觅食算法(粒子群算法)

  • A* 算法

算法备注

  • 各种算法分支的理念,最好有流程图

  • 每种算法给出例子,源码实现

  • 复杂的算法给出框架介绍

  • 算法的适应情况