Och ko’z algoritmlar

Och ko’z algoritmlar.

Bajardi: Rustamov Farrukh

Tekshirdi: Abdusalomova Go'zal

Och ko’z algoritmlar. Reja:

• Ochko’z algoritmlarning asoslari.
• Och ko’z algoritmlarning C++ dasturlash tilida ifodalanishi.
• Och ko’z algoritmlarning amaliy tadbig’i.

Och ko’z algoritmlar

Ushbu maqolada biz ochko’z algoritmlar uchun turli xil rejalashtirish algoritmlarini muhokama qilamiz . Ko'pgina rejalashtirish muammolarini ochko'z algoritmlar yordamida hal qilish mumkin.

Muammoning bayoni: N ta hodisaning boshlanish va tugash vaqtlarini hisobga olgan holda , iloji boricha ko'proq voqealarni o'z ichiga olgan jadvalni toping. Hodisani qisman tanlash mumkin emas. Quyidagi voqealarni ko'rib chiqing:

Bunday holda, hodisalarning maksimal soni ikkitadir. Tanlangan B va D hodisalari quyidagicha :

Muammo uchun bir nechta ochko'z algoritmlarni ixtiro qilish mumkin.
Har bir holat bilan ishlaydigan algoritmlar:
Algoritm_1 : 
Birinchi g'oya - iloji boricha qisqa voqealarni tanlash. Misolda, ushbu algoritm quyidagi hodisalarni tanlaydi:

Biroq, qisqa voqealarni tanlash har doim ham to'g'ri strategiya emas. Misol uchun, algoritm quyidagi holatda muvaffaqiyatsiz bo'ladi:

Agar qisqa voqea tanlansa, u faqat bitta hodisani tanlashi mumkin. Biroq, ikkala uzun voqeani ham tanlash mumkin edi.
Algoritm 2 :
Yana bir g'oya har doim imkon qadar erta boshlanadigan keyingi mumkin bo'lgan voqeani tanlashdir. Ushbu algoritm quyidagi hodisalarni tanlaydi:
Yuqoridagi dalilni Krushkal algoritmi yordamida yaxshiroq tushunish mumkin.
Kruskal algoritmi : Bu grafikning minimal chegaralangan daraxtini topish uchun ishlatiladigan ochko'z algoritm.
Kruskal algoritmini quyidagicha ifodalash mumkin: 0. Dastlab hech qanday chekka o‘z ichiga olmaydigan minimal kenglikdagi T daraxtini yarating, 1. G ning e chekkasini tanlang, bunda (a) e T da bo‘lmaydi va … (b) e minimal og‘irlikda. va … (c) e T 2 da sikl yaratmaydi . Agar T G ning barcha uchlarini o‘z ichiga olmasa, 1-bosqichga o‘ting.