204512/บรรยาย 14

---

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

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

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

---

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)