დეიქსტრას ალგორითმი

დეიქსტრას ალგორითმი — გამოიყენება შეწონილ გრაფში კვანძებს შორის უმოკლესი გზების მოსაძებნად, რომელიც შეიძლება წარმოადგენდეს, მაგალითად, საგზაო ქსელს. ის შეიმუშავა კომპიუტერულმა მეცნიერმა ედსგერ დეიქსტრამ 1956 წელს და გამოაქვეყნა სამი წლის შემდეგ.

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

ალგორითმი იყენებს მინიმალური პრიორიტეტის რიგის მონაცემთა სტრუქტურას აქამდე ცნობილი უმოკლესი გზების შესარჩევად. სანამ უფრო მოწინავე პრიორიტეტული რიგის სტრუქტურები აღმოაჩენდნენ, დეიქსტრას ორიგინალური ალგორითმი მუშაობდა (||2)
დროში, სადაც || არის კვანძების რაოდენობა. ფრედმანმა და ტარჯანმა 1984 წელს შემოგვთავაზეს ფიბონაჩის მონაცემთა სტრუქტურის პრიორიტეტული რიგი შესრულების დროის სირთულის ოპტიმიზაციისთვის (||+||||). ეს ასიმპტოტურად ყველაზე სწრაფი ცნობილი ერთწყაროანი უმოკლესი გზის ალგორითმია შეუზღუდავი არაუარყოფითი წონებით თვითნებური მიმართული გრაფიკებისთვის. თუმცა, სპეციალიზებული შემთხვევები (როგორიცაა შემოსაზღვრული/მთელი წონები, მიმართული აციკლური გრაფიკები და ა.შ.) შეიძლება კიდევ უფრო გაუმჯობესდეს. თუ წინასწარი დამუშავება დაშვებულია, ასეთი ალგორითმები, როგორიცაა შეკუმშვის იერარქიები, შეიძლება იყოს მეშვიდე საფეხურამდე უფრო სწრაფი.

დეიქსტრას ალგორითმი ხშირად გამოიყენება გრაფებში, სადაც კიდის წონები დადებითი მთელი რიცხვები ან ნამდვილი რიცხვებია. მისი განზოგადება შესაძლებელია ნებისმიერ გრაფზე, სადაც კიდის წონები ნაწილობრივ დალაგებულია, იმ პირობით, რომ შემდგომი იარლიყები (შემდეგი იარლიყი წარმოიქმნება კიდის გადაკვეთისას) მონოტონურად არაკლებადია.

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

ისტორია
დეიქსტრა უმოკლესი გზის პრობლემაზე 1956 წელს, ამსტერდამის მათემატიკურ ცენტრში პროგრამისტად მუშაობისას ფიქრობდა. მას სურდა ახალი კომპიუტერის შესაძლებლობების დემონსტრირება. მისი მიზანი იყო ისეთი პრობლემისა და კომპიუტერული გადაწყვეტის არჩევა, რომელიც არაკომპიუტერული ადამიანებისთვის გასაგები იქნებოდა. მან შეიმუშავა უმოკლესი გზის ალგორითმი და მოგვიანებით -ისთვის დანერგა ნიდერლანდების 64 ქალაქის ოდნავ გამარტივებული სატრანსპორტო რუკისთვის (მან ის 64-მდე შეზღუდა, რათა 6 ბიტი საკმარისი ყოფილიყო ქალაქის ნომრის კოდირებისთვის). ერთი წლის შემდეგ, იგი წააწყდა კიდევ ერთ პრობლემას, რომელიც ინსტიტუტის შემდეგ კომპიუტერზე მომუშავე ტექნიკის ინჟინრებმა წამოჭრეს: მინიმუმამდე დაეყვანათ მავთულის რაოდენობა, რომელიც საჭირო იყო მანქანის უკანა პანელზე პინების შესაერთებლად. გამოსავლის სახით, მან ხელახლა აღმოაჩინა პრაიმის მინიმალური გამჭოლი ხის ალგორითმი (რომელიც ადრე იარნიკისთვის იყო ცნობილი და ასევე ხელახლა აღმოაჩინა პრაიმმა). დეიქსტრამ ალგორითმი 1959 წელს გამოაქვეყნა, პრაიმიდან ორი წლის შემდეგ და იარნიკიდან 29 წლის შემდეგ.

ალგორითმი
ალგორითმს სჭირდება საწყისი კვანძი და ითვლის ამ საწყისი კვანძიდან ყველა სხვა კვანძამდე უმოკლეს მანძილს. დეიქსტრას ალგორითმი იწყება უსასრულო მანძილებით და ცდილობს მათ ეტაპობრივად გაუმჯობესებას:

შექმენით ყველა დაუთვალიერებელი კვანძის სიმრავლე: დაუთვალიერებელი კვანძების სიმრავლე.
ყველა კვანძს, დაწყებული საწყისიდან, მიანიჭეთ მანძილის მნიშვნელობა: საწყისი კვანძისთვის ის ნულის ტოლია, ხოლო ყველა სხვა კვანძისთვის უსასრულობაა, რადგან თავდაპირველად ამ კვანძებამდე გზა არ არის ცნობილი. შესრულების დროს, კვანძამდე მანძილი არის საწყის კვანძსა და -ს შორის იმ დროისთვის ნაპოვნი უმოკლესი გზის სიგრძე.
დაუთვალიერებელი კვანძების სიმრავლიდან აირჩიეთ მიმდებარე კვანძი, რომელსაც აქვს ყველაზე მცირე (სასრული) მანძილი; თავდაპირველად, ეს არის საწყისი კვანძი (მანძილი ნული). თუ დაუთვალიერებელი კვანძების სიმრავლე ცარიელია ან შეიცავს მხოლოდ უსასრულო მანძილის მქონე კვანძებს (რომლებიც მიუწვდომელია), მაშინ ალგორითმი მთავრდება მე-6 ნაბიჯზე გადასვლით. თუ ერთადერთი საზრუნავი სამიზნე კვანძისკენ მიმავალი გზაა, ალგორითმი მთავრდება, როგორც კი მიმდინარე კვანძი სამიზნე კვანძი გახდება. წინააღმდეგ შემთხვევაში, ალგორითმი გრძელდება.
მიმდინარე კვანძისთვის გაითვალისწინეთ მისი ყველა მოუნახულებელი მეზობელი და განაახლეთ მათი მანძილები მიმდინარე კვანძიდან; შეადარეთ ახლად გამოთვლილი მანძილი მეზობლისთვის ამჟამად მინიჭებულ მანძილს და მიანიჭეთ მას უფრო მცირე მანძილი. მაგალითად, თუ მიმდინარე კვანძი აღნიშნულია 6 მანძილით და მის მეზობელ -სთან დამაკავშირებელ კიდეს აქვს 2 სიგრძე, მაშინ -მდე მანძილი -ს გავლით არის 6 + 2 = 8. თუ ადრე აღნიშნული იყო 8-ზე მეტი მანძილით, მაშინ განაახლეთ ის 8-მდე (-მდე გზა -ს გავლით უფრო მოკლეა). წინააღმდეგ შემთხვევაში, შეინარჩუნეთ მისი მიმდინარე მანძილი (-მდე გზა -ს გავლით არ არის უმოკლესი).
მიმდინარე კვანძის ყველა მოუნახულებელი მეზობლის განხილვის შემდეგ, მიმდინარე კვანძი ამოღებულია მოუნახულებელი ნაკრებიდან. ამრიგად, მონახულებული კვანძი არასდროს მოწმდება ხელახლა, რაც სწორია, რადგან მიმდინარე კვანძზე ჩაწერილი მანძილი მინიმალურია (როგორც ეს უზრუნველყოფილია მე-3 ნაბიჯში) და შესაბამისად, საბოლოოა. გაიმეორეთ მე-3 ნაბიჯიდან.
ციკლის დასრულების შემდეგ (ნაბიჯები 3–5), ყველა მონახულებული კვანძი შეიცავს თავის უმოკლეს მანძილს საწყისი კვანძიდან.

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

მიმდინარე გზაჯვარედინიდან, ყველა მეზობელ (პირდაპირ დაკავშირებულ) გზაჯვარედინამდე მანძილი ფასდება მიმდინარე გზაჯვარედინის იარლიყის (მნიშვნელობის) და მეზობელამდე მანძილის შეჯამებით და შემდეგ მეზობელს ხელახლა ენიჭება ამ ჯამისა და მეზობლის არსებული იარლიყის უმცირესი ნიშნულით. ანუ, მეზობელს ხელახლა ენიჭება იარლიყი, თუ მიმდინარე გზაჯვარედინზე მისასვლელი გზა უფრო მოკლეა, ვიდრე ადრე შეფასებული ბილიკები. თუ ასეა, მეზობელამდე გზა მონიშნეთ მასზე მიმართული ისრით და წაშალეთ ნებისმიერი სხვა ისარი, რომელიც მასზე მიუთითებს. მიმდინარე გზაჯვარედინის თითოეულ მეზობელამდე მანძილის შეფასების შემდეგ, მიმდინარე გზაჯვარედინი მონიშნულია, როგორც მონახულებული. ყველაზე პატარა იარლიყით დაუთვალიერებელი გზაჯვარედინი ხდება მიმდინარე გზაჯვარედინი და პროცესი მეორდება მანამ, სანამ არ მოინახულებთ ყველა კვანძს, რომლის იარლიყიც დანიშნულების ადგილის იარლიყზე ნაკლებია.

როგორც კი აღარ დარჩება დაუთვალიერებელი კვანძი, რომლის ჭდე დანიშნულების ადგილის ჭდეზე პატარაა, დარჩენილი ისრები უმოკლეს გზას აჩვენებს.

ფსევდოკოდი
შემდეგ ფსევდოკოდში, არის მასივი, რომელიც შეიცავს მიმდინარე მანძილებს სხვა ვერტიკებისკენ, მაგ. არის წყაროდან წვერომდე მიმდინარე მანძილი. ის მასივი შეიცავს მითითებებს წინა ნახტომის კვანძებზე წყაროდან მოცემულ წვერომდე უმოკლეს გზაზე (ექვივალენტურად, ეს არის შემდეგი ნახტომი მოცემული წვეროდან წყარომდე გზაზე). კოდი, ეძებს წვეროს წვეროების სიმრავლეში რომელსაც ყველაზე ნაკლები აქვს მნიშვნელობა. . აბრუნებს ორ მეზობელ კვანძს შორის შემაერთებელი კიდის სიგრძეს (ანუ მანძილს). და . ცვლადი მე-14 ხაზზე არის გზის სიგრძე კვანძი მეზობელ კვანძამდე თუ ის გაივლიდა. თუ ეს გზა უფრო მოკლეა, ვიდრე ამჟამად ჩაწერილი უმოკლესი გზა, მაშინ მანძილი განახლებულია

1 :
2
3 .:
4 [] ← 
5 [] ← 
6 
7 [] ← 0
8
9 :
10 ← []
11 .
12
13 :
14 ← [] + .
15 ამოცანა 2. იპოვეთ მინიმალური საერთო სიგრძის გზა ორ მოცემულ და კვანძს შორის. ჩვენ ვიყენებთ იმ ფაქტს, რომ თუ არის კვანძი -დან -მდე მინიმალურ გზაზე, ამ უკანასკნელის ცოდნა გულისხმობს -დან -მდე მინიმალური გზის ცოდნას.

არის ბელმანის ოპტიმალურობის პრინციპის პერიფრაზირება უმოკლესი გზის პრობლემის კონტექსტში.