|
Endi faraz qiling P ba'zi yakuniy bo'lmagan chekka uchun to'g'ri F va ruxsat bering T o'z ichiga olgan minimal daraxt bo'lishi F
|
| bet | 6/7 | | Sana | 28.07.2023 | | Hajmi | 0.93 Mb. | | #77545 |
Bog'liq algoritm mustaqil ish иш хақи, Mavzu Antivirus-dasturlari, 1-SINF, V sinf texnologiya va dizayn yo‘nalishi buyicha 5-sinflar uchun , Nometal materiallar, Жуфт сузлар, дарс ишланма сон, BEKLEMISHEV KLASSIFIKATSIYASIGA KO, A new generation of realistic writers, Ochiq faoliyat ishlanma 2, Zamonaviy sun, 1-oktyabr oqituvchi va murabbiylar www.sadikov.uz (1)Endi faraz qiling P ba'zi yakuniy bo'lmagan chekka uchun to'g'ri F va ruxsat bering T o'z ichiga olgan minimal daraxt bo'lishi F. Agar keyingi tanlangan chekka bo'lsa e ham ichida T, keyin P uchun to'g'ri F + e. Aks holda, agar e ichida emas T keyin T + e tsiklga ega C. ushbu tsiklda tegishli bo'lmagan qirralar mavjud F, chunki e qo'shilganda tsikl hosil qilmaydi F lekin qiladi T. ruxsat bering f ichida joylashgan chekka bo'ling C lekin emas F + e. e'tibor bering f shuningdek t ga tegishli va P tomonidan u algoritm tomonidan ko'rib chiqilmagan. Shuning uchun f kamida katta vaznga ega bo'lishi kerak e. keyin T − f + e daraxt va u bir xil yoki kamroq vaznga ega T. shunday qilib T − f + e o'z ichiga olgan minimal daraxt f + e va yana P ushlab turadi. Shuning uchun, induksiya printsipi bo'yicha, P qachon ushlab turadi F yoyilgan daraxtga aylandi, bu faqat agar mumkin bo'lsa F minimal yoyilgan daraxtning o'zi. Parallel algoritm[tahrir] Kruskal algoritmi tabiatan ketma-ket va parallellashtirish qiyin. Biroq, qirralarning dastlabki saralashini parallel ravishda bajarish yoki muqobil ravishda har bir takrorlashda minimal og'irlikdagi qirrani olish uchun ikkilik uyumning parallel bajarilishini ishlatish mumkin.[5] protsessorlarda o'z vaqtida parallel saralash mumkin bo'lganligi sababli, [6] Kruskal algoritmining ish vaqti qisqartirilishi mumkin O(E) (V)), bu erda yana bitta qiymatli Ackermann funktsiyasining teskari tomoni. Kruskal algoritmining filtr-Kruskal nomli varianti Osipov va boshq.[7] va parallelizatsiya uchun yaxshiroq mos keladi. Filtr-Kruskalning asosiy g'oyasi-qirralarni quicksort-ga o'xshash tarzda ajratish va saralash narxini pasaytirish uchun bir xil daraxtning tepalarini bog'laydigan qirralarni filtrlash. Buni quyidagi psevdokod ko'rsatadi.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Endi faraz qiling P ba'zi yakuniy bo'lmagan chekka uchun to'g'ri F va ruxsat bering T o'z ichiga olgan minimal daraxt bo'lishi F
|
