20211225-组合数学概述

组合数学概述

1. 概述

组合数学，也叫离散优化，是运筹优化的重要组成部分。

组合优化是要从呈组合数复杂度爆炸式增长的解空间中，寻找最优的解向量，即指定最优决策方案。

组合优化问题涉及了分配、调度、指挥、路由等众多类型的问题，并且她与统计学习存在密切关系。

• 统计学习更侧重于预测和单步决策，比如：

  • 预测出了某件商品的销量，就可以知道需要进多少货；
  • 预测出了某个区域的人流量，就可以知道需要分配多少保安巡逻；
  • 检测出患者患有某种疾病，就可以知道开什么药。

• 组合优化更侧重多方的、全局的、系统性的序列决策。同时，离散优化与连续优化在思想上有很多相通之处。

2. 组合优化包含的问题

• 路由问题：用开销最小的路径覆盖所有目的地。
  • 车辆路由
  • 数据流量路由
• 指派问题：在有限的时间和空间中合理使用软硬件资源创造更多的收益。
  • 时间指派：
    • 先后序调度：单机作业调度、车间流水线调度
    • 时间槽分配：航班与列车时刻表、人员排班表、选修课表
  • 空间指派：
    • 哪个背包装哪些物品：背包问题；
    • 哪个处理器处理作业：多级作业调度；
    • 哪个中心服务哪些客户：中心选址；
• NPC：可以在多项式时间内相互规约。

3. 如何定义一个问题

• 基本要素：
  • 已知：输入数据；
  • 决策：输出结果；
  • 决策：输出结果可行还是不可行；
  • 目标：输出结果好还是坏；
• 观察问题的不同角度举例：
  • 图着色问题
    • 每个节点染什么颜色；
    • 每种颜色的节点集合包含了哪些节点。
  • 布尔表达式可满足性问题
    • 保证每个布尔变量在所有子句中取值一致，最大化为真的子句数量；
    • 保证每个子句为真，最大化布尔变量的一致性。

4. 基本求解方法分类

• 贪心算法：在保证求解速度的前提下提升精度【部分可以保证最优性的贪心算法往往可以归类为DP（e.g. Dijkstra算法）】；
• 近似算法：离最优解的差距有保障的贪心算法；
• 精确算法：在确保最优性的前提下降低复杂度；
  • 深度/广度/优先度优先树搜索
  • 动态规划
  • 混合整数规划的求解算法
• 启发式算法：在优度和复杂度之间寻找平衡点
  • 基于邻域动作：元启发式算法
    • 单个解：局部搜索；
    • 多个解：种群算法；
  • 基于树搜索：
    • A*：启发函数可接受时为精确算法；
    • 向前看树搜索（Lookahead Tree Search）
    • 线搜索（Beam Search）
    • 蒙特卡洛树搜索（Monte-Carlo Tree Search）

5. 问题规约与转换

• 经典问题到现实问题：
  • 图着色
    • 寄存器分配
    • 多业务波长分配
    • 停机位分配
    • 宿舍分配
  • 旅行销售员
    • 快递与外卖配送
    • 物资采购
    • 人类基因组计划
• 经典问题相互转换：
  • 独立集 == 最大团 == 顶点覆盖 == 支配集 == 集合覆盖 == 中心选址
  • 非对称旅行商 == 对称旅行商
  • 必经点最短简单路 == 非对称旅行商 == 最短简单路 == 最长简单路
• 经典问题分解：图着色 = 集合覆盖 + 独立集