|
Tayanch iboralar: maqsad, agent,reja, vacuum Tatilni rejalashtirish
Ruminiyadagi tatil; Joylashgan joyi Arad. Buharestdan ertaga parvoz qiladi. Maqs adni formulalashtirish:
Buharestda bo’lish
Muammoni formulalashtirish:
Shtatlar: Turli shaharlar Harakatlar: Shaharlar orasida qatnov
Shaharlar ketma-ketligi: Arad, Sibiu, Fagaras, Bucharest Muammoni hal qilish agenti
sensor ar
actuatorlar
G ovamformua ashtinsh
muammoniformu a ashtinsh
shtat а г
Harakat ar
Yechimni topish
8.1-rasm
Misol: Marshrut topish
ROMANIA
UKRAINE
UKRAINE
MOLDOVA
HUNGARY
Maramures
ROMANIA
* Suceava
Southern
Bucovina
^ Iasi
i Orad ea
^ Пасйи
Crlsana
Deva
Banat
Alba
lulla
Targu Ф ^
Mures _ %■
♦ Sighispana Moldavia • Tran sylvan la
Sibiu ■ • Brasov
Moravlta ■
Д v 1Q0 km 0 60 mt
YUGOSLAVIA
Mt Moldcvomu
Fagaras '
Vlnuiitjiius
Carpathian Moumtatns1
Snagw.
»»* Bucharest
Scorn ceetH Craiova *
Muammo yechimi
i Sinaia i о Ploiesti
Wallachla
Ciurgiu i
8.2 -rasm
Danube
Delta
Northern n i i Dobruja "*“=*
лея
Constanta
BULGARIA
7730 Black See Coast
<© Lonely Flare:
Vacuum Dunyosi
8.4-rasm
Neamt
Arad
118
Vaslui
Craiova
8.3-rasm
Eforie
Muammoni hal qilish agenti.
Muammoni hal qilishning 4 ta asosiy bosqichi bor:
Maqsadni formulalashtirish
Qaysi biri kerakli yo’nalish
Qaysi yo’nalish va shtatlar orqali boriladi
Yo’nalishlaming ehtimoliy ketma-ketliklari ichidan Eng optimal yo’nalishni tanlash.
So’nggi qarorni Chiqarish.
function SIMPLE-PROBLEM-SOLYING-AGENT(percept) return an action
static: seq, an action sequence
state, some description of the current world state goal, a goal
problem, a problem formulation
state ^ UPDATE-STATE(state, percept)
if seq is empty then
goal ^ FORMULATE-GOAL(state)
problem ^ FORMULATE-PROBLEM(state,goal) seq ^ SEARCH(problem) action ^ FIRST(seq) seq ^ REST(seq) return action Qilingan taxminlar
Muhit static
Muhit tarifga ega
Kuzatiladigan muhit
Harakatlar deterministic Muammoni formulalashtirish.
Muammo aniqlashtiriladi:
Boshlang’ch nuqta, Arad
Yorislik funksiyasi S(X)= Shtatlar yo’nalishlari tarmoqlari juftliklari
S(Arad)={ ^ Zerind, Zerind>,...} Boshlanuvchi shtat + vorislik funksiyasi = shtatlar fazosi
Maqsadni testlash,
Aniq malumot, x=‘buharestda bo ’lish ’
Nazarda tutiladi, checkmate(x)
Yo’nalishlarning orasidagi masofa
c(x,a,y) bosqich narxi, tahminiy >= 0
A solution is a sequence of actions from initial to goal state. Optimal solution has the lowest path cost.
Shtat yo’nalishlarim tanlash
Real dunyo haddan tashqari murakkab.
Shtatlar fazosidan muammo yechimi uchun abstrakti kerak.
Shtat = Ko ’ chmas mulk maj muasi.
Yo’nalish = real harakatlar kompleks birikmasi.
e.g. Arad ^Zerind mumkin bo'lgan murakkabliklarni ifodalaydi. yo'nalishlar, detours, qolgan to'xtaydi, etc.
Ikki davlat o'rtasidagi yo’lni real dunyodagi aksi bo'lsa ajralmaslikka amal qiladi.
Yechim = real dunyoda yechimning real yo'llari belgilangan. Har bir real muammoga qaraganda mavhum harakat osonroq.
Misol: vacuum dunyosi
8.5-rasm
Shtatlar ??
Boshlang’ch Shtat ??
Harakatlari ??
Maqsad test ??
Yo'l qiymati ??
Shtatlar?? Quruqlikdan tashqari ikki yo’naish bor: 2 x 2 =8 Shtatlar.
Boshlang’ch shtat?? Biror shtat boshlang’ch deb olinadi
Harakatlar?? {Chap, o’ng, to’g’ri}
Maqsad test?? maydonlar toza YOKI yo'qligini tekshirish.
Yo’l qiymati?? maqsadga erishish uchun harakatlar soni.
Misol: 8-puzzle
8.6 -rasm
Shtatlar ??
Boshlang’ch shtat ??
Harakatlari ??
Maqsad test ??
Yo'l qiymati ??
Shtatlar?? Har bir g'isht butun son Manzil
Boshlang’ch shtat?? Har qanday shtat boshlang’ch bo'lishi
mumkin
Harakatlar?? {chap, o’ng, tepa, past}
tekshiring
• Yo’l miqdori?? maqsadga erishish uchun harakatlar soni
Maqsad test?? maqsad konfiguratsiyasiga erishilganligini
8.7-rasm
Shtat fazosining olchami =91/2=181.440
1 9
15-jumboq=.65x10 24-jumboq =.5x1025 Kengligi-birinchi strategiyasi
Ф Pastdagi yoyilmagan belgilarga yoyish Ф Amalga oshirish: boshlanishi FIFO navbati bo’yicha Ф Yangi belgilarni navbat oxirida kiritish
8.1.8-rasm.
Sezuvchan qidiruv
Heuristics ko'p hollarda tezroq echim topadigan muammoni hal qilish strategiyasidir ma'lumotdan ko'ra ko'proq. Biroq, bu kafolatlangan emas. Sezuvchan qidirish mumkin juda ko'p vaqt talab qiladi va hatto hal bo'lmasligi mumkin. Biz odamlar har qanday narsalar uchun evristik jarayonlarni muvaffaqiyatli ishlatamiz. Qachon supermarketda sabzavot sotib olish, masalan, biz turli variantlarni ko'rib chiqamiz narxiga, tashqi ko'rinishiga, narxiga, narxiga, narxiga, ishlab chiqarish manbai va sotuvchiga ishonch, keyin biz eng yaxshi variantni hal qilamiz ichak hissi bilan. Nazariy jihatdan qulupnayni asosiyga berish yaxshi bo'lishi mumkin kimyoviy tahlilni qabul qilishdan oldin, Misol uchun, qulupnay zaharlanishi mumkin. Agar shunday bo'lsa, bu tahlilga arziydi. HEURISTICSEARCH(Start, Goal)
NodeList = [Start]
While True
If NodeList =0 Return(“No solution”)
Node = First(NodeList)
NodeList = Rest(NodeList)
If GoalReached(Node, Goal) Return(“Solution found”, Node)
NodeList = SortIn(Successors(Node),NodeList)
Ammo, biz bunday tahlilni amalga oshirmayapmiz, chunki juda ko'p narsa bor. Bizning intuitiv tanlovimiz muvaffaqiyatli bo'lishini va bizni tezda qo'lga kiritadigan yuqori ehtimoli mazali qulupnay eyishni maqsadimiz. Sezuvchan qarorlar haqiqiy vaqtda qaror qabul qilish kerakligi bilan chambarchas bog'liq resurslar cheklangan. Amalda tezda yaxshi yechim topiladi optimallashtiruvchi, lekin juda qimmat bo'lgan echim. Matematik modellashtirish uchun davlatlar uchun f (s) ni baho berish funktsiyasi ishlatiladi heuristik. Maqsad, ma'lum bir qidirish muammosini hal qilishda ozgina harakatni topishdir minimal umumiy xarajat bilan. Iltimos, unutmang, albatta yechim topishga harakat va ushbu echimning umumiy qiymati. Misol uchun, bu mumkin Google Xaritalar, shahar hokimiyatidan marshrutni topish uchun yarim soniyalik kuchga ega San-Frantsiskodan Yosemit milliy bog'idagi Tuolumne Meadowsga boringlar, lekin bu erdan chiqishingiz mumkin San-Frantsiskodan Tuolumne-ga yo'l olgan Meadows avtoulovi to'rt soat davom etishi mumkin benzin va boshqalar uchun (umumiy xarajat). Keyinchalik, baholashni qo'shib, kengligi birinchi qidiruv algoritmini o'zgartiramiz. Hozirgi vaqtda ochiq tugunlar endi chapdan o'ng tomonga kengaytirilmaydi, balki ularning euuristik reytingiga ko'ra. Ochiq tugunlar to'plamidan, tugun minimal reyting doimo kengaytiriladi. Bunga darhol
erishiladi tugunlarni kengaytirganda va ularni ochiq tugunlar ro'yxatiga ajratish orqali baholash. Keyin ro'yxat daraxtdagi turli chuqurliklardan tugunlarni o'z ichiga olishi mumkin. Chunki davlatlarning evristik baholashi juda muhim, chunki biz izlaymiz davlatlar va ular bilan bog'liq tugunlar o'rtasida hozirdan farq qiladi. Tugun o'z ichiga oladi davlat va qidiruvga tegishli qo'shimcha ma'lumot, masalan, uning chuqurligi qidiruv daraxti va davlatning tarjimai holi. Natijada "Successors" funksiyasi, bu tugunning vorislari (bolalari) ni yaratadigan, darhol bo'lishi kerak bu hal qiluvchi tugunlar uchun ularning har birining komponenti sifatida ularning bahslashish darajalarini hisoblash tugunni tanlang. Umumiy qidiruv algoritmini aniqlab olamiz. Tugun ro'yxati boshlang'ich dugumlerle boshlanadi. Keyin, pastadir, birinchi ro'yxatdagi tugun o'chiriladi va u eritma tugunmi bo'lmagani uchun sinovdan o'tkaziladi. Agar yo'q bo'lsa, u "Successors" funksiyasi va uning vorislari ro'yxatga kiritilgan funksiya bilan kengaytiriladi
Do'stlaringiz bilan baham: |
