算法设计

稳定匹配问题

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算法，能够找出从左子图流向右子图的最大流，则它们的最大匹配

近邻搜索

通过爬山法局部找更优的点

详细可看另外一篇--人工智能