Tarmoqlanuvchi algoritmlar.Agar hisoblash jarayoni biror bir berilgan shartning bajarilishiga qarab turli tarmoqlar bo‘yicha davom ettirilsa va hisoblash jarayonida har bir tarmoq faqat bir marta bajarilsa, bunday hisoblash jarayonlariga tarmoqlanuvchi algoritmlar deyiladi. Tarmoqlanuvchi algoritmlar uchun ayri strukturasi ishlatiladi. Tarmoqlanuvchi strukturasi berilgan shartning bajarilishiga qarab ko‘rsatilgan tarmoqdan faqat bittasining bajarilishini ta’minlaydi.
|
Taxminiy algoritmlar, bir problemni yechish uchun eng yaxshi yechimni topish uchun ishlatiladigan algoritmlardir. Bu algoritmlar, bir nechta yechimlarni tekshirib chiqish orqali eng yaxshi yechimni topishga harakat qiladi. Taxminiy algoritmlar, kichik va o'rta miqdordagi ma'lumotlar bilan ishlash uchun katta foydali bo'ladi. Masalan, bir foydalanuvchi kiritgan sonning kvadratini topish uchun taxminiy algoritm ishlatilishi mumkin.
Informatika va operatsiyalarni tadqiq qilishda yaqinlashish algoritmlari samarali algoritmlar bo'lib, optimallashtirish masalalariga (xususan, NP-qiyin muammolarga) qaytariladigan yechimning optimalgacha bo'lgan masofasi bo'yicha isbotlangan kafolatlar bilan taxminiy yechim topadi.[1] Taxminlovchi algoritmlar tabiiy ravishda nazariy informatika sohasida keng tarqalgan P ≠ NP gipotezasi natijasida paydo bo'ladi. Ushbu taxminga ko'ra, optimallashtirish muammolarining keng sinfini ko'p nomli vaqtda hal qilish mumkin emas. Shuning uchun yaqinlashtirish algoritmlari sohasi polinom vaqtida bunday masalalarning optimal echimlarini qanchalik yaqinlashtirish mumkinligini tushunishga harakat qiladi. Aksariyat hollarda bunday algoritmlarning kafolati yaqinlashish nisbati yoki yaqinlashish omili sifatida ifodalangan multiplikativ hisoblanadi, ya'ni optimal yechim har doim qaytarilgan yechimning (oldindan belgilangan) multiplikativ omili doirasida bo'lishi kafolatlanadi. Shu bilan birga, qaytarilgan yechim sifatiga qo'shimcha kafolat beradigan ko'plab taxminiy algoritmlar ham mavjud. Ikkalasini ham ta'minlovchi yaqinlashuv algoritmining diqqatga sazovor namunasi Lenstra, Shmoys va Tardos [2] ning bir-biriga bog'liq bo'lmagan parallel mashinalarda rejalashtirish uchun klassik yaqinlashish algoritmidir.
Taxminan algoritmlarni loyihalash va tahlil qilish eng yomon holatda qaytarilgan yechimlar sifatini tasdiqlovchi matematik dalilni o'z ichiga oladi.[1] Bu ularni ba'zi kirishlar bo'yicha juda yaxshi echimlarni topadigan, lekin muvaffaqiyatli yoki muvaffaqiyatsiz bo'lishi mumkinligi haqida aniq ko'rsatma bermaydigan, tavlanish yoki genetik algoritmlar kabi evristikadan ajratib turadi.
Ba'zi mashhur optimallashtirish muammolarini taxmin qilishimiz mumkin bo'lgan chegaralarni yaxshiroq tushunish uchun nazariy kompyuter faniga qiziqish keng tarqalgan. Misol uchun, informatika fanida uzoq vaqtdan beri davom etayotgan ochiq savollardan biri Agraval va boshqalar tomonidan Shtayner Forest muammosi uchun 2-yaqinlashmasidan ustun bo'lgan algoritm mavjudligini aniqlashdir.[3] Qattiq optimallashtirish muammolarini yaqinlik nuqtai nazaridan tushunish istagi hayratlanarli matematik bog'lanishlar va qiyin optimallashtirish muammolari uchun algoritmlarni loyihalashda keng qo'llaniladigan usullarning kashf etilishi bilan bog'liq. Birinchisiga mashhur misollardan biri yuqori o'lchamli geometriyadan foydalangan holda grafik nazariy muammosini hal qiladigan maksimal kesish uchun Goemans-Uilliamson algoritmidir.[4]
|
