คุยกับผู้ใช้:Champion ks

ยินดีต้อนรับสู่วิกิพีเดียภาษาไทย

ยินดีต้อนรับคุณ Champion ks สู่วิกิพีเดียภาษาไทย หน้าต่อไปนี้อาจเป็นประโยชน์แก่คุณ:

มือใหม่ขอแนะนำอย่างยิ่งให้คุณเริ่มจากแก้หรือต่อเติมบทความที่มีอยู่แล้วก่อน ไม่ควรรีบสร้างบทความด้วยตัวเองเพราะมักไม่ผ่านและถูกลบ

แนะนำเว็บ

และ

เรียนรู้การแก้ไข (ขอใช้เวลาอ่านไม่นานเพื่อให้ทราบพื้นฐาน)

อีกทางหนึ่ง อ่านหน้า การเข้ามีส่วนร่วมในวิกิพีเดีย ซึ่งสรุปทุกอย่างไว้หน้าเดียว

ฉันอ่านหมดแล้วยังไม่เข้าใจเลย

ถามที่แผนกช่วยเหลือ หรือ หรือ ใช้ แชตดิสคอร์ด

อย่าลืมลงชื่อในหน้าพูดคุย โดยการพิมพ์ --~~~~ จะปรากฏชื่อและวันเวลา

Hello Champion ks! Welcome to Thai Wikipedia. If you are not a Thai speaker, you can ask a question in our Guestbook.

-- 21:16, 12 กันยายน 2554 (ICT)

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

ขั้นตอนวิธีการลบย้อนกลับ(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 ทั้งหมด }

ขั้นตอนวิธีนี้สามารถทำงานได้ในเวลา 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)

อ้างอิง

• Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design, New York: Pearson Education, Inc..
• Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", Proc. 32nd ACM Symposium on Theory of Computing, pp. 343–350, doi:10.1145/335305.335345.

ยินดีต้อนรับสู่วิกิพีเดียไทย

อย่าลืมดูหน้า วิกิพีเดีย:ศาลาชุมชน/อภิปราย/บทความวิทยาการคอมพิวเตอร์ ด้วยนะครับ --taweethaも 10:04, 17 กันยายน 2554 (ICT)