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

ขั้นตอนวิธีการลบย้อนกลับ (อังกฤษ: Reverse-delete algorithm) เป็นขั้นตอนวิธีในทฤษฎีกราฟที่ใช้สำหรับ ต้นไม้แผ่ขยายต่ำสุด (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 ทั้งหมด } 

ตัวอย่าง

รูปภาพ	คำอธิบาย
	จากรูป นี่คือกราฟเริ่มต้น ตัวเลขบนเส้นแสดงถึงค่าน้ำหนักของเส้นเชื่อมเส้นนั้นๆ ขั้นตอนวิธีนี้จะเริ่มต้นจากเส้นเชื่อมที่มีน้ำหนักมากสุด ในที่นี้คือเส้น DE ขนาด 15 ถัดมาจึงทำการตรวจสอบว่าถ้าลบเส้นเชื่อมนี้ออกจะทำให้กราฟแยกออกจากกันหรือไม่ถ้าไม่ใช่จึงทำการลบเส้นนี้ออก เส้นถัดมาที่มีขนาดใหญ่รองลงมา คือเส้น FG ดังนั้นขั้นตอนวิธีนี้จึงตรวจสอบว่าถ้าลบเส้นเชื่อม FG ออกแล้ว จะไม่ทำให้กราฟนี้แยกออกจากกัน เส้นเชื่อมที่ขนาดใหญ่ถัดมาคือเส้น BD ซึ่งขั้นตอนวิธีนี้ก็ตรวจสอบเส้นเชื่อมนี้เหมือนเดิมและลบออก ถัดมาคือตรวจสอบเส้น EG ซึ่งปรากฏว่าถ้าลบเส้นเชื่อมนี้ออกจะทำให้กราฟนี้ขาดออกคือมีปม G ที่หลุดออก ทำให้กราฟไม่เชื่อมต่อกัน ดังนั้นจึงข้ามไปยังเส้นเชื่อม BC ต่อไป เส้นถัดมาคือ เส้น EF ขั้นตอนวิธีนี้จึงตรวจสอบเส้นเชื่อมนี้และทำการลบออก
	ขั้นตอนวิธีนี้จะค้นหาเส้นเชื่อมไปเรื่อยๆจนไม่พบเส้นเชื่อมที่ลบต่อไปได้แล้ว หลังจากนั้นก็จะได้กราฟที่เป็น ต้นไม้แผ่ขยายต่ำสุดแล้วคืนค่ากลับไป ดังรูปเส้นเชื่อมสีแดงแสดงถึงเส้นที่ถูกลบไปแล้วและเส้นเชื่อมที่เหลือจะถูกแสดงเป็นสีเขียว

ประสิทธิภาพการทำงาน

ขั้นตอนวิธีนี้สามารถทำงานได้ในเวลา ${\displaystyle O(ElogE(loglogE)3)}$ ซึ่ง ${\displaystyle E}$ คือจำนวนเส้นเชื่อม และ ${\displaystyle V}$ คือจำนวนปม โดยอธิบายการทำงานของเวลาได้ดังนี้

• การจัดเรียงข้อมูลโดยเปรียบเทียบน้ำหนักของเส้นเชื่อมทั้งหมดใช้เวลา ${\displaystyle O(ElogE)}$
• การลบแต่ละครั้งใช้เวลา ${\displaystyle O(1)}$
• การตรวจสอบว่ากราฟเชื่อมต่อกันทุกปมหรือไม่ ใช้เวลา ${\displaystyle O(logV(loglogV)3)}$

ดังนั้นจึงใช้เวลาทั้งสิ้นของขั้นตอนวิธีนี้ ${\displaystyle O(ElogV(loglogV)3)}$

ขั้นตอนวิธีที่เกี่ยวข้อง

• Kruskal's algorithm
• Prim's algorithm
• Borůvka's algorithm
• Dijkstra's algorithm

อ้างอิง

• Kleinberg, Jon; Algorithm Design, New York: Pearson Education, Inc..
• Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", pp. 343–350, doi:10.1145/335305.335345 {{}}: |title= ไม่มีหรือว่างเปล่า ((help)).
• 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 2016-03-04 ที่ เวย์แบ็กแมชชีน
• http://courses.cs.vt.edu/~cs5114/spring2009/lectures/lecture05-greedy-graph-algorithms.pdf