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

1.3. Aşağıdan yuxarıya yanaşma üsulu ilə alqoritmlərin qurulması
Bu yanaşma əvvəlki üsulun tam əksinədir. Üsul yerinə yetirilən zaman məsələnin həlli üçün əks istiqamətdə düşüncə tərzindən istifadə olunur[11,17]. Bunu həndəsi olaraq təsvir etməyə çalışaq. Tutaq ki, hər hansı məsələnin həlli verilmiş başlanğıc A_b situasiyası əsasında sonda A_s situasiyasına gəlib çatmaqdan ibarətdir. Bu yanaşma ilə əvvəlcə A_s situasiyasına gətirib çıxardan bir addım əvvəlki situasiyalara baxılır. Tutaq ki, bunlar A₁ və A₂-dir. Sonra sonuncuların hər birinin qurulmasından əvvəlki situasiyanın varlığı araşdırılır.


A_s
A₁ A₂


Şək. 1.7 Aşağıdan yuxarıya yanaşma üsulunun həndəsi şərhi
Elə məsələlər var ki, onların aşağıdan yuxarıya, yaxud yuxarıdan aşağıya üsulla həllərinin digərinə nisbətən üstünlüyü yoxdur, məsələn, hanoy qülləsi haqqında məsələ. Məqsəd diskləri birinci çubuqdan sonuncu çubuğa köçürmək olarsa, kiçik, orta və böyük disklər əvəzinə “1”, “2”, “3” rəqəmlərindən, çubuqlar əvəzinə massivin 1-ci, 2-ci, və 3-cü sütunlarından istifadə etməklə bu məsələni geriyə çəkilmək üsulu ilə (yəni aşağıdan yuxarıya yanaşma üsulu ilə) şəkil 1.8-də təsvir olunduğu kimi araşdırmaq olar.

		1
		2
		3

A_s

		2
	1	3

		2
1		3

A₁ A₂

Şək. 1.8. Üç diskdən ibarət hanoy qülləsi məsələsinin aşağıdan yuxarıya yanaşma üsulu ilə həllinin həndəsi şərhi
Məsələni yuxarıdan aşağıya yanaşma üsulu ilə araşdırsaq, bu fraqmentə tam simmetrik bir fraqment alınar. Deməli, bu məsələyə görə yanaşmalardan heç birinin digəri ilə müqayisədə üstünlüyü olmadı.

1
2
3

A_b

2
3	1

2
3		1

A₁

A₂


Şək. 1.9. Üç diskdən ibarət hanoy qülləsi məsələsinin yuxarıdan aşağıya yanaşma üsulu ilə həllinin həndəsi şərhi

Lakin geridən yanaşma üsullarının bir sıra məsələlərin həllində əhəmiyyəti aşağıdakılardan ibarətdir: 1) verilmiş məsələnin yuxarıdan aşağıya həll üsulu yoxdur; 2) verilmiş məsələnin hər iki üsulla həlli var, ancaq 1-ci və 2-ci üsulların kombinasiyalarından istifadə etməklə məsələnin həllini sürətləndirmək, yaddaşa qənaət etmək olar.

Indi də elə məsələyə baxaq ki, bunun həllini geridən yanaşma üsulu ilə yerinə yetirmək daha əlverişlidir.
Məsələ 1. Verilmiş ağacda ağacın kökü ilə yarpaq tipli düyünlər arasında ən qısa yolun və bunun topologiyasının qurulması məsələsinə baxaq.

156651



256651

356651
1 10
9

756651

456651

556651

656651
5 2 7



856651

956651
4 3 6 8

100

11


Şək. 1.10. Minimal yolu axtarılan ağac modeli

Ağacın 11 düyünü var, bunlar müvafiq surətdə 1,...,11 ilə işarə olunmuşdur. Düyünləri birləşdirən tillər üzərinə müvafiq çəki əmsalları yazılmışdır: t_1,2=1, …, t_7,11=8.

Ağac modelini D ilə, bunun elementlərini X və A ilə işarə edək: D=(X,A). Burada A- tillər çoxluğu, X- düyünlər çoxluğudur. Baxılan misalda X={1,...,11}. Bu ağacda düyünləri üç qrupa bölmək olar: X=X_y X_d X_u. Burada X_y –yarpaq tipli düyünlər çoxluğu, X_d- dizyunktiv düyünlər çoxluğu, X_u – unar düyünlər çoxluğudur. X_y={8,9,10,11}, X_d= {1,2,3}, X_u={4,5,6,7}.
Qoyulmuş məsələni həll etmək üçün iki parametr daxil etmək lazımdır [10]: T(i) – diksret funksiyadır, rekursiv olaraq aşağıdan yuxarıya hesablanır , i düyünündən ağacın hər hansı yarpağına qədər ən qısa məsafənin davamiyyətini göstərir. Q_i – bu bir çoxluqdur, ağacın yarpaqlarından başlayaraq onun kökünə doğru aşağıdan yuxarıya qiymətləndirilir. Bu parametrin vəzifəsi i nömrəli düyündən hər hansı yarpağa qədər ən qısa məsafəyə aid olan yolun topologiyasını müvafiq tillər çoxluğu vasitəsilə təsvir etməkdən ibarətdir. Qeyd edək ki, ümumiliyi pozmadan unar tipli düyünləri də dizyunktiv düyünlər çoxluğuna aid etmək olar, ona görə də aşağıda təsvir olunan alqoritmdə unar düyünlər üçün T(i) funksiyasına ayrıca baxılmayıb.
1-ci addım. Yarpaq tipli düyünlər üçün bu parametrlərin hesablanması.
T(i)=0 (1.1)
Q_i= (1.2)
2-ci addım. Digər düyünlər üçün bu parametrlərin hesablanması. Ümumiliyi pozmadan fərz etmək olar ki, i nömrəli düyünün σ qədər varis düyünləri var. Bunları x_i1, x_i2,..., x_iσ ilə işarə edək.
T(i)= t_i,j + T(j)}=t_i,j0+T(j₀) (1.3)
Q_i=(x_i,x_i,j0) Q_j0 (1.4)
Bu alqoritmi baxılan misala tətbiq edək:
T(8),T(9),T(10),T(11)=0,
Q₈,...,Q₁₁= ,
T(4)=4 ,T(5)= 3 ,T(6)= 6,T(7)=8,
Q₄=(4,8),
Q₅=(5,9),
Q₆=(6,10),
Q₇=(7,11),
T(2)=5,
T(3)=13,
Q₂={(2,5), (5,9)},
Q₃={(3,6), (6,10)},
T(1)=6,
Q₁={(1,2), (2,5), (5,9)}.
Beləliklə, T(1) minimal yolun davamiyyətini, Q₁ həmin yolun topologiyasını göstərir. Qeyd edək ki, bu məsələni yuxarıdan aşağıya yanaşma üsulu ilə həll etsək, mümkün olan bütün yolların hamısını qurub qiymətləndirmək lazım olar, ona görə də əlverişli deyil.
Indi elə məsələyə baxılacaq ki, onun həllində hər iki yanaşmadan istifadə olunur.
Məsələ 2. Masanın üstündə k qədər çöp var; min=a, max=b olmaqla, növbə ilə iki nəfər çöpləri götürürlər. Sonuncunu götürən uduzur. Uduş strategiyasını qurmalı.
Fərz edək ki, k=20, a=1, b=2.
Həlli: Hər bir oyunçu çalışmalıdır ki, sonda masanın üstündə bir ədəd çöp qalsın ki, rəqib bunu götürmək məcburiyyətində qalaraq uduzsun. Qeyd edək ki, sonda iki çöp saxlamaq olmaz, çünki bu halda rəqib çöpün yalnız birini götürərək digər oyunçunu məğlub duruma salar. Deməli, sonda bir çöp saxlamaq lazımdır, bundan əvvəlki addımda 1+(1+2)=4, bundan da əvvəlki addımda 1+2(1+2)=7, və s. sayda çöp saxlamaq lazımdır. Deməli uduşu təmin edən ədədlər ardıcıllığı, yəni uduş strategiyası budur: 1,4,7,10,13,16,19. Bu dəhlizə birinci daxil olan oyunçu sonadək oyunun qaydalarına riayət etsə, sonda qalib gəlir. Beləliklə, k=20 olduqda ilk başlayan oyunçu başlanğıcda bir çöp götürməlidir və hər dəfə rəqib bir çöp götürdükdə iki çöp, rəqib ikisini götürdükdə isə birini götürməlidir.
Oyunun başqa bir variantına baxaq: həmin başlanğıc şərtlər daxilində sonuncunu götürən qalib gəlir. Bu halda uduş strategiyası belədir: 0,3,6,9,12,15,18. Beləliklə, bu halda birinci başlayan iki çöp götürməklə masa üstündə 18 çöpün qalmasına nail olmalıdır.
Bu məsələni ümumiləşdirsək, “sonuncu çöpü götürən məğlub olur” oyunu üçün uduş strategiyası belə olar:
a, a+(a+b), a+2(a+b), a+3(a+b),....
“Sonuncu çöpü götürən qalib gəlir” oyunu üçün uduş strategiyası belə oar:
0, (a+b),2(a+b),3(a+b),....
Göründüyü kimi, baxılan məsələnin həllinin uduş strategiyasını quranda aşağıdan yuxarıya yanaşma üsulundan, bilavasitə oyunun icrasında yuxarıdan aşağıya yanaşma üsulundan istifadə olunmalıdır.
Məsələ 3. A(m,n) düzbucaqlısı verilib, m≥n. Bu düzbucaqlının A(m,1) xanasına hər hansı şahmat fiquru, məsələn, top fiquru qoyulub. Bu fiqur yalnız sağa və yuxarı hərəkət edə bilər. Oyunda iki nəfər iştirak edir, növbə ilə oynayırlar. Hər addımda topu istənilən qədər sağa və ya yuxarı sürüşdürmək olar. Hər kim ştrixlənmiş A(1,n) xanasına tez çatsa, o qalib hesab olunur. Deməli, A(1,n) məqsəd situasiyasıdır. Bundan əvvəlki addımda A(2, n-1) xanasını tutmaq lazımdır. Beləliklə, ştrixlənmiş zonaya kim birinci daxil olsa və oyunun qaydalarına axıra kimi riayət etsə, o qalib gəlir. Bu oyunun uduş strategiyası aşağıdan yuxarıya yanaşma ilə belə qurulur:
A(1,n) , A(2, n-1), A(3, n-2),..., A(k, n-k+1); (1≤k≤n ).

i j	1	2	3	4
1
2
3
4
5