Masalani echishning ba’zi strategiyalrini qarab chiqamiz. Graflarda hal qiluvchi yo’llarni qurishga yo’naltirilgan bir qator strategiyalar masalani echishda baholash funksiysi(BF)ga asoslanadi. BF grafning tugunlarida aniqlanadi va haqiqiy qiymatlarni qabul qiladi. Ixtiyoriy tugun uchun hosil qilingan BF qiymati ushbu tugundan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini aniqlaydi.
Masalani BFni hisoblash asosida echish strategiysi evristik izlashning bir ko’rinishi hisoblanadi.
BFni hisoblash asosida masalani echishning boshqa strategiyalariga chuqurligi bo’yichaizlash va kengligi bo’yichaizlash kiradi. Chuqurligi bo’yichaizlashda ixtiyoriy tugunning baholash funksiyasi qiymati ushbu tugundan boshlang’ich tugungacha bo’lgan masofaga to’g’ri proportsional bo’ladi. Kengligi bo’yicha izlashda bu bog’lanish teskari proportsional bo’ladi.
Tugunlarning chuqurligi deganda tugunlarning pog’onalari tartib raqamiga teng bo’lgan son tushuniladi.
Quyida masalani echishning boshqastrategiyalarinikeltiramiz.
Shoxlar va chegaralar usuli. Qidirish jarayonida tugamagan yo’llardan eng qisqasi tanlab olinadi va bir qadamga uzaytiriladi. Hosil qilingan yangi tugamagan yo’llar (mazkur tugunda qancha shox bo’lsa ularning soni ham shuncha bo’ladi) eskilari bilan bir qatorda ko’riladi va yana ulardan eng qisqasi bir qadamga uzaytiriladi. Jarayon birinchi maqsadli tugunga yetguncha takrorlanadi va yechim saqlanadi. So’ngra qolgan tugamagan yo’llardan tugagan yo’lga nisbatan uzunroq yoki unga teng yo’llar olib tashlanadi, qolganlari esa xuddi shunday algoritm bo’yicha ularning uzunligi tugagan yo’lnikidan katta bo’lguncha uzaytiriladi. Natijada yo barcha tugamagan yo’llar olib tashlanadi, yo ular orasidan oldingi olingan yo’ldan qisqaroq bo’lgan yo’l shakllanadi. Oxirgi yo’l etalon hisoblanadi va h.k.
Murning qisqaroq yo’llarni topish algoritmi. Boshlang’ich X0 tugun 0 soni bilan belgilanadi. Algoritm ishlash jarayonining boshlang’ich qadamida Xi tugunning tarmoq tugunlar to’plami X(Xi) olingan bo’lsin. U holda oldin olingan barcha tugunlar undan o’chiriladi, qolganlari esa xi tugunning nishoniga qaraganda bir birlikka oshirilgan nishon bilan belgilanadi va ulardan Xi ga tomon ko’rsatkichlar o’tkaziladi. Keyin hali ko’rsatkichlar manzili sifatida qatnashmaydigan belgilangan tugunlar to’plamida eng kichik nishonli tugun olinadi va u tugun uchun tarmoqlanuvchi tugunlar quriladi. Tugunlarni belgilab chiqish maqsadli tugun hosil qilinguncha takrorlanadi.
Minimal qiymat bilan yo’lni aniqlashning Deykstr algoritmi o’zgaruvchan uzunlikdagi yoyni kiritish hisobiga Mur algoritmining umumlashmasi hisoblanadi.
Doran va Mitchining past baho bilan qidirish algoritmi. Qidirish bahosi optimal yechimning bahosiga nisbatan katta bo’lgan holda ishlatiladi. Bu holda Mur va Deykstr algoritmlaridagiday boshidan eng kam uzoqlikda joylashgan tugunni tanlash o’rniga maqsadgacha bo’lgan masofaning evristik bahosi eng kam bo’lgan tugun tanlanadi. Yaxshi baholashda yechimni tez hosil qilish mumkin, ammo yo’lning minimalligiga kafolat berilmaydi.
Xart,NilsonvaRafaelalgoritmi.Algoritmda ikkala kriteriya birlashtirilgan: g(x) tugungacha bo’lgan yo’l narxi (bahosi) va h(x) tugundan additiv baholanadigan f{x}=g(x)-h(x) funksiyagacha bo’lgan yo’l narxi hisoblanadi. h(x)shartda (bu yerda hp(x) maqsadgacha bo’lgan haqiqiy masofa) algoritm optimal yo’lni topishga kafolat beradi.
Grafda yo’llarni qidirish algoritmlari qidirish yo’nalishi bilan ham farq qiladi. To’g’ri, teskari va ikki tomonga yo’nalgan qidirish usullari mavjud. To’g’ri izlash boshlang’ich holatdan ketadi va maqsad holat oshkormas holda berilganda qo’llaniladi. Teskari qidirish maqsadli holatdan ketadi va boshlang’ich holat oshkor berilmagan, maqsadli holat oshkor berilgan holda qo’llaniladi. Ikki tomonga yo’nalgan qidirish ikkita muammoning qoniqarli yechimini talab qiladi: qidirish yo’nalishining almashishi va «uchrashuv nuqta»sini optimallashtirish. Birinchi muammoni yechish kriteriyalardan biri qidirish «kengligi»ni ikkala yo’nalishda taqqoslashdan iborat. Qidirishni toraytiradigan yo’nalish tanlanadi. Ikkinchi muammoning yuzaga kelishiga sabab to’g’ri va teskari yo’llar ajralib ketishi mumkin va qidirish qancha tor bo’lsa uning ehtimoli ko’proq bo’ladi.
Cheng va Sleyg algoritmi. Ixtiyoriy VA/YOKI grafni har bir YOKI shoxi faqat oxirida VA tugunga ega maxsus YOKI grafga aylantirishga asoslangan. Ixtiyoriy VA/YOKI grafni muloxazalar mantiqining ixtiyoriy formulasiga aylantirish va keyin bu formulani diz’yunktiv normal shaklga keltirishdan foydalanib aylantirish amalga oshiriladi. Bunday aylantirish keyinchalik Xart, Nilson va Rafael algoritmlaridan foydalanishga imkon beradi.
Kalit operatorlar usuli. masala berilgan bo’lsin va f operator albatta bu masalaning yechimiga kirishi ma’lum bo’lsin. Bunday operator kalit operator deb ataladi. f ni qo’llash uchun S holat kerak bo’lsin, uni qo’llash natijasi esa I(c) bo’lsin. U holda VA tugun uchta tarmoq tugunlarni keltirib chiqaradi: , va
. Ulardan o’rtadagisi elementar masala hisoblanadi. va masalalar uchun ham kalit operatorlar tanlanadi va ko’rsatilgan reduksiyalash prosedurasi mumkin bo’lgunga qadar takrorlanadi. Natijada boshlang’ich masala har biri HFda rejalashtirish usuli bilan yechiladigan masala ostilarining tartiblangan majmuiga ajratiladi. Kalit operatorlarni tanlashda alternativlar bo’lishi mumkin, shuning uchuun umumiy holda VA/YoKI graf sodir bo’ladi. Ko’pgina masalalarda kalit operatorni ajratishga erishilmaydi, faqatgina uni o’z ichiga oladigan to’plamni ko’rsatishga erishiladi. Bu holda masala uchun A va V ning farqi hisoblanadi. Oxirgisi kalit operator bo’ladi.
Umumiy masala yechuvchi(UME)ni rejalashtirish usuli. UMEni rejalashtirish eng mashxur model sifatida paydo bo’lgan. U integral hisob, mantiqiy xulosa, grammatik tahlil va shu kabi boshqa masalalarni yechish tuchun ishlatilgan.
UME qidirishning ikkita asosiy prinsiplarini birlashtiradi: maqsadlarni va vositalarni tahlil qilish va masalani rekursiv yechish. Qidirishning har bir siklida UME uchta turdagi standart masalalarni qat’iy ketma-ketlikda yechadi: A obyektni B obyektga almashtirish, A va B orasidagi D farqni kamaytirish, f operatorni A obyektga qo’llaydi.
Mantiqiy xulosa asosida rejalashtirish. Bunday rejalashtirish holatlarni qandaydir mantiqiy hisobning to’g’ri qurilgan formulalari (TQF) ko’rinishida tavsiflashni; operatorlarni yoki TQF ko’rinishda yoki bir TQFni boshqasiga o’girish qoidalari ko’rinishida tavsiflashni taqozo etadi. Operatorlarni TQF ko’rinishida tasvirlash rejalashtirishning deduktiv usullarini yaratishga imkon beradi, operatorlarni o’girish qoidalari ko’rinishida tasvirlash esa deduktiv xulosa elementlari bilan rejalashtirish usullarini yaratishga imkon beradi.
Chuqurligi bo’yicha izlash strategiyasini faqat tugunlar N = {n1, n2, …, nr} ro’yxati va yoylar L = {l1, l2, …, ls} ro’yxatidan iborat HFberilganda qo’llash maqsadga muvofiq. Bu erda lk= (nik, njk) qirralar bo’lib, niktugundan njktugunga yo’naltirilgan bo’ladi.
