The Algorithm Design Manual (一) 閱讀筆記
I - 1. Introduction to Algorithm Design
An algorithm is a procedure to accomplish a specific task. An algorithmic problem is specified by describing the complete set of instances it must work on and of its output after running on one of these instances. //透過完整的instances且用輸入輸出描述整個算法
- Robot Tour Optimization
- Input: A set S of n points in the plane.
- Output: What is the shortest cycle tour that visits each point in the set S?
 |
我們會發現這個方法不是最佳解，如果0作為起點，此算法將會一直"左右左右"走。
書中提到第二個想法，每次重複地連接一組端點成edge，這一組pair是其中兩點最近的edge，終止條件是形成了一個cycle。最後再連接兩組終點形成一個cycle。
這是著名的travel salesman problem，暴力解方法是每次從起點去尋找其他n-1個點的可能，所以是(n-1)!
OptimalTSP(P)
d = ∞
For each of the n! permutations Pi of point set P
If (cost(Pi) ≤ d) then d = cost(Pi) and Pmin = Pi
Return Pmin
1.2 Selecting the Right Jobs
Problem: Movie Scheduling Problem
Input: A set I of n intervals on the line.
Output: What is the largest subset of mutually non-overlapping intervals which can
be selected from I?
EarliestJobFirst(I)
Accept the earlest starting job j from I which does not overlap any
previously accepted job, and repeat until no more such jobs remain.
若第一個job是最長的，會造成1.6(l)的問題。
ShortestJobFirst(I)
While (I ̸= ∅) do
Accept the shortest possible job j from I.
Delete j, and any interval which intersects j from I.
若只從短的開始找，會造成1.6(r)的問題。
書中提出了暴力解：
ExhaustiveScheduling(I)
j = 0
Smax = ∅
For each of the 2n subsets Si of intervals I
If (Si is mutally non-overlapping) and (size(Si) > j)
then j = size(Si) and Smax = Si.
Return Smax
總共要做2^n次，離散數學有提到，若A={1,2,3}則組合有2^3=8次，{ ∅ },{1}.{2}.{3},{1,2},{1,3},{2,3},{1,2,3}這樣。
跟TSP不同的是，此問題有最佳解，從每個電影的間隔出發去想，第一個工作的完成時間是x，所以第二個工作要從x之後開始選，每次選擇都選最早完成時間的電影，這是一個greedy的演算法。
OptimalScheduling(I)
While (I ̸= ∅) do
Accept the job j from I with the earliest completion date.
Delete j, and any interval which intersects j from I.
1.3 Reasoning about Correctness
要適當地描述演算法，並step by step的推斷。最常見表示的三種型式：英文、虛擬碼、真實程式語言。Pseudocode is generally useful because it represents a happy medium
1.3.3 Demonstrating Incorrectness
去證明一個算法是不正確的最好方法是，用一個counter-example去產生一個錯誤的答案。
好的counter-examples有兩個重要的特點：
Verifiability – To demonstrate that a particular instance is a counter-example
to a particular algorithm, you must be able to (1) calculate what answer your
algorithm will give in this instance, and (2) display a better answer so as to
prove the algorithm didn’t find it.
Since you must hold the given instance in your head to reason about it, an
important part of verifiability is. . .
從最好的結果推論 or 給input導致錯誤的結果
Simplicity – Good counter-examples have all unnecessary details boiled away.
They make clear exactly why the proposed algorithm fails. Once a counterexample
has been found, it is worth simplifying it down to its essence. For
example, the counter-example of Figure 1.6(l) could be made simpler and
better by reducing the number of overlapped segments from four to two.
幫助找到counter-examples有以下幾點：
1. Think small : 從小case舉例出發，好驗證
2. Think exhaustively : 把所有可能發生的行為描述出來，舉電影排程為例：(1) disjoint intervals (2) overlapping intervals (3)properly nesting intervals
3. Hunt for the weekness : greedy algo每次拿最大，用只拿"最大"想一下counter examples
4. Go for a tie
5. Seek extremes
接下來都是一些簡介。還有real world發生的演算法故事"War Story"。
留言
張貼留言