Ч а с т ь I x главный редактор
«Молодой учёный» . № 23 (313) . Июнь 2020 г. Молодой ученый O’zbekiston
жүктеу/скачать 4.33 Mb. Pdf көрінісі
|
| 726
«Молодой учёный» . № 23 (313) . Июнь 2020 г. Молодой ученый O’zbekiston Молодой ученый O’zbekiston Графларда манзилга элтувчи йўлни топиш масаласи ҳозирги кундаги энг муҳим масалалардан бири бўлиб ҳисо- бланади. Бундай қидириш усуллари йўлни кўрсатувчи на- вигаторларда кенг қўлланилиб келмоқда. Сунъий интеллект соҳасида бундай қидириш усулларининг бир қанча турлари мавжуд, масалан, чуқурликга қидириш, энига қидириш, эв- ристик қидириш, А* кидириш ва бошқа усуллар. Биз ушбу мақолада чуқурликга қидириш ва энига қидириш усулла- рини қўллашни кўриб чиқамиз. Чуқурликга қидириш (depth-first search) — бу усулда бутун қидириш жараёни қидириш дарахтининг жорий чўққисидан бошлаб унинг энг чуқур чўқкисига қараб чиқишдан иборат [1]. Яъни қидириш дарахтида биринчи чўққи олинади ва шундан кейин турган чўққига ўтилади. Бу жараён энг охирги чўққигача давом этади. Кейин эса бир қадам орқага қайтиб ёнидаги чўққига ўтилади ва жараён да- вом этилади. Ҳар бир юришда чўққи манзил чўқки экан- лиги текширилиб ва юришлар ёзиб борилади, агар чўққи манзил бўлса қидирув тўхтатилади. Ёзиб борилган манзил- лар эса юриш йўли бўлиб ҳисобланади. Қидириш дарахтида манзилга олиб борувчи йўллар бир нечта бўлиши мумкин, бу усул эса фақат улардан бирини аниқлайди холос, лекин энг яқин йулни аниқлай олмайди, бунинг учун бошқа усул- лардан фойдаланилади. Энди бу усулни Пакман ўйинида қўллаймиз [3]. Берклидаги Калифорния университети то- монидан сунъий интеллектни талабаларга ўргатиш мақса- дида очиқ кодли Пакман лойихаси ишлаб чиқилган. Бу да- стурда ўйин дастурида қидириш алгоритмини дастурини ёзиш ва натижани текшириб имконияти мавжуд. Ўйин да- стур Python дастурлаш тилида ёзилган, дастурни универ- ситетнинг сунъий интеллект курси саҳифасидан юклаб олиш мумкин. Қидиришни амалга ошириш учун бизга да- стурдаги search.py файли керак бўлади. Бу файлда бир не- чта қидириш усулларининг бўш методлар келтирилган. Ма- салан depthFirstSearch () методи бу чуқурликга қидириш усули учун мўлжалланган. Бизнинг вазифамиз шу метод кодини ёзишдан иборат. Ўйин лабиринтида бошланғич нуқта ва манзил белги- ланган бўлади. Натижани олиш учун depthFirstSearch () ме- тоди йўллар кетма-кетлиги кўрсатилган массивни метод на- тижаси сифатида қайтариши лозим. Масалан, ўнга, чапга, ўнга, ўнга, … Бошланғич нуқта координатасини аниқлаш учун getStartState () функциясидан фойдаланилади. Белги- ланган нуқтадан юриш мумкин бўлган координаталарни аниқлаш учун эса getSuccessors () функциясидан фойда- ланилади. Бу функция қайтарадиган қиймат 3 та: коорди- ната, йуналиш, кадамлар сони, масалан, (3,4), West, 1. Бел- гиланган нуқта манзилини текшириш учун isGoalState () функцияси қўлланилади. Қидиришни амалга оширишда маълумотлар структурасидан фойдаланиш мақсадга му- вофиқ. Шу сабабли дастурнинг ўзида стек, навбат струк- туралари амалга оширилган, бу маълумотлар структура- лари util.py файлида келтирилган. Демак, биз чуқурликга кидириш усулини қўллашимизда қуйидагича кетма-кет- ликдан фойдаландик: — учта қисмдан (нуқта координатаси next_node, юриш лозим бўлган йўллар кетма-кетлиги way, юрилган йўллар кетма-кетлиги visited_nodes) иборат стек эъ- лон қилинади, — стекнинг биринчи ячейкасига жорий яъни бош- ланғич нуқта координатаси ёзилади, — стек бўшагунча давом этувчи цикл эълон қилинади, — биринчи ячейкадаги маълумотлар ўчирилиб алоҳида ўзгарувчиларга кўчирилади, — юриш мумкин бўлган йўллар сонигача давом этувчи цикл эълон қилинади, — хар бир юриш мумкин бўлган нуқта текширилиб чиқилади, яъни, агар жорий нуқта олдин юрилма- ган бўлса ва ушбу нуқта манзил нуқта бўлмаса шу нуқта стекга қўшилади ва қидириш давом этади. — агар манзил нуқта аниқланса натижа қайтарилади ва қидириш тўхтатилади. Стекнинг ишлаш хосияти бу охирги бўлиб киритилган маълумот биринчи бўлиб стекдан чиқиб кетади, шу сабабли чуқурликга қидириш усулида стекдан фойдаланиш қулай усул бўлиб ҳисобланади. Масалан, бизда қидириш дарахтида иккита А ва Б юриш мумкин бўлган чўққилар мавжуд бўлсин. А ва Б чўққилари текширилади, агар манзил аниқланмаса, энг охирги киритилган Б чўққиси стекдан чиқарилиб шун- дан кейинги турган чўққилар текширилади ва шу кўринишда қидириш давом эттирилади. Чуқурликга қидириш алгорит- мининг дастурдаги коди 1-расмда келтирилган. 1-расм. жүктеу/скачать 4.33 Mb. Достарыңызбен бөлісу:
|