อัลกอริทึมของ Kruskal - การก่อสร้างของกรอบที่เหมาะสม

ในช่วงต้นศตวรรษที่ 19 เรขาคณิตจาค็อบสไตเนอร์จากเบอร์ลินตั้งค่างานของวิธีการเชื่อมต่อสามหมู่บ้านเพื่อให้ยาวของพวกเขาเป็นที่สั้นที่สุด ต่อมาเขาสรุปปัญหา: มันเป็นสิ่งจำเป็นที่จะหาจุดในระนาบที่ระยะห่างจากมันถึง n จุดอื่น ๆ ได้ต่ำสุด ในศตวรรษที่ 20 ก็ยังคงทำงานในหัวข้อนี้ ก็ตัดสินใจที่จะใช้เวลาไม่กี่จุดและเชื่อมต่อพวกเขาในลักษณะที่ว่าระยะห่างระหว่างพวกเขาเป็นที่สั้นที่สุด ทั้งหมดนี้เป็นกรณีพิเศษของปัญหาการศึกษา

"โลภ" อัลกอริทึม

อัลกอริทึมของ Kruskal หมายถึง "ความโลภ" อัลกอริทึม (เรียกว่าการไล่ระดับสี) สาระสำคัญของเหล่านั้น - ชนะสูงสุดในแต่ละขั้นตอน ไม่เสมอไป "โลภ" ขั้นตอนวิธีการให้ทางออกที่ดีที่สุดในการแก้ไขปัญหา มีทฤษฎีเป็นแสดงให้เห็นว่าในใบสมัครของพวกเขาเพื่องานเฉพาะที่พวกเขาให้การแก้ปัญหาที่เหมาะสม นี่คือทฤษฎีของ matroids อัลกอริทึม Kruskal หมายถึงปัญหาดังกล่าว

การหาน้ำหนักซากขั้นต่ำ

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

ลักษณะ

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

การดำเนินงาน

แสดงว่าป่าในปัจจุบันเอฟมันแบ่งชุดของจุดในด้านการเชื่อมต่อ (แบบฟอร์มสหภาพของพวกเขา F และพวกเขาจะไม่เป็นสมาชิกร่วม) ที่ขอบทั้งสองด้านของจุดสีแดงพวกเขาอยู่ในชิ้นเดียว ชิ้นส่วน (x) - ฟังก์ชั่นที่แต่ละจุดสุดยอด x ผลตอบแทนที่ได้เป็นส่วนหนึ่งของชื่อมันเป็น x Unite (x, y) - ขั้นตอนที่สร้างพาร์ทิชันใหม่ประกอบด้วยการรวมส่วนของ x และ y และทุกส่วนอื่น ๆ ที่ ให้ n - จำนวนของขอบ แนวคิดเหล่านี้จะรวมอยู่ในขั้นตอนวิธีของครูสกาล การดำเนินงาน:

1. จัดขอบทั้งหมดของกราฟตั้งแต่วันที่ 1 เพื่อ n-TH น้ำหนักน้อยไปหามาก (AI, สอง - ฉันที่มีจำนวนขอบปลาย)

2. สำหรับ i = 1 ถึง n ทำ

3. x = ชิ้นส่วน (AI)

4. Y: = ชิ้นส่วน (BI)

5. ถ้า x ไม่ Y ไม่เท่ากันแล้ว Unite (x, y) ที่จะรวมกับจำนวน F ฉันขอบ

ความถูกต้อง

ให้ T - กรอบรูปแบบของกราฟเดิมสร้างขึ้นโดยใช้อัลกอริทึม Kruskal และ S - กรอบโดยพลการของตน เราต้องพิสูจน์ว่า W (T) ไม่เกิน W (S)

Let M - ส่วนใหญ่ของครีบ S, P - เป็นส่วนใหญ่ของครีบ T. ถ้า S ไม่เท่ากับ T แล้วมีกรอบซี่โครง et T, ไม่ได้อยู่ในเอสเอสเอตติดกับวงจรก็จะเรียกว่าซีซีลบออกจาก ES ขอบใด ๆ ที่อยู่ S. เราได้รับเฟรมใหม่เพราะขอบและจุดเหมือนกัน น้ำหนักไม่เกิน W (S) ตั้งแต่ W (เอ) ไม่ W (e) ในขั้นตอนวิธีการพลังงาน Kruskal การดำเนินการนี้ (แทนซี่โครง T S บนซี่โครง) จะต้องทำซ้ำตราบใดที่ได้รับตันน้ำหนักของแต่ละเฟรมที่ได้รับตามมาคือไม่เกินน้ำหนักก่อนหน้านี้ซึ่งหมายความว่า W (T) ไม่เกิน W (S)

ทนทานของอัลกอริทึมของ Kruskal ดังนี้จากทฤษฎีของ Rado-เอ็ดมันด์ใน matroids

ตัวอย่างการประยุกต์ใช้อัลกอริทึม Kruskal

แดนกราฟที่มีโหนด A, B, C, D, E และซี่โครง (A, B), (A, E), (B, C), (B, E), (C, D), (C, E) (D, E) น้ำหนักของขอบที่แสดงอยู่ในตารางและในรูป ในขั้นต้นป่าก่อสร้าง F มีจุดทั้งหมดของกราฟและไม่ได้มีซี่โครงใด ๆ อัลกอริทึม Kruskal แรกเพิ่มซี่โครง (A, E) ตั้งแต่น้ำหนักได้ต่ำสุดและจุดและอีอยู่ในชิ้นส่วนที่แตกต่างกันการเชื่อมต่อไม้ F (ซี่โครง (A, E) เป็นสีเขียว) แล้วซี่โครง (C, D) เพราะ ว่าอย่างน้อยนี้น้ำหนักขอบของขอบกราฟที่ไม่ได้อยู่ F และมันเป็นสีเขียวแล้วด้วยเหตุผลเดียวกันเกิดขึ้นขอบ (A, B) แต่ขอบ (ข, E) จะถูกส่งถึงแม้ว่าเขาและน้ำหนักต่ำสุดของขอบที่เหลือเพราะมันเป็นสีแดง: จุดที่ขและ e เป็นองค์ประกอบเดียวกันของการเชื่อมต่อป่า F, ที่อยู่, ถ้าเราเพิ่ม F ขอบ (ข, E) จะถูกสร้างขึ้น วงจร จากนั้นเพิ่มขอบสีเขียว (B, C) จะถูกส่งผ่านขอบสีแดง (C, E) แล้ว D, E ดังนั้นจึงมีการเพิ่มขอบตามลำดับ (A, E), (C, D), (A, B), (B, C) จาก nihera กรอบที่เหมาะสมและประกอบด้วยกราฟเดิม ดังนั้นในกรณีนี้จะดำเนินการขั้นตอนวิธี Kruskal ตัวอย่างที่แสดงให้เห็น

ภาพแสดงกราฟซึ่งประกอบด้วยสององค์ประกอบที่เกี่ยวโยงกัน เส้นหนาระบุที่ดีที่สุดซี่โครงกรอบ (สีเขียว) สร้างขึ้นโดยใช้อัลกอริทึม Kruskal

ภาพด้านบนแสดงให้เห็นถึงรูปแบบของกราฟเดิมและด้านล่าง - โครงกระดูกของน้ำหนักที่น้อยที่สุดที่สร้างขึ้นสำหรับเขาโดยใช้อัลกอริทึม

ลำดับของซี่โครงเพิ่ม (1.6); (0,3), (2,6) หรือ (2,6), (0,3) - ไม่ได้เป็นสำคัญ (3,4); (0,1), (1,6) หรือ (1,6), (0,1) ยังดูแล (5,6)

อัลกอริทึมของ Kruskal พบการประยุกต์ใช้ในทางปฏิบัติเช่นการเพิ่มประสิทธิภาพการสื่อสารปะเก็น, ถนนในเมืองใหม่โครงการบ้านจัดสรรในแต่ละประเทศเช่นเดียวกับในกรณีอื่น ๆ