DSA ochko‘z (greedy) algoritmlar
Ochko‘z algoritmlar
Ochko‘z algoritm har bir qadamda nima qilishni butun masala qanday ko‘rinishini o‘ylamasdan, faqat joriy vaziyatga asoslanib hal qiladi.
Boshqacha aytganda, ochko‘z algoritm oxir-oqibat global optimal yechimni topishga umid qilib, har bir qadamda lokal optimal tanlovni amalga oshiradi.
Masalan, Dijkstra algoritmida keyingi boriladigan cho‘qqi har doim — tashrif buyurilgan cho‘qqilarning joriy guruhidan qaraganda — manbadan hozirgi paytda eng qisqa masofaga ega bo‘lgan keyingi tashrif buyurilmagan cho‘qqi bo‘ladi.
Demak, Dijkstra algoritmi ochko‘zdir, chunki keyingi qaysi cho‘qqiga borish tanlovi umumiy masalani yoki bu tanlov kelgusidagi qarorlarga yoki oxir-oqibat eng qisqa yo‘llarga qanday ta’sir qilishi mumkinligini hisobga olmasdan, faqat hozirda mavjud ma’lumotlarga asoslanadi.
Ochko‘z algoritmni tanlash — bu loyihalash tanlovi, xuddi dinamik dasturlash algoritm loyihalashdagi boshqa bir tanlov bo‘lgani kabi.
Ochko‘z algoritm ishlashi uchun masala ikkita xususiyatga ega bo‘lishi kerak:
- Ochko‘z tanlov xususiyati: Masala shunday ekanini anglatadiki, uning yechimiga (global optimumga) har bir qadamda ochko‘z tanlovlar (lokal optimal tanlovlar) qilish orqali erishish mumkin.
- Optimal qism tuzilma: Masalaning optimal yechimi qism masalalarning optimal yechimlari to‘plamidan iborat ekanini anglatadi. Demak, masalaning kichikroq qismlarini lokal ravishda (ochko‘z tanlovlar qilish orqali) yechish umumiy yechimga hissa qo‘shadi.
Ushbu darslikdagi masalalarning aksariyati, masalan, massivni saralash yoki grafda eng qisqa yo‘llarni topish shu xususiyatlarga ega, shuning uchun bu masalalarni Selection sort yoki Dijkstra algoritmi kabi ochko‘z algoritmlar yordamida yechish mumkin.
Ammo kommivoyajyor masalasi yoki 0/1 ryukzak masalasi kabi masalalar bu xususiyatlarga ega emas, shuning uchun ularni yechishda ochko‘z algoritmdan foydalanib bo‘lmaydi. Bu masalalar quyida batafsilroq muhokama qilinadi.
Bundan tashqari, masalani ochko‘z algoritm bilan yechish mumkin bo‘lsa ham, uni ochko‘z bo‘lmagan algoritmlar bilan ham yechish mumkin.
Ochko‘z bo‘lmagan algoritmlar
Quyida ochko‘z bo‘lmagan algoritmlar keltirilgan, ya’ni ular har bir qadamda faqat lokal optimal tanlovlar qilishga tayanmaydi:
- Merge Sort: Massivni qayta-qayta ikkiga bo‘ladi, so‘ngra massiv qismlarini saralangan massiv hosil bo‘ladigan tarzda yana birlashtiradi. Bu amallar ochko‘z algoritmlardagi kabi lokal optimal tanlovlar ketma-ketligi emas.
- Quick Sort: Pivot elementni tanlash, elementlarni pivot element atrofida joylashtirish va pivot elementning chap va o‘ng tomoni bilan xuddi shu ishni bajarish uchun rekursiv chaqiruvlar — bu harakatlar ochko‘z tanlovlar qilishga tayanmaydi.
- BFS va DFS orqali aylanib chiqish: Bu algoritmlar grafni har bir qadamda o‘tishni qanday davom ettirish haqida lokal tanlov qilmasdan aylanib chiqadi, shuning uchun ular ochko‘z algoritmlar emas.
- n-Fibonachchi sonini memoizatsiya yordamida topish: Bu algoritm masalalarni yechishning dinamik dasturlash deb ataladigan usuliga tegishli bo‘lib, u ustma-ust tushuvchi qism masalalarni yechadi, so‘ngra ularni qayta birlashtiradi. Umumiy algoritmni optimallashtirish uchun har bir qadamda memoizatsiya qo‘llaniladi, ya’ni har bir qadamda bu algoritm nafaqat lokal optimal yechim nima ekanini ko‘rib chiqadi, balki shu qadamda hisoblangan natija keyingi qadamlarda ishlatilishi mumkinligini ham hisobga oladi.
0/1 ryukzak masalasi
0/1 ryukzak masalasini ochko‘z algoritm bilan yechib bo‘lmaydi, chunki yuqorida aytilganidek, u ochko‘z tanlov xususiyatini ham, optimal qism tuzilma xususiyatini ham qanoatlantirmaydi.
0/1 ryukzak masalasi
Qoidalar:
- Har bir buyumning vazni va qiymati bor.
- Ryukzakingizning vazn chegarasi bor.
- Ryukzakda o‘zingiz bilan qaysi buyumlarni olib ketishni tanlang.
- Buyumni yo olasiz, yo olmaysiz — masalan, buyumning yarmini olib bo‘lmaydi.
Maqsad:
- Ryukzakdagi buyumlarning umumiy qiymatini maksimal darajaga yetkazing.
Bu masalani ochko‘z algoritm bilan yechib bo‘lmaydi, chunki har bir qadamda eng yuqori qiymatli, eng kam vaznli yoki qiymatning vaznga nisbati eng yuqori bo‘lgan buyumni tanlash (lokal optimal yechim, ochko‘z) optimal yechimni (global optimumni) kafolatlamaydi.
Aytaylik, ryukzakingizning chegarasi 10 kg va oldingizda quyidagi uchta xazina bor:
| Xazina | Vazn | Qiymat |
|---|---|---|
| Eski qalqon | 5 kg | $300 |
| Chiroyli bo‘yalgan sopol ko‘za | 4 kg | $500 |
| Metall ot haykalchasi | 7 kg | $600 |
Eng qimmatli narsani birinchi olish orqali ochko‘z tanlov qilish, ya’ni $600 qiymatli ot haykalchasini olish, vazn chegarasini buzmasdan boshqa narsalardan birortasini ham ololmasligingizni anglatadi.
Demak, bu masalani ochko‘z usulda yechishga harakat qilib, qo‘lingizda $600 qiymatli metall ot qoladi.
Ammo bu holatda eng yaxshi yechim — qalqon va ko‘zani olish: bunda vazn chegarasidan oshmagan holda ryukzakdagi umumiy qiymat $800 ga yetadi.
Har doim eng kam vaznli xazinani olsak-chi? Yoki har doim qiymatning vaznga nisbati eng yuqori bo‘lgan xazinani olsak-chi?
Bu tamoyillarga amal qilish ushbu aniq holatda haqiqatan ham eng yaxshi yechimga olib kelsa-da, agar bu misoldagi qiymatlar va vaznlar o‘zgartirilsa, bu tamoyillar ishlashini kafolatlay olmaymiz.
Bu 0/1 ryukzak masalasini ochko‘z algoritm bilan yechib bo‘lmasligini anglatadi.
0/1 ryukzak masalasi haqida bu yerda batafsil o‘qing.
Kommivoyajyor masalasi
Kommivoyajyor masalasi ham ochko‘z algoritm bilan yechib bo‘lmaydigan mashhur masala, chunki yuqorida aytilganidek, u ochko‘z tanlov xususiyatini ham, optimal qism tuzilma xususiyatini ham qanoatlantirmaydi.
Kommivoyajyor masalasining shartiga ko‘ra, siz savdo vakilisiz va mollaringizni sotish uchun bir qancha shahar yoki qishloqlarga borishingiz kerak.
Kommivoyajyor masalasi
Qoidalar: Har bir shaharga faqat bir marta boring, so‘ngra yo‘lni boshlagan shahringizga qayting.
Maqsad: Mumkin bo‘lgan eng qisqa marshrutni toping.
Bu yerda ochko‘z algoritmdan foydalansangiz, har doim hozir turgan shahringizga eng yaqin bo‘lgan keyingi, hali borilmagan shaharga borasiz. Ammo bu ko‘p hollarda sizni eng qisqa umumiy yo‘lga ega optimal yechimga olib kelmaydi.
Quyidagi simulyatsiya ochko‘z algoritm kommivoyajyor masalasini yechishga harakat qilganda qanday ko‘rinishini ko‘rsatadi.
Simulyatsiyani ishga tushirganda algoritm nuqsonli ekani har doim ham yaqqol ko‘rinmasligi mumkin, ammo ba’zan chiziqlar kesishib, umumiy masofani uzaytirib yuborayotganini payqashingiz mumkin, holbuki bunga aniq ehtiyoj yo‘q.
Kommivoyajyor masalasini yechishga harakat qilayotgan ochko‘z algoritm.
Kommivoyajyor masalasiga ochko‘z yondashuvni qo‘llash ba’zan mumkin bo‘lgan eng qisqa marshrutga ancha yaxshi yaqinlashish bersa-da, ochko‘z algoritm umumiy holda kommivoyajyor masalasini yecha olmaydi.
Kommivoyajyor masalasi ochko‘z algoritm bilan yechilishi uchun zarur bo‘lgan xususiyatlarni qanoatlantirmaydi.
Eslatma: Aslida kommivoyajyor masalasida eng qisqa marshrutni samarali topadigan algoritm yo‘q. Biz shunchaki barcha mumkin bo‘lgan marshrutlarni tekshirishimiz kerak! Bu bizga \(O(n!)\) vaqt murakkabligini beradi, ya’ni shaharlar soni (\(n\)) oshirilganda hisoblashlar soni keskin ortib ketadi.
Kommivoyajyor masalasi haqida bu yerda batafsil o‘qing.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!