O‘zbekiston respublikasi axborot texn ologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al -xorazmiy nomidagi toshkent axborot texn ologiyalari universiteti “Axborot texnologiyalari” kafedrasi H

Hart, Nilson va Rafael algoritmi. Algoritmda ikkala kriteriya birlashtirilgan: g(x) uchgaCha bo’lgan yo’l narxi (bahosi) va h(x) uchdan additiv baholanadigan f{x}=g(x)-h(x) funktsiyagaCha bo’lgan yo’l narxi. h(x)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’ch holatdan ketadi va maqsad holat oshkormas holda berilganda qo’llaniladi. Teskari qidirish maqsadli holatdan ketadi va boshlang’ch 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 c 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.
Masalani reduktsiya usulida yechish.
98
Bu usul yaxshi natijalarga olib keladi, chunki ko’pincha masalani yechish c ierarxik strukturaga ega bo’ladi. Ammo asosiy masala va uning barcha qism masalalari bir xil usul bilan yechilishini talab etish shart emas. Reduktsiya masalaning global aspektlarini tasvirlash uchun foydali, maxsus masalalarni yechish cda esa holatlar bo’yicha rejalashtirish usuli maqsadga muvofiq. Holatlar bo’yicha rejalashtirish usulini reduktsiyalar yordamida rejalashtirish usulining xususiy holi deb qarash mumkin, chunki holatlar fazosida operatorning har bir qo’llanilishi boshlang’ch masalani ulardan hech bo’lmaganda bittasi elementar bo’ladigan ikkita soddaroq masalaga keltirishni bildiradi. Umumiy holda boshlang’ch masalani reduktsiyasi ulardan hech bo’lmaganda bittasi elementar masala bo’ladigan ikkita qism masalani shakllantirishga olib kelinmaydi.
Masalalar fazosida rejalashtirishni izlash boshlang’ch masalani ketma - ket osonroq masalalarga keltirishdan iborat. Bu jarayon elementar masalalar hosil bo’lguncha davom ettiriladi. Bunday masalalarning qisman tartiblangan majmuasi boshlang’ch masalaning yechimini tashkil etadi. Masalani alternativ qism masalalar to’plamiga ajratishni VA/YOKI graf ko’rinishida tasvirlash oson. Bunday grafda oxirgi uchdan tashqari barcha uchlar yo kon’yunktiv bog’langan (VA uchlar) yo diz’yunktiv bog’langan (YOKI uchlar) tarmoqlanuvchi uchlarga ega bo’ladi. Xususiy holda VA uchlar bo’lmaganda holatlar fazosi grafi sodir bo’ladi. Oxirgi uchlar YOKI yakunlovchi (ularga elementar masalalar mos keladi) YOKI tupikli bo’ladi. Boshlang’ch uch (VA/YOKI grafning ildizi) boshlang’ch masalani tasvirlaydi. VA/YOKI grafda qidirishning maqsadi boshlang’ch uchning yechilishini ko’rasatish. Yechiladigan uchlar barcha tarmoqlanuvchi uchlari yechiladigan yakunlovchi uchlar va hech bo’lmaganda bitta tarmoq uchi yechiladigan yoki uchlar hisoblanadi. Yechiladigan graf yechib bo’ladigan uchlardan tashkil topgan va boshlang’ch masalaning yechilish usulini ko’rsatadi. Tupikli uchlarning bo’lishi yechilmaydigan uchlarga olib keladi. Tupikli uchlar, hech bo’lmaganda bitta tarmoq uchi yechilmaydigan VA uchlar, har bir tarmoq uchi yechilmaydigan YOKI uchlar yechib bo’lmaydigan hisoblanadi.