Qidiruv orqali masalalarni yechish. Amaliy

Qidiruv orqali masalalarni yechish. Amaliy

• Mashg’ulotning maqsadi va mazmuni.
• Qidiruv algoritmlarini Piton dasturlash tilida dasturlash va Pakman loyihasining birinchi masalasida qo’llash.
• Nazariy qism
• Pakman loyihasining birinchi loyihasi masalasi qidirish algoritmlarini realizasiya qilishga mo’ljallangan. Pakman harakat qiladigan labirintlarning asosiy uch turi mavjud:
• tinyMaze (2.10-rasm);
• mediumMaze (2.9- rasm);
• bigMaze (2.11- rasm).
• Shart bo’yicha realizasiya qilingan algoritmlar shu uchta labirintda ishlashi talab qilinadi. Bundan tashqari har bir funksiyaning chiquvchi qiymati bu ketma-ketlikda bo’lishi lozim. Ya’ni chiquvchi qiymatda labirintdagi harakatlar ketma-ketligi ko’rsatiladi. Masalan, return [s,s,w,s]. Bunda funksiyaning chiquvchi qyimati sifatida 4 ta qadam belgilangan. Ya’ni janub, janub, g’arb va janubga harakatlanish ko’rsatilgan. Aynan shu ko’rinishda barcha qidiruv funksiyalari echimni chiqaradi.
• Masalalarni echishda loyihadagi standart funksiyalardan foydalanish maqsadga muvofiq. Ular:
• problem.getStartState() – boshlang’ich xolatni aniqlaydi,
• util.Stack – stek,
• util.Queue – navbat,
• util.PriorityQueue – prioritetli navbat,
• problem.isGoalState() – joriy uzelni maqsad uzelligini tekshiradi,
• problem.getSuccessors() – joriy uzelning voris uzellarini aniqlaydi,
• Realizasiya qilingan funksiyalarni chaqirish uchun fn={bfs, dfs, astar} foydalaniladi.
• 
• Bildunterschrift: 2.9 – rasm. mediumMaze labirinti.

Folie 2

• 
• 
• Bildunterschrift: 2.10 – rasm. tinyMaze labirinti.
• Bildunterschrift: 2.11 – rasm. bigMaze labirinti.

1-masala

• 1-masala. Bu masalada chuqurlik bo’yicha qidirish (DFS) algoritmini to’liq realizasiya qilish talab qilinadi. Buning uchun search.py faylida depthFirstSearch() funksiyasini yozish talab qilinadi. Funksiya yozib bo’lingandan so’ng tegishli buyruqlar orqali funksiya barcha labirintlarda tekshirib ko’riladi. Uchta labirintda qidiruvni amalga oshirish uchun uch xil buyruq yoziladi. Agar funksiya to’g’ri yozilgan bo’lsa buyruq o’rinlanganda pakman o’z harakatini boshlaydi va nuqtda etib boradi. Chuqurlikga qidirish algoritmida stekdan foydalangan maqsadga muvofiq.
• DFS algoritmi uchta labirintda realizasiya qilingandan so’ng quyidagicha natijalarni olish mumkin.
• 

2-masala

• 2-masala. Bu masala birinchi masalaga o’xshash bo’lib, bunda chuqurlikga qidirish algorimi o’rniga eniga qidirish algoritmini (BFS) realizasiya qilish talab qilinadi. Bu masalada ham yozilgan funksiya uchta labirintda ham natija ko’rsatishi lozim. Algoritm breadthFirstSearch() funksiyasida realizasiya qilinadi. BFS algoritmini realizasiya qilishda navbat ma’lumotlar tuzilmasidan foydalanish lozim. BFS funksiyasi quyidagicha natijalarni ko’rsatishi mumkin.
• 

3-masala

• 3-masala. Bu masalada A* qidirish algoritmini dasturlash lozim. Buning uchun algoritm aStarSearch() funksiyasida yoziladi. Bu algoritm nuqtaga eng yaqin yo’l bilan etib borishi lozim. A* algoritmini realizasiya qilishda prioritetli navbatdan foydalanish kerak. A* algoritmining ko’rsatgan natijalari quyida ko’rsatilgan.
• 

Topshiriqlar

• Amaliy mashg’ulotga tayyorgarlik qo’rilayotganda [1-3] adabiyotlardan foydalanish.
• Amaliy mashg’ulotni nazariy qismini o’rganib chiqish.
• Pakman loyihasini o’rganib chiqish.
• Eniga qidirish algoritmini depthFirstSearch() funksiyasida realizasiya qilish.
• Chuqurlikga qidirish algoritmini breadthFirstSearch() funksiyasida realizasiya qilish.
• A* algoritmini aStarSearch() funksiyasida realizasiya qilish.
• Uchta algoritmning ko’rsatgan natijalarini solishtiring.

Adabiyotlar

• Iskusstvenniy intellekt: Sovremennie podxodi – A Rassel i Norvig. – iz. Pirson Prentice Hall – 2009 – 1132p.
• Vvedenie v Python – Guido Van Rossum, Fred L Dreyk izd. Network theory – 2003
• Iskusstvenniy intellekt. Osnovi vichislitelnix agentov – David Pul, Alan Makvorf izd. Cambridge University Press – 2010 – 682 str.
• Veroyatnostnie graficheskie modeli: Prinsipi i texniki – Dafni Koller, Nir Ffiidman izd. MIT Press – 2009 – 1231p.
• Usilennoe obuchenie: Vvedenie – Richard S Satton i Andryu G. Barto izd. MIT Press – 1998.
• Mashinnoe obuchenie, neyronnaya i statisticheskaya klassifikasiya D. Michi, D.J. Spigelxalter, S.S. Teylor 1994g. 290 str

Demonstation

• PACMAN code Python algorithm A*, DFS, BFS, UCC (Einbetten)