算法设计与分析笔记0x09 —— 网络流

Max-flow and Ford-Fulkerson Algorithm

  • 网络流是一个有向图,源点s,汇点t
  • 每条边流量f(e)不能超过容量c(e)
  • 守恒: 指向结点的流量之和($\sum_{e\,in\,to\, v}f(e)=\sum_{e\,out\,of\,v}f(e)$)等于流出结点的流量之和 (except source and sink points)
  • 流的值: 流出源点的流量综合 $v(f)=\sum_{e\,out\,of\,s}f(e)$.
  • Max flow problem 找到 s-t flow 使其流的值最大
  • Greedy algorithm: 局部最优, 非全局最优.
    • Start with f(e) = 0 for all edge e ∈ E.
    • Find an s-t path P where each edge has f(e) < c(e).
    • Augment flow along path P.
    • Repeat until you get stuck.

Continue reading “算法设计与分析笔记0x09 —— 网络流”

算法设计与分析笔记0x05 —— 分治法(1)

Divide and Conquer

  • Break up problem into several parts
  • Solve each part recursively
  • Combine solution to sub-problems into over solution

Let’s consider about mergesort.
$$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + n$$
We solve it and get T(n)=O(nlogn), which could be proved by several methods mentioned in Basic Algorithm Note.

Continue reading “算法设计与分析笔记0x05 —— 分治法(1)”

算法基础笔记0x05 —— 查找与选择

Search Algorithm

  • 给定一个排好序的数组,搜索输入x
  • Idea Maintain an interval between [l, r] where x may be. Shrink the interval as quickly as possible.
    • Initially the interval is all of A, i.e. l = 1, r = |A|.
  • Use a probe point m = (l + r) / 2.
    • If x < A[m], x can’t lie in [m, r], so keep searching in [l, m-1].
    • If x > A[m], keep searching in [m+1, r].
    • If l = r but x ≠ A[m], then x is not in A.

Continue reading “算法基础笔记0x05 —— 查找与选择”