204512/บรรยาย 14

---

จดบันทึกคำบรรยายโดย:

นายดิเรก ยิ้มละมัย   รหัส : 50653799

Lecture Date :: 26 September 2007 (06.00PM)

Create Date :: 27 September 2007 (05.18PM)

Last Update :: 02 October 2007 (12.01PM)

วางโครงเฉยๆ อ่ะครับ จะรีบทำให้เสร็จเร็วๆนะครับ

---

Approximation Algorithm

เนื่องจากการดำเนินการด้วย Algorithm ตรงๆ นั้นหากทำให้เสร็จโดยสมบูรณ์จะมีระยะเวลามากกว่า polynomial time ดังนั้นจึงมี approximation algorithm ด้วยการใช้ heuristic บางอย่างมาช่วยในการดำเนินการ แต่จะไม่รับประกันว่าค่าคำตอบนั้นดีที่สุด

Vertex Cover problem

ให้กร๊าฟ G = (V, E) หา set C ⊆ ที่ Cover edge ทั้งหมด ที่มีขนาดเล็กที่สุด แนวคิดแรก หาก node ที่มี edge เข้าหาตัวมันมากที่สุด Degree มาก แต่จะได้ความห่างจากคำตอบที่ดีที่สุดคือ log(n) แนวคิดที่ดีกว่า หยิบ edge แทนจะทำให้ได้ Node 2 node ในการหยิบหนึ่งครั้งได้ความห่างอยู่ที่ 2 เท่าของคำตอบที่ดีที่สุด วิธีการคร่าวๆ ดังรูป

Algorithm 

C <- ø
While มี edge ใน G
เลือก edge e = (u, v) ใดๆ
C <- C υ {u, v}
ลบทุกๆ Edge ที่ติดกับ u หรือ v
[ M <- M υ {e} ] //ใส่เพื่อ analysis ว่าเป็น edge ร่วมที่เลือก
return C

Claim

สำหรับ vertex cover C’ ใดๆ
|C’| ≥ |M|

Proof

เนื่องจาก C’ เป็น vertex cover ทุกๆ edge e Є M, C’ จะต้องมีจุดปลายของ e อย่างน้อย 1 จุด
อย่างไรก็ตามทุกๆ edge ใน M ไม่ใช่จุดปลายร่วมกันเลยนั่นคือ |C’| ≥ |M| ตามต้องการ ----#
เพราะฉะนั้น Approximate ไม่เกิน 2 เท่า

คำอธิบาย

edge เหล่านี้สังเกตดีๆ ว่าจะไม่ share node กันเลย จะใช้ cover อย่างน้อยเท่ากับจำนวน edge เหล่านี้ ในแต่ละ edge มี 2 node จะต้องเลือก 1 node เราเลือก edge ทำให้บอกได้ว่าดีที่สุดคือ vertex cover มีค่าเท่ากับจำนวน edge แต่เราเอกได้ 2 node ต่อ 1 edge ดังนั้นคำตอบที่ได้จะเป็น 2 เท่าของ edge
เพราะฉะนั้น คำตอบจะเป็น 2 เท่าของคำตอบจริง

Metric Steiner Tree problem

Steiner tree คือ ปัญหาที่เรามี Complete graph G = (V, E) มี edge weight W(e) บนเส้นเชื่อม e มี Set T ⊆ V หากมองถึง Minimum spanning tree คือหา ทุกๆ node เชื่อมกันที่มี Weight ต่ำที่สุด แต่ในส่วนของ Steiner tree นั้นจะหา Minimum Steiner tree ขอเรียกว่า Minimum Cost Tree ที่ Span T (Steiner Tree)

เราสามารถนำโหนดอื่นๆ มาช่วยในการหาได้ เพราะความจริงเราหา minimum spanning tree ไม่ได้จริงในทุก graph แต่เราอยากหาเส้นทางที่ไปได้และใกล้เคียง

หากใช้ Minimum spanning tree เราจะถือว่าทุกโหนดสำคัญ ซึ่งทำให้อาจได้ค่าจาก A, B, C, D เดินหากันนั้นไกลมาก ทั้งที่อยู่ใกล้กันมาก ดังรูป

Algorithm

สร้างกร๊าฟ G’ ที่ มี T เป็นเซตของโหนด
มี Cost เหมือนเดิม
โดยไม่สนใจโหนดภายนอกโยนทิ้งทั้งหมด คือ การไม่สนโหนดช่วยเหลือ
หา MST G’ (ค่าไม่เกินสองเท่าของ Steiner tree)

จะพิสูจน์ว่า minimum spanning tree หาได้ค่าดีที่สุดไม่เกินสองเท่าของ Minimum Steiner Tree พิจารณา Optimal Steiner Tree

Depth First Search Animation:: DFS Animation

• • การสร้าง Steiner Tree ใดๆ สามารถหาได้จาก Spanning ที่มีค่าไม่เกน2เท่าของ Optimum

จะสร้าง F’ ที่เป็น Spanning Tree บน F ที่มี Cost(F’) ≤ 2.Cost(F)

ขั้นตอนการทำงานจากรูป Steiner Tree ด้านบน

1) จาก F สร้าง Trail H ด้วย DFS ความยาวของ H = 2.Cost(F) เพราะแต่ละ Edge ใน F ถูกเดินผ่าน 2 ครั้ง
2) สร้าง F’ จาก H โดยการสร้าง Short cut จะได้ว่า
Cost(F’) ≤ ความยาวของ H = 2.Cost(F)

Minimum Steiner Tree มี Span ที่ Cost ไม่เกิน 2 เท่าของ Steiner Tree ทำให้ได้ค่าดีที่สุดไม่เกิน 2 เท่าของ Minimum Steiner Tree แต่ก็ยังมีตัวอย่างที่ MST G’ ให้คำตอบ 2 เท่า

จากรูป

1) จะเป็นการเชื่อมแบบ Completed Graph และ ทุก Edge ความยาว 2 ทำให้ Spanning Tree ตอบ 2(n-1)
2) จากนั้นเติมโหนดสีแดง จะไม่เปลี่ยนค่า Cost ของการเดิน เพราะจะยังคงค่าความยาว 2 เท่าเดิม และเรามีค่า Steiner คือ n โหนด
จะพบว่าเราได้ 2(n-1)/n ซึ่งยิ่งค่า n มากๆ ค่าก็จะเป็นค่าที่เข้าใกล้ 2

Traveling Sale person problem

พื้นฐาน

มีเมือง n เมือง 1,…,n ระหว่างเมือง i กับ j มีระยะทาง d(i,j) โดยที่ d เป็น metric ซึ่งมีเงื่อนไขดังต่อไปนี้
(1) d(i,j) = 0 ;∀i หากเป็นจุดเดียวกันระยะทางเป็นศูนย์
(2) d(i,j) = d(j,i) ; ∀i,j จุดต้นและปลายเดียวกันไปมาหากันระยะทางเท่ากัน
(3) d(i,j) ≤ d(i,k) + d(k,j) ; ∀i,j,k เส้นทางใหม่ ระยะทางไม่ยาวเกินไปกว่าระยะทางเดิม
โดย TSP ต้องการหา Cycle ที่ผ่านครบทุกเมือง เมืองละ 1 ครั้งเท่านั้น

พิจารณา Optimum Solution C* ของ TSP

ลบ Edge 1 edge ออกจาก C* จะได้ Part P (Part นั้นซึ่งเป็น Tree) ที่มี Cost ไม่เกิน Cost ของ C*
ถ้า T เป็น MST ของกร๊าฟ
Cost(T) ≤ Cost(P) ≤ Cost(C*)

“การทำ Spanning Tree จะได้กร๊าฟ แต่เราต้องการ Part เพื่อ Tour”

เราต้องการเดินครบทุก Edge แต่กร๊าฟเรากลายเป็น Tree การเดินจะซ้ำบาง Edge ดังนั้นเราเติมบาง Edge จะทำให้เดินได้ตามที่ต้องการ แท้จริงแล้วคือการนำ Short Cut มาช่วย

1. Minimum Spanning Tree ค่า Cost จะไม่เกิน Optimum

2. เราต้องหา Edge มาเติมเพื่อให้ Degree เป็นคู่แต่ค่าใช้จ่ายต่ำ

Claim1

ทุกๆ กร๊าฟมีโหนด degree คี่เป็นจำนวนคู่ (ผลรวมของ degree ทั้งหมดเป็นเลขคู่)
1. Edge บวก Degree ให้กับโหนดทั้งสองโหนด
::ได้ว่า Node มี 2 เท่าของจำนวน Edge
ผลรวม degree คู่ (2 edges) หากแม้นดึงออกก็ยังทำให้ degree รวมยังคงเป็นคู่เพราะว่า degree คี่รวมกันเป็นจำนวนคู่ จะได้ degree รวมยังคงเป็นคู่จริง
∑ vมีdegreคู่deg(V) + ∑ vมีdegreคี่deg(V) = ∑ vЄVdeg(V)

พิจารณา

- Node degree คี่

- เติม Edge เข้าไป จับคู่โหนด degree คี่ (เส้นสีเขียว)

o ??? การจับคือปัญหา เพราะจะต้องจับคู่ให้ระยะทางรวมน้อยที่สุด

o Minimum Matching ใน General Graph แก้ได้ใน Polynomial time (ปัญหา Minimum Matching ปรกติพบเห็นได้ใน Bipartite graph

- จะสร้าง G’ โดยมีโหนดเป็นโหนด degree คี่ ใน T

o Weight ของแต่ละเส้นเชื่อม w(u,v) = d(u,v)

- หา Minimum Weight Matching M ใน G’

- หา Cycle ใน T υ M

- หา Short Cut

คำตอบมีค่าใช้จ่าย Cost(T) + Cost(M) ≤ Optimum + Cost(M) ≤ 1.5 (Optimum) ซึ่งเราจะพิสูจน์ภายหลังว่า Cost(M) ≤ 0.5(Optimum)

Set Cover problem

มี Universal U = {1,…,n}

มี Set S1, S2,…,Sm ที่ Si ⊆ U ;∀i

ตัวอย่าง

เลือก Subset น้อยที่สุด และเลือกไปเรื่อยๆได้ U , เช่น run test case ให้น้อยครั้งที่สุดเพื่อหา BUG ว่ามีกี่ case โดยการเลือก Set ของการ Test

ต้องการหา I ⊆ {1,…,m} ที่ |I| น้อยที่สุด และ u Si = U ; โดยที่ I Є I

เทคนิค Greedy

1.เลือก Set ที่โตที่สุดและตัดออก

2.เลือก Set ใหญ่สุดที่เหลือ

จะได้ไม่เกิน ln(n) เท่า

Algorithm

u = U ; 1 ← ø

while u ≠ ø

เลือก i ที่ Maximize u ∩ Si

I ← I υ {i}

u ← u - Si

end while

สมมติให้มี Set จำนวน K sets ที่ cover U (คำตอบที่ดีที่สุดคือ K sets)
จะต้องมีอย่างน้อย 1 set ที่กินไม่น้อยกว่า 1/K ของทั้งหมด

Step แรก

เลือก Set ที่ Cover อย่างน้อย n/K elements

ให้ ni แทน |u| หลังการเลือก Set ไป i set

n0 = n

ni ≤ ni-1 - ni-1/K = ni-1 (1-1/K)

ni ≤ n(1-1/K)^i ; ก้อนนี้จะต้องยกกำลัง i กี่ครั้งจึงจะกิน n จนหมด

ทำกี่ครั้ง

ni < n(1 - 1/K)^i ; K > 0

ni < n(e^-1/K)^i

ni < n.e^-i/K

ถ้าให้ i = k ln(n)

จะได้ว่า ni < n.e^-(K ln(n))/K = n.e^-(ln(n)) = n.1/n = 1

ln (n) คือ approximation algorithm