算法设计
稳定匹配问题
algorithm-stable-match
描述
有若干个男和若干个女，每个男对每个女都有一个偏好值，女同理，怎么找出一个算法，使得匹配适当
适当性
配对结果不存在单方面更改使得获取到更好得一方，而那方也正好更喜欢此方
Gale-Shapley算法
- 遍历男
- 如果man1没有配对，则从优到劣选择femal
- 如果此时femal已经配对，则从femal得优先队列中比较man1跟已经匹配得man2得优先级比较，如果man1>man2，则把femal得配对更换乘man1-femal，并取消femal-man2
- 如果遇到femal没有配对过，则配对man1-femal
- 循环上述过程，知道所有man和femal都有一个配对
分析
上述算法，男总是能选择到最优，但是女总是选择到次优，所以算法是不公平得。
如果在信息不对称的情况，男的并不能获取到女的优先偏好，那么女可以通过说谎，把优先顺序置换，那么此时女可以获得更优解
DAG的拓扑顺序
algorithm-dag
DAG定义
有向无环图
拓扑
DAG可以转化为从左到右序列的结构
转换算法
- 计算每个节点的入度
- 获取入度为0的节点，放在第一位
- 删除入度为0的节点和关联的边并重新计算节点入度
- 循环上述过程
贪婪算法
Coin Changing Problem（最小硬币问题）
问题
有若干面值硬币，给定一个金额，求出使用最小硬币可以达到金额的组合
贪婪算法
- 对硬币根据面值从大到小排序
- 每次取最大面值的硬币，并减去金额，直到不能再取
- 如果金额不等于零，则从次高面值的硬币取
- 循环以上过程，直到金额等于零
分析
贪婪算法并不能总是得到最优解
例如面值为1 4 5，金额为8，那么如果使用贪婪算法，得到{5,1,1,1}，并不是最优解{4, 4}
对于此问题，可以化解为f(n) = min(1+f(n-k_1) ,1+ f(n-k_2),1+ f(n-k_3))
k_1>k_2>k_3...
如果使得对于任意n，满足f(n-k_1)<f(n-k_2)<f(n-k_3)...
那么此时可以使用贪婪算法得到最优解
Interval Scheduling(贪心区间调度)
algorithm-interval-scheduling
求最大任务数
列出动态规划公式
f(startTime) = max( 1+ f(endTime1) , 1+ f(endTime2) ....1+ f(endTimen) )
如果按照endTime从小到达排序，可得
f(endTime_k-1)>=f(endTime_k-2)
所以此时如果使用贪婪算法，每次取endtime最早的任务处理，可得最优解
Interval Partitioning Problem(时段区间最小问题)
algorithm-interval-partitioning
描述
安排若干个区间，把相容得任务放在同一个区间，求区间的最小数
算法
使用贪婪算法，分别使用最早开始时间优先，最后结束时间优先，最长覆盖优先
分析上述三种算法，容易得到最后结束时间优先和最长覆盖优先反例。
下面分析最早开始时间优先的证明
先给出算法：
- 对任务按照最早开始时间排序
- 找到最早开始的任务，找到相容的区间k个
- 任意选择其中一个，加入此任务，并更新区间状态
- 如果不相容，则开辟一个新区间n+1
- 循环以上过程，直到所有任务分配完成
证明
- 假设目前存在m个区间
- 目前加入任务k
- 如果任务k与m个区间都不相容，那么m->m+1
- 如果k与其中n个区间相容，那么能否找到一个更优解？
- 加入选择n个中的一个j，那么第j个区间会更新为starttime_j->endtime_k
- 其他n-i个区间更新为starttime_o->starttime_k
- 反证法，如果存在后面一个任务b，b可以插入到j中，而j的区间不会大于starttime_j->endtime_k
- 那么由于k: starttime_k->endtime_k, b: starttime_b->endtime_b
- 那么endtime_b必然小于enttime_k
- 但是根据优先选择开始时间早的任务，那么有starttime_k>starttime_b
- 那么可以得到b和k必然互斥
- 得出矛盾，所以不存在此情况
sheduling to minimize lateness(最小延迟调度)
algorithm-lateness
问题
- 1->6为任务id
- t为任务i完成需要的时间
- d为任务可以容忍的最后时间
- 求一个单区间序列，使得di-ti最小
算法
优先选择
- 按t，每次取最小的
- 按d，每次取最小的
- 按d-t，每次取最小的
容易得到1和3，容易得到反例，故不能得到最优解
algorithm-lateness-not
以下分析第2钟情况
过程
- 按照dealine从小到大排序
- 每次从最小dealine取
- 然后累加延迟
- 循环以上过程，直到取完所有节点
证明
- 加入有两个任务1和2
- 有d1<d2
- l1={t1 - d1} + {t1 + t2-d2}
- l2={t1 + t2 - d1} + {t2 - d2}
- {}<0，则取0，否则取正数
- 假设l1>l2
- 如果在l1中，任务1和2都有延迟，l2中都有延迟，那么它们相等
- 否则，假设任务1没延迟，则有
- {t1 + t2-d2} > {t1 + t2 - d1} + {t2 - d2} > {t1 + t2 - d2} + {t2 - d2}
- 矛盾
shortest path(最短路径)
Dijkstra算法
最小生成树
algorithm-spanning-tree
Kruskal算法
- 对边的权重进行排序
- 取最小的边，如果加入的边不构成圈
- 否则选择下一条最小的边，直到集合加入所有节点
分治
求逆序对个数
algorithm-inversions
通过归并算法
- 把数组一分为二
- 计算左右子数组各自的逆序对
- 计算左子数组相对与右子数组的逆序对
algorithm-inversions_merge
动态规划
最大权重区间调度问题
列出动态规划
f(startTime) = max(w_i+f(endTime_i), w_i-1 + f(endTime_i-1)....) if startTime_i>startTime
通过分析上述公式，虽然f(endTime_i)>f(endTime_i-1)，但是无法保证w_i>w_i-1，可知无法通过贪婪算法求得最优解
背包问题
algorithm-knasack
字串对齐问题
问题
有两个字符串
实现diff算法，得出它们之间最小的不同
algorithm-diff
算法
cost(i,j) = j if i==0
cost(i,j) = i if j==0
cost(i,j) = cost(i-1, j-1) if s1[i] == s2[j]
else
cost(i,j) = min(cost(i-1, j) + 1, cost(i, j-1) + 1)
最短路径（带负权重边）
f(u->v) = min(w1 + f(n1->v), w2 + f(n2->v), w3 + f(n3->v) ... )
其中n为u的下一节点，w为u到n的cost
网络最大流
algorithm-network
网络如图所示，如何找到网络从s到t能通过的最大流量？
最小割
algorithm-network-min-cut
此为网络中的一种流量，我们把图分为两部分，把它从其中一部分流向另一部分的流量叫做割。不难证明，网络的最大流量，必然是割的最小值。
Ford-Fulkerson算法
algorithm-network-ff
- 通过深度搜索，从s到t，寻找一条路，例如s->2->5->t
- 在路上引入反向路（残存网络），标记为最小的流量8
- 重复上述过程，直到再也找不到一条从s->t的路为止
choosing good augmenting paths算法
algorithm-network-goodarg
如图，在选择增广路策略中，如果选择不当，例如总是选择1，那么可能会导致在多项式时间内不能让算法终止。
此算法，通过引入多尺度，来控制增广路的选择
- 设置s为最大边大小的一半
- 把边大于s的构成一个子图
- 进行FF搜索
- s = s / 2
- 循环以上过程，直到s == 1
二分图问题
algorithm-network-two
描述
图被分为左右两个子图，子图内的节点不会有边相连，有若干条边关联左右两个子图的节点。
问怎么匹配，使得左右子图匹配的节点数最多
算法
algorithm-network-two-2-max
通过引入s和t节点，每条边设置为流量1，二分图问题转化为最大流问题。
通过FF算法，能够找出从左子图流向右子图的最大流，则它们的最大匹配
近邻搜索
通过爬山法局部找更优的点
详细可看另外一篇--人工智能
