ขั้นตอนวิธีของคาร์เกอร์

จากวิกิพีเดีย สารานุกรมเสรี

ในวิทยาการคอมพิวเตอร์และทฤษฎีกราฟ ขั้นตอนวิธีของคาร์เกอร์ (อังกฤษ: Karger's algorithm) เป็น Monte Carlo method เพื่อคำนวณหา การตัดน้อยสุด (minimun cut) ของกราฟต่อเนื่อง ซึ่งถูกพัฒนาขึ้นโดย David Karger

โดยการตัดน้อยสุด คือ จำนวนเส้นเชื่อมน้อยสุดที่ต้องลบออกเพื่อให้กราฟแยกเป็น 2 ส่วน(component)

ขั้นตอนวิธี[แก้]

ตัวอย่างการลดเส้นเชื่อม

หลักการของขั้นตอนวิธีนี้ใช้แนวคิดในการย่อเส้นเชื่อม e ในกราฟ หรือกล่าวได้ว่าเป็นการย่อเส้นเชื่อมทำให้ปม 2 ปมที่ต่อกับ e ซ้อนกัน ทำให้ลดจำนวนปมทั้งหมดของกราฟลงไปหนึ่งปม ขั้นตอนวิธีนี้จะดำเนินการย่อไปเรื่อยๆ จนกว่าจะเหลือปมในกราฟเพียง 2 ปมเท่านั้น ซึ่งการกระทำนี้มีความเป็นไปได้สูงที่ขั้นตอนวิธีนี้จะคืนการตัดน้อยสุด โดยจะคืนเซตของเส้นเชื่อมที่ต่อกับปมที่เหลือทั้งสอง

การย่อ[แก้]

การกระทำนี้เอาเส้นเชื่อม e ที่มีปลาย x และ y และย่อมันลงในปมใหม่ v_e ซึ่งจะกลายเป็นเส้นประชิด(adjacent)ของปมเก่าทั้งหมดที่ต่อกับx และ y โดยสามารถเขียนแนวคิดนี้ให้อยู่ให้รูปคณิตศาสตร์ได้

ให้กราฟ G = \left ( V, E \right ) และ e = \lbrace x, y \rbrace \in E, การย่อของ G ไปเป็น e (เขียนเป็น G/e = \left ( V', E'\right )) เป็น มัลติกราฟ เมื่อ:

V' = \left( V \setminus \lbrace x, y \rbrace \right) \cup \lbrace v_e \rbrace

และ:

E' = \lbrace \lbrace v, w \rbrace \in E \mid \lbrace v,w \rbrace \cap \lbrace x,y \rbrace = \emptyset \rbrace \cup \lbrace \lbrace v_e,w \rbrace \mid
\lbrace x,w \rbrace \in E \setminus \lbrace e \rbrace หรือ  \lbrace y,w \rbrace \in E \setminus \lbrace e \rbrace \rbrace

เป็นไปได้ที่จะพิสูจน์ว่าการกระทำนี้ไม่ได้ลดภาวะเชิงการนับของการตัดน้อยสุด แต่อาจเป็นการเพิ่มให้มากขึ้น

รหัสเทียม[แก้]

รหัสเทียมนี้สามารถสร้างขึ้นโดยใช้ 2 ฟังก์ชัน

 function Karger(G, K)
 min := + \infty
 for i = 1 to K do
   t := Full_contraction(G)
   if t < min then
     min := t
 return min
 function Full_contraction(G)
 for i := 1 to |V| - 2 do
   e := Random(\varepsilon)
   G' = ( V', \varepsilon') := G / e
   V := V'
   \varepsilon := \varepsilon'
 return |\varepsilon|

ฟังก์ชัน Full_contraction ทำการย่อเส้นเชื่อมตามขั้นตอนวิธีที่ได้ระบุไว้ จากนั้นทำซ้ำไปเรื่อยๆ จนกว่าจะเหลือปมในกราฟเพียงสองปม จากนั้นจึงคืนค่าจำนวนเส้นเชื่อมระหว่างสองปมนั้น ซึ่งจะเท่ากับจำนวนตัดน้อยสุด แต่มันไม่สามารถประกันได้ว่าขั้นตอนวิธีนี้จะคืนการตัดที่น้อยที่สุดจริงๆ เพราะฉะนั้นการ excution Full_contraction K ครั้งโดยฟังก์ชัน Karger จะส่ง parameter K เพื่อให้ทำการคำนวณค่าน้อยสุดเป็นจำนวน K ครั้ง และเก็บคำตอบครั้งที่น้อยที่สุด ซึ่งวิธีนี้จะช่วยลดโอกาสที่จะคืนค่าการตัดน้อยสุดผิด

ประสิทธิภาพเชิงเวลา[แก้]

ฟังก์ชัน Full_contraction ใช้เวลาในการทำงานในรูปสัญกรณ์โอใหญ่ได้เป็น O(e) เมื่อe คือ จำนวนเชิงเชื่อม เนื่องจากต้องทำการลบเส้นเชื่อมทุกเส้นเชื่อมจนกว่าจะเหลือปมเพียง 2 ปม และการทำฟังก์ชัน Karger เป็นการทำ Full_contraction ซ้ำเป็นจำนวน K รอบ แต่เนื่องจาก K เป็นค่าคงที่ ดังนั้นประสิทธิภาพเชิงเวลาจึงยังคงเป็น O(e) หรือ O(V 2) สำหรับกราฟหนาแน่น

อ้างอิง[แก้]

  1. David R. Karger, Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1993
  2. David R. Karger and Clifford Stein, A New Approach to the Minimum Cut Problem. Journal of the ACM 43(4):601-640, 1996