DO
IZLASH (X || (a),I+I);
END;
END.
Bu yerda
||
ikki vektorni birlashtirish operatsiyasini bildiradi,ya’ni ixtiyoriy
a
1
,a
2
,...,a
n
b
1
b
2
,...,b
m
lar uchun
(a
1
,a
2
,...,a
n
) || (b
1
b
2
,...,b
m
)=(a
1
,a
2
,...,a
n
,b
1
b
2
,...,b
m
)
va
( ) ||
(a
1
)=(a
1
)
bo’ladi
.
IZLASH( ( ), 1)
—ni chaqirish ham yechimlarni topadi, shuningdek, hamma
qaytishlar mexanizmda ko’rinmas bo’ladi. Quyidagi ko’rinishda tasvirlanadigan
(quriladigan) izlash daraxtinin1g tubidan o’tish atamalarini yozish qaytishli izlash
jarayonini osonlashtiradi. Izlash daraxtining ildizi ( 0 - daraja) boshlang’ich qismiy
yechim bo’ladigan vektorga mos keladi. Ba’zi p - uchlarning o’g’li bo’ladigan k -
darajali ixtiyoriy k
1 uchlar uchun (
a
1
,a
2
,...,a
k-1
) qismiy yechimmos keladi, (
a
1
,a
2
,...,a
k-
1
,a
k
) esa p - uchga mos keladi,
a
k
S
k
. Bunda p - uchlar o’g’illari tartiblanganligi
S
k
ning
a
k
elementlari tartiblanganligiga mos keladi.
Daraxt tubi va kengligini aylanib o’tishlar.
Ko’pgina masalalarda ba’zi daraxtlarni (masalan izlash daraxtini) aylanib
o’tiladi, uning har bir uchiga aniq bir marta tashrif va bunda shu uchga tegishli
ma’lumotlarni ba’zi tizimli qayta ishlashlar sodir bo’ladi. Daraxtning har bir uchiga
16
tashrif oddiy operatsiyalarni bajarish,masalan: daraxt uchlari belgilarini chop etish yoki
murakkab operatsiyalarni bajarish,masalan: ba’zi funksiyalarni hisoblash bilan bog’liq
bo’lishi mumkin.
Agar uchlarga tashrif orqali daraxt strukturasi buzulmasa, daraxt uchlaeini
aylanib o’tishning quyidagi ikki asosiy usuli bir qancha foydali hisoblanadi: tubini
aylanib o’tish va kengligini aylanib o’tish.
Daraxt tubini aylanib o’tishda (xuddi fo’g’ri tartibda o’tish kabi ma’lum)
quyidagi rekursiv protsedura bilanmoslikda daraxt uchlariga tashrif buyuriladi: oldin
daraxtning q - ildiziga tashrif , keyin agar ildiz qaralayotgan daraxtning bargi bo’lmasa,
u holda har bir q - ildizning p - o’g’li tubini aylanib o’tish protsedurasiga murojaat
qilinadi,negaki, hamma shoxlar p - ildizlar bilan xuddi q - ildiz o’g’li p - uch tartibidek
aylanib o’tiladi.
Agar daraxt bo’lab joriy yo’lni saqlash uchun S - stekni qo’llasak, ya’ni daraxt
ildizidan boshlanib, uchida tugaydigan, berilganmomentda tashrif buyuruvchi yo’lni
saqlash uchun S - stekni qo’llasak, daraxt tubini aylanib o’tishning rekursiv bo’lmagan
algoritmini qurish mumkin:
Daraxt ildiziga tashrif va uni S - bo’sh stekka joylashtirish;
WHILE S - stek bo’sh bo’lmaguncha DO
BEGIN
S - stekning tepasida joylashgan uch p bo’lsin;
IF p - uch o’g’li hali kelmagan
THEN Katta o’g’ilni p - uchga keltirish va uni S - stekka joylashtirish;
ELSE BEGIN p - uchni S - stekdan o’chirish;
IF p - uka bo’lsa
THEN Ukani p - uchga keltirish va uni S - stekka joylashtirish;
END;
END[9].
Daraxt kengligini aylanib o’tish, ba’zan gorizontal tartibda o’tuvchi usul ham
deyiladi, daraxt uchlari bo’ylab chapdan-o’ngga, daraxt ildizlari bo’ylab darajama-
17
daraja murojaatni amalga oshiradi.Shunday qilib, uzunligi noaniq bo’lgan ( r - ma’lum
emas), qandaydir (
a
1
,a
2
,...
) vektor ko’rinishidagi biror yechimini topish mumkin.
Chuqurlikni aylanib o’tish algoritmini shunday ta’riflash kerakki, uni
tasvirlangan grafning hammauchlari bo’ylab aylanib o’tishga qo’llash mumkin bo’lsin:
WHILE Hech bo’lmaganda bitta uchga tashrifga ega bo’lguncha DO
BEGIN p - tashrif buyurilmagan uchlarning birinchisi ( minimali) bo’lsin;
p - uchga kelish va uni S - stek tepasiga joylashtirish;
WHILE S - stek bo’sh emas DO
BEGIN S - stek tepasida joylashganuch p bo’lsin;
IF p - uchda kelmagan qo’shiluvchi uchlar bo’lsin;
THEN BEGIN p - ning qo’shilgan uchlari lchida birinchi tashrif buyurmaganuch q -
bo’lsin;
(p,q) reber bo’ylab yurish q - uchga tashrif va uni s - stekka joylashtirish;
END;
ELSE p - uchni S - stekdan uchirish;
END;
END.
Algoritm ishi natijasida grafning bir-biriga o’tgan reberlari bir yoki bir nechta
daraxt uchlariga tashrif bilan tasvirlanadi[9].
Qaytishli izlashni takomillashtirish: dasturda qaytishli izlashning realizatsiyasi
hamma usullarda mumkin bo’lgan yechimlar to’plami sifatida qaraladi.Faqat shunday
konfiguratsiyalar, ya’ni imkoniyatlar sonini ko’paytiradigan komfiguratsiyalar tadqiq
qilinadi. Imkoniyatlar to’plamini qisqartirish uchun shu turdagi analizdan foydalanish
chegarali izlash yoki shoxlarni kesib tashlash deyiladi.
Ikki konfiguratsiyani ekvivalent deb hisoblash mumkin, agar ulardan biri
aylantirish va akslantirish yordamida boshqasiga o’tsa. Aylantirish va akslantirish
yordamida ulardan hamma konfiguratsiyalar to’plami quriladi.
Yana bir takomillashtirish— shoxlarning qo’shilishidir. Uning g’oyasi shundan
iboratki, bir xil ishni ikki marta bajarishni oldini olish, agar ba’zi daraxtning shoxlarini
izlash izomorf bo’lsa, hech bo’lmaganda ulardan birini tadqiq qilishning iloji bo’lsa.
18
Shuni nazarda tutish lozimki,nafaqat dasturlarni qayta ishlashda, balki shu bilan
birga qayta ishlangan dasturni o’chirishda ham har xil takomillashtirishlarni
qo’llashmaqsadga muvofiqdir.
|
