+6-маъруза

А* algoritmi



Bu algoritm HFko’rinishida berilgan tugunlar to’plamida evristik axborotlar baholi funksiya shaklida ifodalanganda evristik izlashda qo’llaniladi. Aytaylik, echiladigan masalaning HFni ifodalovchi grafda N = {n₁, n₂, …, n_r} –tugunlar to’plami, L = {l₁, l₂, …, l_s} – yoylar to’plami berilgan bo’lsin. Ushbu grafdagi

ixtiyoriy
L  (n_i , n _j ) L
yoy uchun ushbu yoyning bahosini ifodalovchi c(n_i, n_j)

son aniqlangan bo’lsin.Dgar bir nechta maqsadli tugunlar mavjud bo’lsa, u holda boshlang’ich tugunni n₀, maqsadli tugunni esa t yoki t_i bilan belgilaymiz.
Baholash funksiyasi f(ּ) ning qiymatini shunday aniqlaymizki, uning n tugunlardagi qiymati f(n) ikkita qiymatlar yig’indisi bahosidan iborat bo’ladi:

1. 
   boshlang’ich n₀ tugunlardan n tugungacha bo’lgan yo’lning minimal bahosi;
   
2. 
   n tugunlardan qaysidir maqsadli t yoki t_i tugungacha bo’lgan yo’lning minimal bahosi;
   

Agar birinchi bahoni g*(n) va ikkinchi bahoni h*(n) bilan belgilasak, u holda
f(n) baholsh funksiyasi f*(n)=g*(n) + h*(n).
g*(n) va h*(n) fynksiyalarni c(n_i, n_j) lar yordamida quyidagicha aniqlash mumkin:
g^*(n)  min _c(n , n )

l_ ⁿ
i_ j_
n

0
ⁿ⁰ l_ l_ _n

h^* (n)  min min
_ c(n , n )

n₀
^l ^{l n}
l_ l_ ⁿ
i_ j_

n₀

_l


Bu erda formuladagi g*(n) uchun minimum boshlang’ich n₀ tugundan n
n


tugungacha bo’lgan barcha ⁿ₀ yo’llar bo’yicha hisoblanadi. Formuladagi h*(n)
uchun tashqi minimum barcha maqsadli t_i tugunlar bo’yicha, ichki minimum esa boshlang’ich n tugundan tugallanadigan maqsadli t_i tugungacha bo’lgan barcha

_l ^ti
 ⁿ

^ n yo’llar bo’yicha hisoblanadi.
^l m
belgilash, boshlang’ich m tugundan n

tugallanadigan ixtiyoriy yo’l uchun foydalaniladi.
Umumiy holda baholash funksiyasini f (n) = g(n) + h(n),
aniqlash mumkin, bu erda g(n) funksiy - g*(n) funksiyalarning qandaydir bahosi (yaqinlashish), h(n) funksiy esa - h*(n) funksiyalarning qandaydir bahosi (yaqinlashish). g(n) funksiyning bahosi sifatida n₀ tugunlardan n tugungacha

bo’lgan
 ⁿ



l
n₀
yo’llardagi yoylar bahosining yig’imdisi, ya’ni

g(n) 

l l ⁿ
c(n , n ).

i

j
 

^{ } n₀

Barcha maqsadli bo’lmagan tugunlar uchun qanoatlantiruvchi baholash funksiyasi f (n) = g(n) + h(n), А* algotitmi deb ataladi.
h(n)
 h * (n)
shatni

Barcha maqsadli bo’lmagan tugunlar uchun
h(n)
 h * (n)
shat qatnashmasa

baholash funksiyasi f (n) = g(n) + h(n), А algotitmi deb ataladi.
А va А* algoritmlarida g(n) funksiy g*(n) funksiyalarning qandaydir bahosi hisoblanadi. Ikkala algoritmda ham tugunlarni izlashni davom ettirish uchun alternativ tugunlar orasidan f (n) funksiyaning eng kichchik qiymatiga mos keladigan tugun tanlanadi.
Misol. Aitaylik izlashning 1-qadamida ܵ_଴ tugun ochilgan bo’lsin va undan yo’lning baholash qiymatlari ݃ො⁽ܸ_ଵ⁾ = 3 ܽݒ ݃ො⁽ܸ_ଶ⁾ = 7 ega bo’lgan ܸ_ଵ va ܸ_ଶ tugunlar chiqqan bo'lsin. 2-qadamda ܸ_ଵ tugun ochiladi va undan ܸ_ଷ va yana
ܸ_ଶ tugun chiqadi, bunda ܸ_ଵ tugundan ܸ_ଶ tugunga olib boruvchi yolning baholash funksiyasi qiymati qiymatlari ݃ො⁽ܸ_ଵ⁾ = 3 . Ko’rinib turibdiki, ܵ_଴ tugundan ܸ_ଶ tugungacha bo;lgam qisqa yo’lning bahosi ݃ො⁽ܸ_ଶ⁾ = 6 (6.8-rasm).



3
Ta’kidlash joizki, ݃ො⁽ܸ⁾ = 7 ≥ ݃⁽ܸ⁾ = 6.
Misol. Aytaylik, A, B, S, D, E, F zavodlar va ular orasidagi yo’l masofalari berilgan bo’lsin (6.9-rasm). Biz A zavoddan F zavodga kelishimiz kerak. Zavodlar orasidagi masofa ikki yoqlama, ya’ni xarakat ikki tomonga ham yo’naltirilgan bo’lishi mumkin.

Bizga tugunlar orasidagi masofalar berilganligi uchun ular orasidagi yo’lni izlash uchun BFdan foydalanamiz. A zavodga eng yaqin zavod- B (10км), keyin –

S(29), D(47), E(71), F(16). Yo’lning umumiy uzunligi - 173 км bo’lib, u optimal 95
км (A-S-E-F) yo’ldan ancha farq qiladi.
Faraz qilaylik, bizga har bir zavoddan F gacha bo’lgan masofalar ma’lum bo’lsin (6.10-rasm). Bu ma’lumotlardan navbatdagi punktni tanlashda foydalanish mumkin. Demak, Adan boradigan punktlarga B (93км), S (64) va D (83) kiradi. Har bir qadamda maqsadli punktga maksimal yaqinlashish maqsadida, biz birinchi qadamda - S, ikkinchi qadamda -E, keyin–Fni tanlaymiz. Umumiy yo’lning uzunligi optmal qiymatga teng bo’ladi.


Izlashning ushbu ko’rinishi xasisli (жадным) izlash deb ataladi. Bunda har bir yangi tugun baholash funksiyasi f(n) asosida tanlanadi. Biz aniq baholashga ega bo’lmaganligimiz sababli evristik funksiya h(n) yoki evristikadan foydalanamiz. Qaralayotgan masalada evristik funksiya h(n) sifatida to’g’ri chiziq bo’yicha maqsadli punktgacha bo’lgan masofa olinadi.

Optimal marshrut minimal yo’llardan iborat bo’lgani uchun, ulardan izlashning oxirida natijalarni baholash uchun emas, balki izlashning har bir qadamida foydalanish kerak. Biz to’liq ma’lumotlarga ega bo’lmasakda, bizda bosib o’tilgan yo’l haqidagi aniq axborot va evristik funksiya mavjud. Ulardan foydalanib, har bir etapda yo’lning umumiy uzunligini baholash mumkin. Echimlar bahosini baholshlar yig’indisini minimallashtirish usuli А* algoritm deb ataladi.

Baholash funksiyasi f(n) har bir qadamda f(n) = g(n) + h(n),
hisaoblanadi, bu erda g(n)-n-tugunda erishiladigan bahosi, h(n)- n-tugunda evristik funksiyaning maqsadga erishiladigan bahosi.
Baholash funksiyasini 6.10-rasmda keltirilgan zavodlarga borish yo’lining oxirgi varianti uchun qaraymiz. Adan chiqadigan punktlarni qaraydigan bo’lsak, u holda baholash funksiyasi quyidagi qiymatlarga ega bo’ladi (6.12-rasm).

6.12-rasm.
Ko’rinib turibdiki, S minimal BFga ega. Shuning uchun navbatdagi punkt sifatida S punkti tanlanadi.
Ikkinchi qadamda biz uchib o’tilgan 31 км. yo’lga ega bo’lamiz. Shuning uchun Sdan navbatdagi punktlargacha baholash funksiyasi qiymatlari 6.13-rasmdagidek bo’ladi.

6.13-rasm.
Navbatdagi marshrut punk ti sifatida E tanlanadi (6.14-rasm)

6.14-rasm.

Edan faqat Dgacha yo’l bor, lekin uning baholash funksiyasining qiymati A-D marshruti baholash funksiyasining qiymatiga nisbatan katta. Bundan kelib chiqadiki, bu marshrut (A-S-E -D - …) optimal echimni bermaydi. Shuning uchun S punktining o’rniga boshqa zavodni tanlash kerak.
Baholash funksiyasi qiymatIning o’sishini e’tiborga olsak, u holda S punktidan keyin B tanlanadi. B tanlanadigan bo’lsa baholash funksiyalri bo’yicha punktlar 6.15- rasmdagidek joylashadi:

6.15-rasm.
Bu erda D и S punktlari uchun ham olingan baholash fuksilarining qiymatlari oldingi marshrutlarda olingan baholash fuksilarining qiymatlaridan yuqori bo’layapti. Shuning uchun marshrutni Ddan boshlash kerak.
Ddan to’g’ri Fga boriladi. Maqsadli echimga erishildi va u optimal echim hisoblanadi.
Misol. S₀ boshlang’ich holatdan S_t oxirgi holatga o’tuvchi ≪Sakkiz≫ o’yinini qaraymiz (6.16-rasm). Bu o’yinda har bir yurish harakati bo’sh katakga, ya’ni mos matritsada o (nol) raqami turgan katakga amalga oshiriladi.

6.16-rasm.

Bu o’yinning maqsadi S₀ boshlang’ich holatdan S_t oxirgi holatga o’tishni tamonlovchi o raqami turgan katakning yurish harakatining qisqa ketma-ketligini izlshdan iborat. S yordamida bir nechta yurish harakatidan keyin hosi bo;lgan joriy holatni belgilaymiz.
Baholash funksiyasini f (S) = g(S) + h(S) aniqlaymiz. Bunda g(S) funksiyga-S₀ boshlang’ich holatdan S_t oxirgi holatga olib keluvchi haqiqiy yurish harakatlari sonini, h(S) evristik funksiyaga esa - S_t maqsadli holatga nisbatan S holatda o’zining joyida joylshmagan fishka(raqam)lar sonini mos qo’yamiz. Masala sharti va h(S) evristik funksiyaning aniqlanishidan barcha maqsali bo;lmagan tugunlar

uchun
h(S)  h *(S)
tengsizlik kelib chiqadi. А* algoritmga asosan maqsadli

echimni izlash daraxti 6.17 –rasmda keltirilgan.

6.17-rasm.
Ushbu rasmda har bir yurish harakati holatining o’ng pastki qismidagi kvadrat qavsda g(S) va h(S) funksiyalarning mos qiymatlari keltirilgan. Optimal hal qiluvchi yo’l qalin chiziq bilan ajratilgan.
Ushbu holda S₀ boshlang’ich holatdan S_t maqsadli holatni olish uchun o (nol) raqamli bo’sh katakchani eng kami bilan 5 marta yurish harakati amalga oshiriladi.