|
b_1
n = Ef=0 =
b ni beradi? omil ective og'ir uchun teoremasi 6,1 keng konstantasi bilan n qidiruv daraxtlar omili, deyarli barcha tugunlari so'nggi darajada bo'ladi.
Isbot: (Mashq ??). Misol: B shahardan A shaharga eng qisqa yo'l iqtisodiy funktsiyasi bilan janubiy Germaniya chizmasi.
Davlat: sayyohi joriy holati bo'lib, bir shahar. Davlat bo’ylab, : A va n o'zboshimchalik shahar. Davlat maqsadi : A va n o'zboshimchalik shahar. Actions: qo'shni shaharga joriy shahardan Travel. Ahamiyati funktsiyasi: shaharlar o'rtasidagi masofa. Davlat maydoni: Barcha shaharlar, grafik, ya'ni tugunlari.
U bir yechim bor, agar bo'lsa ham tanituvchi 6,3 A qidiruv algoritmi, optimal deb ataladi har doim?
NDS eng kam harajat bilan hal qiladi. 8 jumboq muammo hisoblanadi deterministik: har bir harakat noyob vorisi davlatga bir davlatdan olib keladi. kuzatiladigan: agent har doim u bilan bo'lgan davlatni biladi. Deb atalmish O foydalanish algoritmlarni, optimal echimlar topish mumkin.
Aks holda: Taqvim ta'lim
Eristik qidiruv
Evristika ko'p hollarda bir yechim topish muammo hal qilish strategiyasi tezroq qidiruv. Hech qanday kafolat yo'q! kundalik hayotda, evristik usullari muhim ahamiyatga ega. Cheklangan resurslardan ostida haqiyqi vaqt-qarorlari tez topiladi A yaxshi yechim optimal bo'lgani afzal, lekin olmoq uchun juda qimmat. davlatlar uchun evristik baholash funksiyasi f (bo'ladi)
Node = davlat + evristik baholash
HeuristicSearch(Start, Goal)
NodeList = [Start]
While True
If NodeList= ; Return(\No solution")
Node = First(NodeList)
NodeList = Rest(NodeList)
If Goal Reached(Node,Goal) Return(\Solution found", Node)
NodeList = SortIn(Successors(Node),NodeList)
Depth- RST va birinchi qidirish breadth- funktsiyasi maxsus holatlari
Evristik qidiruv. (Mashq ??)
8-jumboqli muammoni deterministik bo'lib, demak, har bir harakatdan kelib chiqadi noyob voris davlatga davlat. Bundan tashqari, kuzatilishi mumkin, ya'ni agent har qanday holatni har doim ham biladi har doim berilmaydi. "Munihdan Ulmga olib ketish" aktsiyasi mayda Misol uchun, voqea sodir bo'lganligi sababli, "Munich" ning vorisi bo'lgan davlatga olib keladi. U ham bo'lishi mumkin sayyoh yo'qolganligi sababli u qaerda ekanligini bilmaydi. Biz istaymiz birinchi navbatda bu kabi asoratlarga e'tibor bermaylik. Shuning uchun bu bobda biz faqatgina deterministik va kuzatish mumkin bo'lgan muammolarga qarash. Deterministik va kuzatish mumkin bo'lgan 8 jumboq kabi muammolar harakatlar qiladi rejalashtirish juda oddiy, chunki mavhum modelga ega bo'lishi mumkin muammoni echish uchun amaliyotni bajarmasdan harakat tartibini toping haqiqiy dunyodagi harakatlar. 8 jumboq bo'lsa, aslida bunga ehtiyoj qolmaydi hal qilish uchun haqiqiy dunyodagi kvadratlarni harakatlantirish. Biz maqbul echimlar topamiz oflayn algoritmlar bilan. Ulardan biri, masalan, futbol o'ynashi kerak bo'lgan robotlar yaratish. Bu erda hech qachon bo'lmaydi harakatlarning mutlaq mavhum modeli bo'lsin. Misol uchun, to'pni urgan robot muayyan yo'nalish to'pning harakatlanadigan joyida aniqlik bilan bashorat qila olmaydi, chunki, boshqa narsalar bilan bir qatorda, raqibning qo'lga olishi yoki urinishini bilmaydi to'p. Bu erda onlayn algoritmlar kerak bo'ladi, ular sensorga asoslangan qaror qabul qiladi Har qanday vaziyatda signallar. Sekshtda tavsiflangan takomillashtirishni o'rganish. 10, ishlaydi ushbu qarorlarni tajribaga asoslangan holda optimallashtirishga qaratilgan.
Opponentlar bilan o'yinlar
Shaxmat, shashka, Othello va Go kabi ikkita o'yinchi uchun o'yinlar deterministikdir chunki har bir harakat (bir harakat) bir xil ota-onadan bir xil bola holatiga olib keladi davlat. Bunga javoban, tavern non- deterministik emas, chunki bolaning holati bog'liq zar zarrachalari natijasida. Bu o'yinlar har bir o'yinchining kuzatilishi mumkin har doim to'liq o'yin holatini biladi. Poker kabi ko'p karta o'yinlari, masalan, faqatgina qisman kuzatilishi mumkin, chunki futbolchi boshqa narsani bilmaydi futbolchilarning kartalari yoki ular haqida qisman ma'lumot bor.
Ushbu bobda hozirgi kunga qadar muhokama qilingan muammolar aniq va sezgir edi. Quyida biz ham xuddi deterministik va kuzatiladigan o'yinlar ko'rib chiqamiz. Bundan tashqari, biz o'zimizni nolga teng o'yinlar bilan cheklaymiz. Bu o'yinlar. Har bir daromad bitta o'yinchi raqib uchun bir xil qiymatni yo'qotishni anglatadi. Ushbu daromad va yo'qotish summasi har doim nolga teng. Bu shaxmat o'yinlari, dama, Othello va GO yuqorida qayd etilgan.
Minimax qidiruvi
Har bir futbolchining maqsadi g'alaba bilan yakunlangan optimal harakatlar qilishdir. Amalda qidiruv daraxtini qurish va uni butunlay qidirish (masalan 8-jumboq) g'alabaga olib keladigan bir qator harakatlar uchun. Biroq, bor quyidagi xususiyatlarga e'tibor berish kerak:
Shaxmatda samarali tarmoqlashtiruvchi omil 30-35 orasida. Odatda o'yinda Har bir futbolchi uchun 50 ta harakat, qidiruv daraxti 30100 dan ortiq ~ 10148 bargli tugunlarga ega. Shunday qilib, qidiruv daraxtini to'liq o'rganish uchun hech qanday imkoniyat yo'q. Bundan tashqari, shaxmat ham bor odatda vaqt chegarasi bilan o'ynaydi. Ushbu real vaqt talabi tufayli, qidiruv daraxtdagi tegishli chuqurlik bilan cheklanishi kerak, masalan, sakkiz yarim qadam.
Ushbu chuqurlikdagi cheklangan daraxtning bargli tugunlari orasida odatda echim yo'q tugunlarni (ya'ni o'yinni tugatadigan tugunlarni) egulikni baholashni o'z ichiga oladi. B lavozimlari uchun B funktsiyasi ishlatiladi. Dasturning o'ynash darajasi kuchli. Bu baholash funktsiyasi sifatiga bog'liq. Shuning uchun biz yana davolanamiz
Quyidagi o'yinda Maksni optimallashtirishni istagan o'yinchini chaqiramiz,
va uning raqibi Min. Raqibning (Minning) harakatlari oldindan ma'lum emas, shuning uchun haqiqiy qidiruv daraxti ham yo'q. Bu muammoni chiroyli hal qilish mumkin raqib har doim eng yaxshi harakatni amalga oshirishi mumkinligini taxmin qilmoqda. Juda yuqori b-pozitsiyasi uchun B (lar) ni baholash uchun, Maks va Maks. Eng yomoni raqib Min uchun. Max uning bahosini maksimal darajada oshirishga harakat qilmoqda harakatlansa, Min minimal darajada baholanadi.
To'rt yarim bosqichli va barglarning bahosi bo'lgan qidiruv daraxti - keltirilgan. Ichki tugunni baholash maksimal ravishda o'z-o'zidan chiqariladi
yoki tugunning darajasiga qarab, uning kichik tugmachalari.
Takrorlash uchun savollar:
O’yinlar nazariyasining mohiyati.
Qanday o’yin turlarini bilasiz.
O’yinlarni strategiyasi nima.
- ma’ruza BAYES TO’RLAR
Do'stlaringiz bilan baham: |
