Algoritmlarni loyhalash ”fanidan mustaqil ishi qabullagan: ass. M. A. Artikbayev Bajargan: J. M. Sadullayev Nukus-2024 Mavzu: Xoffman daraxtlari. Reja

Download 118,78 Kb.
bet	3/5
Sana	16.05.2024
Hajmi	118,78 Kb.
	#238888

1 2 3 4 5

Bog'liq
Sadullayev Javlonbek Algaritmlarni loyhalash

Prima algoritmi
Algoritm g`oyasi. Graf uchlarining ixtiyoriysi tanlanadi. Sung ushbu uchdan chiqgan barcha qirralardan eng arzon qiymatliysi tanlanadi.Shunday qilib ikkita uchli bitta qirrali daraxtni xosil qilamiz. Shundan sung bir uchi ushbu daraxtga tegishli bo`lgan barcha qirralardan eng arzon qiymatliysi tanlanadi. Bu qirra yoki qirralar, agar eng arzon qiymatliysi bir nechta bo`lsa, daraxtga qo`shiladi.Qirralarni qo`shish jarayoni bunday qo`shishlar sikl xosil qilinguncha davom etadi. Bunday daraxt qurish jarayoni asta sekin grafni barcha uchlarini qamrab oladi. Shunday qilib,graf qirralaridan tashkil topgan daraxt xosil kilamiz, daraxtga qolgan uchlardan ixtiyoriysini qo`shilishi sikl xosil qiladi. Ostov daraxtini qurish jarayonini va yaqqol tasvirini avval keltirilgan misoldak o`ramiz.

11.3rаsm

B D
5 10 C 7
A 8 12 9
6 15 E
G 13 11
8 F
Birinchi etapda biz ixtiyoriy uchini tanlab olamiz. Masalan D uchini tanlaymiz. D uchidan ikkita DC va DE qirralar chiqib, ulardan eng arzon qiymatliysi DC qirra bo`ladi. Shunday qilib bitta qirra DC va ikkita D va C uchdan tashkil topgan daraxt xosil qilamiz.
Ushbu uchlardan DE, SB, SA, SE qirralar chiqadi. Ulardan qiymati bo`yicha eng arzoni SA qirra bo`ladi va uni qurilgan daraxtga qo`shib DSA daraxt xosil qilamiz
11.4rаsm.
D
7
8 C
A
Shundan so`ng ushbu daraxt uchlaridan chiquvchi qirralardan eng arzon qiymatliysini tanlashimiz kerak. Bunday qirralar 6 bo`lib ular: DE, CB, CE, AB, AE, AG .Qiymati bo`yicha eng arzoni AB qirra bo`ladi. Uni qurilgan daraxtga qo`shib D S A V daraxt xosil qilamiz.
11.5rаsm. D
B 7
5 8 C
A

Xuddi shunday qoyida buyicha keyngi bosqichda AG qirra qo`shiladi va yana daraxt xosil qilinadi.

11.6rаsm. D
B 7
A 5 8 C
6
G

Keyingi qadamda GF qirra qo`shiladi va 11.7 rasm ko`rinishidagi daraxt xosil bo`ladi

11.7rаsm.
D
B 7
A 5 8 C
6
G 8
F

Shundаn so`ng ushbu dаrаxtgа qo`shish mumkin bo`lgаn qirrаlаrni qiymаti bo`yichа sаrаlаb DE qirrаni аniqlаymiz vа uni qo`shib 11.8rаsm ko`rinishidаgi dаrаxtni xosil qilаmiz.

11.8rаsm.
D
B 7 9
A 5 8 C E
6
G8
F
Agar bu daraxtni Kruskal algoritmi bo`yicha olingan daraxt bilan solishtirsak, ikkala xolda ham bir xil natijaga erishganimizni ko`ramiz. Ko`rinishidan sodda bo`lgan algoritmni batafsi ltasvirlashimizga sabab shundaki, bu algoritmlarni dasturiy ifodalaganimizda vizual ifodada sezilmagan katta miqdordagi muammolarga duch kelamiz. Dasturiy ifoda jarayonida uchlari, qirralari va ularni insidentligi xaqidagi barcha axborot kompyuter xotirasiga joyilangan bo`lishi kerak va dastur tuzish jarayoni ushbu axboroga asoslangan bo`lishi kerak. Minimal kenglikdagi daraxt. Prim algoritmin ta uchi va m qirrasi boʻlgan ogʻirlikdagi yoʻnaltirilmagan G graf berilgan. Ushbu grafikning barcha uchlarini bog'laydigan va shu bilan birga eng kichik vaznga (ya'ni qirra og'irliklarining yig'indisi) ega bo'lgan pastki daraxtini topish talab qilinadi. Pastki daraxt - bu barcha cho'qqilarni bog'laydigan qirralarning to'plami va istalgan uchdan boshqasiga aniq bitta oddiy yo'l bilan kirishingiz mumkin.
Bunday pastki daraxt minimal kenglikdagi daraxt yoki oddiygina minimal kenglikdagi daraxt deb ataladi. Har qanday grafda n-1 qirralari bo'lishini tushunish oson.Tabiiy sharoitda bu muammo quyidagicha ko'rinadi: n ta shahar bor va har bir juftlik uchun ularni yo'l bilan ulash narxi ma'lum (yoki ularni bog'lab bo'lmasligi ma'lum). Barcha shaharlarni shunday bog'lash talab etiladiki, istalgan shahardan boshqasiga borish mumkin bo'ladi va shu bilan birga yo'l yotqizish xarajatlari minimal bo'ladi.Prim algoritmi
Bu algoritm 1957 yilda ushbu algoritmni kashf etgan amerikalik matematik Robert Prim sharafiga nomlangan. Biroq, 1930 yilda bu algoritmni chex matematigi Voytex Yarnik kashf etgan. Bundan tashqari, Edsger Dijkstra ham 1959 yilda ulardan mustaqil ravishda ushbu algoritmni ixtiro qilgan.

Download 118,78 Kb.

1 2 3 4 5

Download 118,78 Kb.