ขั้นตอนวิธีการลบย้อนกลับ

**ขั้นตอนวิธีการลบย้อนกลับ** () เป็นขั้นตอนวิธีในทฤษฎีกราฟที่ใช้สำหรับ ต้นไม้แผ่ขยายต่ำสุด (minimum spanning tree) ที่มีเส้นเชื่อม เชื่อมทุกปมต่อกันทั้งกราฟ และเส้นเชื่อมระหว่างคู่ปมแต่ละเส้นมีน้ำหนักเส้น ขั้นตอนวิธีนี้เป็น ขั้นตอนวิธีแบบละโมบ (Greedy algorithm) ซึ่งเป็นการย้อนกลับของ ขั้นตอนวิธีของครูสกาล (Kruskal’s algorithm) ที่ใช้ในการหาต้นไม้แผ่ขยายต่ำสุด ขั้นตอนวิธีของครูสกาลจะเริ่มจากกราฟที่ว่างเปล่า แล้วเพิ่มขึ้นทีละเส้นเชื่อม แต่ขั้นตอนวิธีการลบย้อนกลับนี้เริ่มจากกราฟเดิมที่สมบูรณ์แล้วลบออกทีละเส้นเชื่อมจากกราฟนั้นแทนโดยขั้นตอนวิธีดังกล่าวทำงาน ดังนี้

* เริ่มต้นด้วยกราฟ G ซึ่งประกอบด้วยแถวลำดับของเส้นเชื่อม E
* ผ่านกราฟ G โดยลดน้ำหนักของเส้นเชื่อมลงทีละลำดับ
* สำหรับแต่ละเส้นเชื่อม ตรวจสอบว่าการลบเส้นเชื่อมนั้นออก จะไม่ทำให้กลายเป็นกราฟที่ไม่เชื่อมต่อกัน
* ดำเนินการลบโดยไม่นำไปสู่การที่ทำให้การเชื่อมต่อของกราฟขาดออก

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

## รหัสเทียม

 เมธอดรับค่า แถวลำดับของเส้นเชื่อม E(edges[] E)
 {
  จัดลำดับ E ในแถวลำดับเรียงจากมากไปหาน้อยตามลำดับ
  ตั้งค่าเริ่มต้นให้ตัวแปร i=0
  ทำการวนซ้ำไปเรื่อย ๆ ขณะที่ค่า i น้อยกว่าขนาดของแถวลำดับ E ทั้งหมด
  {
   สร้างตัวแปร temp เก็บค่า ในรายการ E ตัวที่ i
   ทำการลบค่า ในรายการ E ตัวที่ i
   ถ้าปมระหว่างเส้นเชื่อมที่เก็บค่าใน temp ขณะนั้น ไม่เชื่อมต่อกัน ก็นำค่า temp เก็บ
   คืนสู่แถวลำดับ E ในช่องที่ i
   เพิ่มค่า i ขึ้น 1
  }
  คืนค่าในแถวลำดับ  E ทั้งหมด
 }

## ตัวอย่าง

## ประสิทธิภาพการทำงาน
ขั้นตอนวิธีนี้สามารถทำงานได้ในเวลา O(E log E (log log E)3) ซึ่ง E คือจำนวนเส้นเชื่อม และ V คือจำนวนปม โดยอธิบายการทำงานของเวลาได้ดังนี้
* การจัดเรียงข้อมูลโดยเปรียบเทียบน้ำหนักของเส้นเชื่อมทั้งหมดใช้เวลา O(E log E)
* การลบแต่ละครั้งใช้เวลา O(1)
* การตรวจสอบว่ากราฟเชื่อมต่อกันทุกปมหรือไม่ ใช้เวลา O(logV (log log V)3)
ดังนั้นจึงใช้เวลาทั้งสิ้นของขั้นตอนวิธีนี้ O(E log V (log log V)3)

## ขั้นตอนวิธีที่เกี่ยวข้อง
* Kruskal's algorithm
* Prim's algorithm
* Borůvka's algorithm
* Dijkstra's algorithm

## อ้างอิง
* Kleinberg, Jon; Algorithm Design, New York: Pearson Education, Inc..
* .
* Reverse-Delete Algorithm (Paperback) by Lambert M. Surhone and Mariam T. Tennoe and Susan F. Henssonow

## เพิ่มเติม
เป็นขั้นตอนวิธีการแก้ปัญหาที่คิดแบบง่าย ๆ และตรงไปตรงมา โดยพิจารณาว่าข้อมูลที่มีอยู่ในขณะนั้นมีทางเลือกใดที่ ให้ผลตอบแทนคุ้มที่สุด ขั้นตอนวิธีจะหาทางเลือกที่ดูดีที่สุดในขณะนั้นซึ่งถ้าข้อมูลนั้นพอเพียงที่จะทำให้สรุปคำตอบที่ดีที่สุด เราจะได้ขั้นตอนวิธีที่มีประสิทธิภาพ โดยทั่วไปการนำไปใช้กับ Optimization problem เพราะว่า เราต้องการการตัดสินใจว่าทางเลือกในปัจจุบันมีค่าตอบแทนมากที่สุดหรือน้อยที่สุดหรือไม่

## แหล่งข้อมูลอื่น
* http://code.google.com/p/mst-algorithms/source/browse/trunk/MSTAlgorithms/src/cz/cvut/fel/minimalSpanningTree/algorithm/implementation/ReverseDeleteMST.java?spec=svn41&r=41
* http://en.vionto.com/show/me/Kruskal's+algorithm
* http://courses.cs.vt.edu/~cs5114/spring2009/lectures/lecture05-greedy-graph-algorithms.pdf

หมวดหมู่:ขั้นตอนวิธีกราฟ
หมวดหมู่:ต้นไม้ทอดข้าม