Nazariy topshiriqlar To'la tanlov algoritmi

Nazariy topshiriqlar

1.To'la tanlov algoritmi

To'la tanlov (yoki brute force) algoritmini analiz qilishdan oldin algoritm dunyosida asosan 2 ta asosiy tushuncha juda muhim ahamiyatga egadir.

Misol tariqasida tushuntirshga harakat qilaman. Sizga savol qo’limda ma’lumot bor, ushbu ma’lumotni Toshkentdan Londonga yuborishim kerak bu holda qaysi yo’llar orqali yuborsam bo’ladi (masalan:Telegram, facebook, google drive, yandex disk). Siz aytishingiz mumkin ma’lumotni telegramdan yuborishimiz maqul deb chunki tez va qulay. Bu javob doim ham to’g’ri bo’lmaydi sababi siz javob berishdan oldin mendan so’rashingiz kerak edi. Ma’lumotning hajmi qancha deb. Mendagi ma’lumot hajmi 10Gb edi. Endi siz aytgan usul o’zini oqlamasligi mumkin sababi telegram orqali yuborilgan axborot (100Gb lik) tarmoq tezligi 25Mb/s bo’lganda ham yetib borish vaqti 8 soat 53 min 20s da yetib boradi. Eng optimal yo’l samolyotda ma’lumotni yuborsam maqsadga muvofiq bo’ladi.

Istalgan muammoni hal qilishda masala yechimining vaqt va xotiradan oladiga joy jihatlariga alohida e’tibor qaratiladi. Yuqoridagi masala agar ma’lumot telegram orqali yuborilsa biz vaqtdan yutqazar edi.

Algoritmlashda Time Complexity va Space complexity degan tushunchalar mavjud. Endi to’la tanlov algoritmi ni analiz qiklishga kirishsak

To'la tanlov (yoki brute force) algoritmi - matematik muammolarni hal qilish usuli. Har qanday variantni tugatib, echim topish usullari sinfiga tegishli. To'liq qidirishning murakkabligi muammoni hal qilishning barcha mumkin bo'lgan echimlari soniga bog'liq. Agar qaror qabul qilish maydoni juda katta bo'lsa, unda to'liq qidiruv bir necha yil yoki hatto asrlar davomida natijalarga olib kelmasligi mumkin.

To'la tanlov (yoki brute force) algoritmi yuqoridagi vaqt va xotiradan oladigan joy ni deyarli hisobga olmaydi. Bu esa masala yechimini topadi lekin eng yomon holatlarda yechadi degani

NP (non-deterministic polynomial) sinfidagi har qanday muammoni to'liq izlash orqali hal qilish mumkin. Bu holda, har qanday aniq echimdan ob'ektiv funktsiyani hisoblash barcha mumkin bo'lgan echimlarning soniga qarab, ko'paytirilgan vaqt ichida amalga oshirilishi mumkin bo'lsa ham, to'liq qidiruv eksponensial vaqtni talab qilishi mumkin.

Misol tariqasida quyidagi savollarni nazariy jihatdan yechishga harakat qilamiz - bu sayohat qiluvchi sotuvchi muammosi (Traveling Salesman Problem TSP). Aytaylik, sotuvchi butun mamlakat bo'ylab 10 ta shaharga tashrif buyurishi kerak. Qat'iy belgilangan masofani minimallashtirish uchun qaysi shaharlarga borish kerakligini qanday aniqlash mumkin? To'la tanlov (yoki brute force) yechimi oddiygina har bir marshrut uchun umumiy masofani hisoblash va keyin eng qisqa yo'lni tanlashdir. Bu ayniqsa samarali emas, chunki aqlli algoritmlar yordamida ko'plab mumkin bo'lgan yo'nalishlarni yo'q qilish mumkin.