Қидирув. Қидирув алгоритмлари

Қидирув. Қидирув алгоритмлари.

АТ кадедраси

Атаджанова М.П.

Режа:

• Қидирувда руҳсат этиш
• Масалани формал аниқлаш
• Муаммони ечимини аниқлаш
• Муҳит ҳолати графлари
• Қидирув алгоритмларини баҳолаш
• Қидирув алгоритмлари

Қидирувда руҳсат этиш

• Агент(агент бўлиб, тизимни бир ҳолатидан иккинчи холатига ўтишида бир неча ҳолатларни ҳисобга олувчи тадқиқотчи, қурилма, механизм бўлиши мумкин) муҳит тўғгрисида тўлиқ аҳборотга эга бўлади, тизим қандай ҳолатда эканлигини аниқлай олади;
• Агентга тизимни бир холатдан иккинчи холатга ўтишини таъминловчи ҳаракатлар тўпламига руҳсат мавжуд бўлиб, бу сифатни таъминлайди;
• Баъзи бир агентларга “мақсад ҳолати” статуси берилади, бунда агентнинг вазифаси – мақсад ҳолатига эришиш учун агент эришилган мақсад ҳақиқий мақсад эканлигин аниқлайди;
• Қидирувни ечими – харакатларнинг кетма-кетлигида(тизим ҳолати ўзгариши), мақсад ҳолатларининг биридан иккинчисига ўтиб туриш жараёни;

Масалани формал аниқланиши Масалалар компоненти 4 жараённи ўз ичига олади

• Бошланғич ҳолат – тизим бошланғич ҳолдатда бўладиган ҳолати;
• Ўтказувчи аниқлаш функцияси – бир ҳолатдан иккинчи ҳолатга ўтишини тасдиқловчи функция;
• Мақсадни текшириш- мавжуд жорий ҳолат “мақсадли ҳолат” эканлигини аниқлаб берувчи алгоритм;
• Йўл қиймати функцияси – ўтишлар орасидаги ҳолатларни ҳар бирини аниқловчи қиймат функцияси. Оддий ҳолатларда ўтишлардаги занжир қиймати занжирдаги холатларнинг барчасига тенг бўлади;

Муаммони ечимини излашнинг алтернатив ҳолати

• ҳолатларнинг кўплиги;
• бош ҳолатдан ҳолатларнинг кўплигини аниқлаш;
• агент учун рухсат этилган ҳаракатлар тўплами;
• ҳаракатлар функцияси(action function) - берилган мавжуд ҳолат учун рухсат этилган ҳолат янги ҳолатни келтириб чиқаради;
• Мақсад ҳолатларининг кўплиги, мантиқли ҳолатлар функцияси, мақсад функция аниқ бўлганда ҳақиқий қийматни қабул қилиниши;
• Мақбул бўлган ечим сифатини аниқлаш критерийси, бунга масалани ечимида харакатларни чегараловчи ҳаракатлар сони, ечимнинг умумий қиймати, харакатларнинг умумий қиймати сони бўйича оптимал ечим талаби;

Ҳолат муҳити графи (explicit graph)

• Матрица ёки рўйҳат кўринишидаги граф алгоритмик қидирувларда ишлатилади
• implicit graph – аниқ бўлмаган графларда қўлланилиб, графлар ўртасидаги қабариқлар ҳотирада сақланиб қолмайди.

Қидирув алгоритмини баҳолаш 4 асосий кўсаткичдан иборат

• Кенглиги — агар алгоритм ҳусусияти мавжуд бўлса, хар доим ечим топади;
• Оптималлик — алгоритм ҳусусияти ҳар доим энг кам қийматли ечим топади;
• Мураккаблик вақти — алгоритмни ишлаш вақти баҳоси;
• Муҳит мураккаблиги — алгоритм учун керакли ҳотира сиғими баҳоси.

Hill Climbing(чўқини заб этиш)

• Мақсад функция мах ёки мin қийматга эришади
• Бир неча параметрлар ичида қидирув ҳолати
• Мақсад функция мах ёки мin қийматга эришадиган қийматни топиш талаб қилинади

Қидирув жараёни

• Исталган ихтиёрий нуқтадан бошланади
• Кейингга ҳолатлар жорий ҳолатнинг кетма-кет ҳолатларининг руйҳати бўйича амалга оширилади
• Яъни хар бир ҳолат олдингисидан битта параметр орқали фарқ қилади

Қидирув жараёни

• Рўйҳатта рухсат этилган қийматлардан максимумга эриштирувчи мақсад функция қиймати танланада
• Алгоритм – мақсад функцияга эриштирадиган бошқа параметр қолмаганлигига ишонч ҳосил қилгандан сўнг тугатилади.

Қидирув алгоритмларини баҳолаш

• Алгоритм керакли ечимни топмаслиги ҳам мумкин. Унга бир неча омиллар яъни, хавф (координата ўқида паралел мавжуд бўлган ечимнинг борлиги) таъсир қилиши мумкин
• Жараёнда алгоритмлар мақсадга эришгунча бир неча марта қайта ишга тушиши мумкин.

Эътиборингиз учун рахмат