Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

5.7. Budaqlar və sərhədlər üsulu ilə minimal uzunluqlu Hamilton konturunun axtarışı

Əvvəlki mövzuda informasiyanın axtarışının ümumi prinsiplərinə baxılmışdı. Bundan başqa tədqiqat obyektindən asılı olaraq müxtəlif axtarış üsullarından istfadə oluna bilər, məsələn, qraflarda və şəbəkələrdə optimal yolların (planların) qurulması üçün budaqlar və sərhədlər üsulundan istfadə etmək olar[13,14]. Üsulun həll sxemi aşağıdakı kimidir. Fərz edək ki, a məsələsini həll etmək lazımdır. Bunun həlli a₁, a₂ alternativ məsələlərin həllinə gətirilir. Sonuncuların hər biri üçün də alternativlər qurulur. Sonda hansısa bir mərhələdə qurulan məsələ sadə üsulla həll oluna bilər.

Buna misal olaraq kommivayajer məsələsini nəzərdən keçirək. Bu məsələyə bəzən “səyyar tacir” məsələsi deyilir. Kommivayajerin vəzifəsi müəyyən bir şəhərdən, məsələn, 1 nömrəlidən başlayaraq bütün şəhərləri yalnız bir dəfə keçməklə həmin şəhərə ən qısa yolla ( və ya ən qısa zaman ərzində) qayıtmaqdır. Belə məsələ ilə səyyar tacir də, poçtalyon da və s. insanlar da qarşılaşa bilər. Fərz edək, baxılan sistemdə yalnız 4 şəhər mövcuddur.
Cədvəl 5.3
Şəhərlər arasında birbaşa məsafələrin davamiyyəti

j i	1	2	3	4
1	M	5	11	9
2	10	M	8	7
3	7	14	M	8
4	12	6	15	M

Cədvəl 5.3-də i və j ilə şəhərlər nömrələnib. Cədvəldən göründüyü kimi 1 nömrəli şəhərin varisləri 2,3,4 nömrəli şəhərlərə qədər birbaşa məsafələri qət etmək üçün zamanlar t(1,2)=5, t(1,3)=11, t(1,4)=9 qeyd edilib.

Qraflar nəzəriyyəsində bu məsələyə minimal uzunluqlu Hamilton konturunun tapılması məsələsi deyilir. Məsələnin ən primitiv, ancaq ən çətin yolu tam seçmə ağacının (aşkar ağacın) qurulmasından ibarətdir. Aydındır ki, n-in böyük qiymətlərində bu məsələni tam seçmə üsulu ilə həll etmək qeyri – mümkündür, çünki ağacın yarpaqlarının sayı (n-1)! düsturu ilə qiymətləndirilir ki, bu da n artdıqca daha böyük sürətlə artır. Ona görə də budaqlar və sərhədlər üsulunu tətbiq edək. Bu üsul həll ağacını bütövlükdə yox, onun müəyyən hissəsini qurmaqla hesablamanı sadələşdirə bilir. Hesablamanın hər addımında həll ağacının yalnız zəruri olan hissəsi qurulur, ona görə də bu ağaca qeyri-aşkar ağac deyilir. Yaddaşa və zamana qənaət naminə ağacın budaqlanmasına müəyyən məhdudiyyət qoyulur. ”Budaqlar və sərhədlər üsulu” adı da buradan götürülüb.


1(1)

2 (2) 3(3) 4(4)

5 (3) 6(4) 7(2) 8(4) 9(2) 10(3)

11(4) 12(3) 13(4) 14(2) 15(3) 16(2)

17(1) 18(1) 19(1) 20(1) 21(1) 22(1)

Şək. 5.6. Aşkar ağac modeli ilə kommivoyajer məsələsinin tədqiqi

Qeyri–aşkar ağacı qurmaq üçün funksiyasından istifadə olunur. ə qiymətləndirmə funksiyası deyilir. Bu funksiyanın vəzifəsi ağacın başlanğıc düyünündən yarpaq tiplı düyünə qədər x nömrəli düyündən keçməklə minimal yolun uzunluğunun aşağı həddini qiymətləndirməkdir. funksiyasını qiymətləndirmək üçün funksiyalarından istifadə olunur. başlanğıc düyündən x nömrəli düyünə qədər minimal yolun dəqiq qiymətini aposterior, yəni təcrübədən (bəzən sınaqdan deyirlər) sonra toplanan informasiya əsasında qiymətləndirir, g(x) funksiyası isə cari düyündən məqsəd düyününə qədər minimal yolun aşağı qiymətini ifadə edir və aprior, yəni təcrübədən əvvəl toplanan informasiya əsasında qiymətləndirir. Bu funskiya şəhərlər arasında birbaşa məsafələr cədvəlindən istfadə əsasında qurulur. Bizim baxdığımız misal əsasında g(x) funksiyası belə qurulur.

Cədvəldən göründüyü kimi ən kiçik çəki əmsalı 5-ə bərabərdir. Kommivayajer 1-dən çıxıb 1-ə qayıtmaq üçün 4 mərhələ keçməlidir. Odur ki 1-ci şəhərdən 1-ci şəhərə ixtiyari Hamilton koturunun uzunlğu 4 5=20-dən az deyil.Eyni qayda ilə ixtiyari iki i və j düyünləri arasında məsafənin aşağı həddi aprior informasiya ilə qiymətləndirilə bilər.
g(x) = 5 ( “x” nömrəli düyündən məqsəd düyününə qədər minimal sayda addımların sayı).“5” ədədi baxdığımız cədvəldə minimal element kimi g(x)-in hesablanması düsturuna daxil edilib. Aşkar ağac qurulanda hər bir düyünün nömrəsi iki hissədən ibarətdir: mötərizənin daxilində düyünün proobrazı, yəni şəhərlər arasında birbaşa məsafələrin cədvəlindən götürülmüş nömrəsi qeyd edilir, mötərizənin qarşısında isə düyünün ağacda tutduğu mövqeyə görə yeni nömrəsi (obraz) qeyd edilib. Ikiqat nömrələmə ona görə yerinə yetirilib ki, düyünlərin obrazları olmasaydı, hər bir nömrəyə-proobraza qarşı bir neçə düyün qarşı qoymalı olardıq, bu da hesablamaya çətinlik gətirərdi.
Razılaşaq ki, f, h, g funksiyasının hər birində arqumenti x həmişə obrazı göstərir. Aşkar ağac əsasında f, h, g funksiyalarının qiymətləndirilməsi qaydasını göstərək.
g(2)= 5 3=15, h(2)=5, f(2)=15+5=20,
g(3)= 5 3=15, h(3)=11, f(3)=15+11=26,
g(4)= 5 3=15, h(4)=9, f(4)=15+9=24,
g(5)= 5 2=10, h(5)=5+8=13, f(5)=10+13=23,
g(6)= 5 2=10, h(6)=5+7=12, f(6)=10+12=22, və s.
Qeyd edək ki, aprior informasiya əsasında qurulan g(x) funksiyasının hesablanmasına müəyyən qədər faydalı informasiyanı qatmaqla hesablamanı bir qədər də sürətləndirmək olar. Yuxarıda qeyd etmişdik ki, g(x) funksiyası cari düyündən məqsəd düyününə qədər minimal yolun aşağı qiymətini ifadə edir və aprior, yəni təcrübədən əvvəl toplanan informasiya əsasında qiymətləndirir. Ən pis halda g(x)=0 qəbul etmək olar, lakin bu məqsədəuyğun deyil, əksinə, elə etmək lazımdır ki, g(x) mümkün qədər yuxarı qiymət alsın. Bunun yollarından biri x-in varis düyünlərinə qədər minimal məsafəni aposterior informasiya olaraq g(x)-in hesablanmasına qatmaqdan ibarətdir. Belə olan halda, məsələn, g(4)= 5 3=15 hesablamaq əvəzinə g(4)= 5 2+6=16 hesablanarsa, qeyri – aşkar ağacın qurulması daha da sürətlənər. min(t(4,2),t(4,3))= min(6,15)=6 qiyməti g(4)-ün hesablanmasına qatıldı.
Qeyri – aşkar ağacı quran zaman da obraz və proobrazlardan istfadə olunur. Üsulun konseptual həll alqoritmi aşağıdakı kimidir:
1) cədvəlin xanalarında olan minimal məsafə (yaxud dəyər) aprior informasiya olaraq istifadə olunur,
2) yuxarıda qeyd olunan dəyərdən və məqsədə çatmaq üçün qarşıdakı addımların sayından g(x) funksiyası qurulanda bunların hasili kimi istfadə olunur,
3)h(x) funksiyası qiymətləndiriləndə başlanğıc düyündən x-nömrəli düyünə qədər keçilən yol tillər üzərindəki dəyərlər toplanaraq hesablanır,
4)qeyri- aşkar ağac üzərində düyünlər varisi olan və varisi olmayan qruplara bölünür. Hansı düyünün varisi qurulubsa həmin düyün qapanır,
5)hər dəfə açıq, yəni hələ qapanmayan düyünlərdən budaqlanma üçün eləsi seçilir ki, f(x) funksiyasının qiyməti həmin düyündə, həmin zamanda minimum olsun,
6) əgər açıq tipli düyünlərdən birində f(x) funskiyasının qiyməti minimum olarsa, deməli məqsədə çatılıb və f(x)-in qiyməti minimal Hamilton konturunun qiymətidir.