难解性问题的求解与算法

这是一篇关于难解性问题的求解与算法的思维导图，主要内容包括：拓展，遗传算法的应用，遗传算法求解NPC类问题，计算学科的遗传算法，遗传算法，可求解与难求解，算法类思维概述。

难解性问题的求解与算法

• 算法类思维概述
  • 现象-算法-本质应用
• 可求解与难求解
  • 不同量级的复杂性在计算时间上的差异
  • 分类（计算复杂性）
    • P类
      • 多项式时间内求解精确解
    • NP类
      • 多项式时间内验证精确解
    • NPC类
      • 1多项式时间内验证每一个解
      • 2求精确解需要使用遍历计算
      • 3指数时间
    • 难解类问题
      • 非NP类问题，多项式时间内不一定能验证一个解
• 遗传算法
  • 起源：生物学中的遗传与进化
  • 类比与创新
    • 自由组合，遗传与进化，优胜略汰
• 计算学科的遗传算法
  • 概念映射
    • 解集，解，编码解，基因，适应度，选择，复制，交叉，变异
  • 仿生学过程进行问题求解
• 遗传算法求解NPC类问题
  • 解的一组概念
    • 可能解，可行解，近似解，满意解，精确解
  • 初始思路（遍历算法）
    • 随即搜索法（以质量换速度）
• 遗传算法的应用
  • 会议室租用问题
  • 航班机组成员选择问题
  • 软件测试用例选择问题
• 拓展
  • 设计要点（解的形式-表现型，编码-基因型，可能解不同表达影响遗传与变异的规则）
  • 策略
    • 选择的多样性
      • 交叉
    • 选择的随机性
• 导向性随即搜索法（质量速度都要）
  • 导向性群随即搜索法
    • 遗传算法