ზურგჩანთის ამოცანის ჰიბრიდული ალგორითმის შესახებ

ავტორი: მაკა ლაბაძე
საკვანძო სიტყვები: ზურგჩანთის ამოცანა, გენეტიკური ალგორითმები, დინამიკური პროგრამირების მეთოდი
ანოტაცია:

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