Kruskal ალგორითმი - მშენებლობა ოპტიმალური ფარგლებში

In მე -19 საუკუნის დასაწყისში geometer Jakob Steiner ბერლინში მითითებული ამოცანა როგორ დაკავშირება სამ სოფელში ისე, რომ მათი სიგრძე უმოკლეს. მოგვიანებით, მან შეაჯამა პრობლემა: ეს არის საჭირო, რათა იპოვოს წერტილი თვითმფრინავი, დაშორება, რომ n სხვა რაოდენობა ყველაზე დაბალი იყო. მე -20 საუკუნეში, იგი აგრძელებს ამ თემაზე მუშაობას. გადაწყდა, რომ რამდენიმე რაოდენობა და დააკავშირებს მათ ისე, რომ მათ შორის მანძილი იყო უმოკლესი. ეს ყველაფერი არის სპეციალური შემთხვევაში პრობლემის შესწავლა მიმდინარეობს.

"ხარბ" ალგორითმი

Kruskal ალგორითმი ეხება "ხარბ" ალგორითმი (ასევე მოუწოდა გრადიენტი). არსი ის - უმაღლესი მოგება თითოეულ ნაბიჯს. არა ყოველთვის, "ხარბ" ალგორითმები უზრუნველყოფს საუკეთესო გამოსავალი პრობლემა. არსებობს თეორია, რომელიც გვიჩვენებს, რომ მათი გამოყენება კონკრეტული ამოცანები აძლევენ ოპტიმალური გადაწყვეტა. ეს არის თეორია matroids. Kruskal ალგორითმი ეხება ასეთი პრობლემები.

მოძიება მინიმალური ალ წონა

ნანახია ალგორითმი აშენებს ოპტიმალური ჩარჩო რაოდენობა. პრობლემა ის არის, ასეთია. Dan undirected გრაფაში გარეშე პარალელურად კიდეები და მარყუჟების და კომპლექტი კიდეები ენიჭება წონის ფუნქცია w, რომელიც ანიჭებს ნომრის თითოეული პირას e - წონა ნეკნი - w (e). წონა თითოეული subset გავურბივარ ნეკნები არის თანხა წონის მისი კიდეები. აუცილებელია, რათა იპოვოს ჩონჩხი მცირე წონა.

აღწერა

Kruskal ალგორითმი მუშაობს. პირველ რიგში, ყველა კიდეებს საწყის გრაფაში მოწყობილი მიმდევრობით წონით. თავდაპირველად, ჩარჩო არ შეიცავს ნეკნები, არამედ ყველა vertices. მას შემდეგ, რაც შემდეგი ნაბიჯი ალგორითმი უკვე აშენებული ნაწილი მდგომარეობაში, რომელიც არის პორტატული ტყეში, ერთ კიდეზე ემატება. ეს არ არის არჩეული თვითნებურად. ყველა კიდეებს გრაფაში, რომლებიც არ ფარგლებში, შეიძლება ეწოდოს წითელი და მწვანე. ზედა ყოველი წითელი კიდეები იმავე კომპონენტი მშენებარე ტყის კავშირით, და მწვანე დაპყრობა - განსხვავებული. აქედან გამომდინარე, თუ თქვენ დაამატოთ წითელი პირას, არის ციკლი, და თუ მწვანე - როგორც შემდეგ მიღებული ეს ნაბიჯი ხის დაკავშირებული კომპონენტი იქნება არანაკლებ ერთი. ამდენად, რის შედეგადაც სამშენებლო არ შეგიძლიათ არ წითელი ზღვარი, მაგრამ რაიმე მწვანე ზღვარზე შეიძლება დაემატოს კიდევ ტყეში. და დასძენს მწვანე პირას მინიმალური წონა. შედეგი არის ფარგლებში მინიმალური წონა.

განხორციელების

აღნიშნავს ტყის F. ეს ყოფს კომპლექტი vertices სფეროში კავშირით (მათი კავშირი ფორმები F, და ისინი disjoint). ორივე კიდეებს წითელი vertices ტყუილი ერთ ჯერზე. ნაწილი (x) - ფუნქცია, რომელიც თითოეული vertex x ბრუნდება ნაწილი სახელი, მას ეკუთვნის x. Unite (x, y) - პროცედურა, რომელიც აშენებს ახალი დანაყოფი, რომელიც შედგება აერთიანებს ნაწილების x და y და ყველა სხვა ნაწილები. მოდით n - ნომერი კიდეები. ყველა ეს ცნებები შედის Kruskal ალგორითმი. განხორციელება:

1. ორგანიზებას ყველა კიდეებს გრაფაში 1 დან n-th აღმავალი წონით. (Ai, bi - i ერთად apex ზღვარზე ნომერი).

2. for i = 1 n გააკეთოს.

3. x = ნაწილი (AI).

4. y = ნაწილი (bi).

5. თუ x არ უდრის y მაშინ Unite (x, y), მოიცავს ერთად ზღვარზე F i ნომერი.

სისწორის

მოდით T - ფარგლებში ორიგინალური გრაფაში აგებულია გამოყენებით Kruskal ალგორითმი და S - მისი თვითნებური ჩარჩო. ჩვენ უნდა დავამტკიცოთ, რომ w (T) არ აღემატება w (S).

მოდით M - გავურბივარ ფარფლები S, P - გავურბივარ ფარფლები T. თუ არ არის ტოლი T, მაშინ არ არის ჩარჩოს ნეკნი და T, რომლებიც არ S. S. et adjoin ციკლი, მას უწოდებენ C. C ამოიღონ ნებისმიერი ზღვარზე es, რომლებიც S. ჩვენ მიიღოს ახალი ჩარჩო, რადგან კიდეებს და წვეროების არის იგივე. მისი წონა არ აღემატება w (S), მას შემდეგ, რაც w (et) აღარ w (es) ხელისუფლებაში Kruskal ალგორითმი. ეს ოპერაცია (შემცვლელი T S ნეკნები ნეკნები) რომელიც უნდა განმეორდეს, რადგან მიიღოს T. წონა ყოველი მომდევნო მიიღო ჩარჩო არ აღემატება წინა წონა, რაც გულისხმობს, რომ w (T) არ აღემატება w (S).

სიმყარე Kruskal ალგორითმი გამომდინარეობს თეორემა Rado-Edmonds on matroids.

გამოყენების მაგალითები Kruskal ალგორითმი

იმის გათვალისწინებით, გრაფაში ერთად vertices a, b, c, d, e და ნეკნები (a, b) (a, e), (ბ, გ), (b, e), (გ, დ), (C, E) (d, e). წონით edges ნაჩვენებია მაგიდაზე და ფიგურა. თავდაპირველად, სამშენებლო ტყის F შეიცავს ყველა vertices გრაფაში და არ შეიცავს რაიმე ნეკნები. ალგორითმი Kruskal დაამატოთ ნეკნი (a, e), რადგან წონა ჰქონდა ყველაზე დაბალი და წვეროების და E არის სხვადასხვა კომპონენტები ხე-ტყის კავშირით F (ნეკნი (a, e) მწვანე), მაშინ ნეკნი (გ, დ), რადგან რომ მინიმუმ ეს ზღვარი წონა გრაფაში კიდეები, რომლებიც არ F, და ეს არის მწვანე, მაშინ იმავე მიზეზით დაერიცხება პირას (a, b). მაგრამ ზღვარზე (b, e) გავიდა, მიუხედავად იმისა, რომ ის და მინიმალური წონა დარჩენილი edges, რადგან ეს არის წითელი: წვეროების ბ და ე ეკუთვნის ამავე კომპონენტის ტყის კავშირით F, რომ არის, თუ დავუმატებთ, რომ F ზღვარზე (b, e), იქმნება ციკლი. შემდეგ დასძინა მწვანე პირას (B, C), რომელიც გადაეცემა წითელი პირას (C, E), და შემდეგ დ, ე. ამდენად, კიდეები ემატება თანამიმდევრულად (a, e), (გ, დ), (a, b), (ბ, გ). მდებარეობა 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 ის ალგორითმი პოულობს პრაქტიკული გამოყენების, მაგალითად, ოპტიმიზაცია gasket კომუნიკაციები, გზების ახალი საცხოვრებელი ადგილას თითოეულ ქვეყანაში, ისევე, როგორც სხვა შემთხვევებში.