AMALIY MASHG’ULOT № 6
FAN NOMI |
|
Algoritmlarni loyihalash
| HAFTA |
|
3
| MAVZU: |
|
Kesishmaydigan to‘plam ostilari va birlashmalarini qidirish algoritmi. NP-to‘liq masalalar. NP-to‘liq masalalarga keltirish usullari.
| ISHDAN MAQSAD: |
|
Kesishmaydigan to‘plam ostilari va birlashmalarini qidirish algoritmi. NP-to‘liq masalalar. NP-to‘liq masalalarga keltirish usullari.
|
Qo’yilgan masala. Kesishmaydigan to’plam ostilari va birlashmalarini qidirish algoritmi.
Ish tartibi:
Nazariy qism
Esingizda bo’lsa bu masalani xasislik algoritmlari orqali yechgandik. Xasislik algoritmlarining xususiyatlaridan kelib chiqib, biz o’shanda 3000 natijasini olgandik. Chunki xasislik algoritmi har doim ham optimal yechimni bermaydi, balki, u yechimni tezkorlik bilan topishga yordam beradi. Yechim yetarlicha bo’ladi, lekin optimal bo’lmasligi mumkin. Masala uchun Xasislik algoritmida algoritm murakkabligi bahosi O(n) ga teng.
Do'stlaringiz bilan baham: |