整数规划 #
举例 #
Combinatorial Optimization #
组合优化问题(COP)
精确方法和近似方法 #
常见相关场景/问题 #
TSP
给定一系列城市和每对城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路
VRP
给定一组客户点、车辆容量、车辆数量、起始点和终点，目标是找到使得所有客户点都被访问一次的最短路径方案。
MVC(最小顶点覆盖问题)
MDS(最小支配集)
MIS(最大独立集)
背包问题
Heuristic algorithm #
SA #
Simulated Annealing
GA #
Genetic Algorithm
GE #
Grammatical Evolution
基于NN和DL的方法 #
分类 #
特点 #
优点 #
缺点 #
经典模型 #
Pointer Network #
PointerNet 是基于 Sequence to Sequence 的 Attention 机制的改进
PointerNet 引入了一种新的神经体系结构来学习输出序列的条件概率，其中元素是与输入序列中的位置相对应的离散标记
模型 #
作者发现， $ A^i_j $ 经过softmax后，也可以直接作为针对原序列的指针进行训练；简单理解为，原来的 $ A^i_j $ 为原序列每一位的注意力，那么新的 $ A^i_j $ 可以作为原序列每一位放在此处的概率，最后选择概率最大的直接输出。
编码器和解码器均为 LSTM
训练的问题 #
强化学习进行训练 #
graph theory #
Tarjan算法提取强连通分量 #
basic #
强联通图
强联通分量
在强连图图的基础上加入一些点和路径，使得当前的图不在强连通，称原来的强连通的部分为强连通分量。
基本思路 #
对于每次搜索的点，我们都加入栈中，遇到回路时，在把栈中的元素逐个弹出，记录它们的起始结点，直到栈中弹出的元素正好是起始结点时，结束弹栈，继续搜索其它强连通分量
在这个过程中，所有的点和都有的边都被遍历了一次，所以最终的时间复杂度为O ( N + E )
流程举例 #
参考 #
maze algorithm #
基本知识 #
- 曼哈顿距离：水平+垂直举例
- 欧几里得距离：直线距离
原理 #
F=G+H
dynamic programing #
Tree algorithms #
R-Tree #
R-Tree是B-Tree的多维版
核心思想 #
操作 #
搜索（query） #
插入（insert） #
删除（delete） #
参考 #
LeetCode Note #
Hash #
哈希表查表操作时间复杂度为1