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

Şək.5.7. Qeyri-aşkar ağac modeli ilə “budaqlar və sərhədlər” üsulunun kommivoyajer məsələsinə tətbiqi

f(2)=5+7+2 5=22,

f(3)=11+8+2 5=29,
f(4)=9+6+2 5=25,
f(5)=13+8+5=26,
f(6)=12+15+5=32,
f(7)=15+8+5=28,
f(8)=24+14+5=43,
f(9)=21+12=33,
f(10)=23+7=30,
f(11)=25+7+5=37,
f(12)=19+6+5=30.
Nəhayət, minimal Hamilton konturunun davamiyyəti f(10)=30 və buna uyğun yolun topologiyası budur: 1,4,2,3,1.
Kommivoyajer məsələsinin həllı üçün “budaqlar və sərhədlər” üsulunun ağacdan istifadə etməyən bir variantı var ki, bu da praktiki cəhətdən daha əlverişlidir. Bu halda hesablama yalnız verilənlər matrisi üzərində aparılır. Müvafiq alqoritm aşağıdakı addımlardan ibarətdir:
1. ilkin verilənlər matrisinin, yəni şəhərlər arasında birbaşa məsafələrin cədvəlinin qurulması;
2. sətirlər üzrə minimal elementlərin seçilməsi;
3. sətirlərin reduksiyası;
4. sütunlar üzrə minimal elementlərin seçilməsi;
5. sütunların reduksiyası;
6. sıfıra bərabər məzmunlu xanaların qiymətləndirilməsi;
7. matrisin reduksiyası;
8. əgər minimal Hamilton konturu hələ tam qurulmayıbsa, keç 2-ci addıma, əks halda keç 9-cu addıma;
9. minimal Hamilton konturunun və onun davamiyyətinin çap edilməsi.
Bu alqoritmi 4 şəhəri əhatə edən qrafa tətbiq edək. Bu modelə biz artıq qeyri-aşkar ağac modelindən istifadə əsasında “budaqlar və sərhədlər” üsulunu tətbiq etmişik. Bu dəfə ağac modelindən istifadə olunmayacaq, yalnız cədvəl üzərində çevirmələr aparılacaq.
1. İlkin verilənlər matrisinin qurulması. Bu matris aşağıda təsvir olunub:

Şəhərlər	1	2	3	4
1		5	11	9
2	10		8	7
3	7	14		8
4	12	6	15

Bizim misalda cəmi 4 şəhər haqqında informasiya mövcuddur, cədvəldə hər şəhərdən digər 3 şəhərə məsafələr əks olunub. Hər şəhərin özündən özünə məsafə ilə işarə olunub. Burada şəhərin özündən özünə məsafənin -a bərabər hesab olunması şəhərin özündən özünə qayıdışın qarşısını almağa xidmət edir.

2. Sətirlər üzrə minimal elementlərin seçilməsi. Hər i nömrəli sətir üzrə minimal elementi c_i ilə işarə edək: c₁= 5, c₂=7, c₃=7, c₄=6.
3. Sətirlərin reduksiyası. Hər sətrin bütün elementlərindən bu sətrə uyğun c_i ədədini çıxaq. Bu əməliyyat nəticəsində hər sətirdə ən azı bir ədəd sıfır saxlayan xana olacaq.

Şəhərlər	1	2	3	4
1		0	6	4
2	3		1