Мирахметова сабина "ДАҒал куч" усули билан тартиблаш. Коммивояжер масаласи

МИРАХМЕТОВА САБИНА
“ДАҒАЛ КУЧ” УСУЛИ БИЛАН ТАРТИБЛАШ. КОММИВОЯЖЕР МАСАЛАСИ.
Алгоритмлар назариясида “ажрат ва хукмронлик қил” тамойили бўйича қурилган алгоритмларни яхлит синфи бор. “Ажрат ва хукмронлик қил” парадигмаси дастлабки мураккаб масалани иккита ёки ундан кўпроқ нисбатан содда масалаларга бўлувчи алгоритмларни бирлаштиради. Ушбу содда масалаларни ечимига асосланиб кейинчалик дастлабки масалала ечими қурилади. Хозирги вақтда алгоритмлашни ушбу тамойили кўп йўналишларда муваффақиятли қўлланилади. Бу ерда биз уларни баъзилари хақида маълумотлар берамиз ва “дагал куч” усулини амалда қўллаш методикасини келтирамиз.
“Дағал куч” атамаси фойдаланишга киритилиши шу билан боғлиқки, масала қисмларга бўлинганда кўп холда бўлиш амала хақида ўйлаб хам ўтирилмайди. Кейинроқ кўрамизки бунга эхтиёж хам бўлмайди. Ушбу тамойилни тасаввур қилиш учун содда масалани кўрайлик.
Берилган сонлар йиғиндисини топинг. Албатта йиғиндини ифодада берилган кетма кетликда тўғридан тўғри бажариш мумкин. Бу холда йиғинди аста секин ошиб боради. Иккинчи усул: аввал жуфт-жуфти билан қўшиб олиб кейин яна жуфтлаб қўшиб оламиз Бу холда оралиқ йиғиндилар нисбатан кичик бўлади.
Иккита натурал сонлар х ва у учун энг катта умумий бўлувчини (ЭКУБ) топувчи Евклид алгоритмини эслайлик. Агар бу сонлар катта бўлса масала анча мураккаб бўлади. Агар уларнинг айирмаси хам ЭКУБга бўлинишини ҳисобга олсак, масалани соддалаштириб x, z сонлар учун ЭКУБ ини топишга ўтишимиз мумкин. Уларни ўсиш тартибида жойлаштириб х деб белгиласак, у холда биз масалани аввалги фақат кичик қийматлардаги берилишига қайтамиз. Бу усулни y-x=x шарт бажарилгунча давом эттирамиз ва ЭКУБ=х оламиз. Таъбиийки, бу дастлабки х эмас. Мисол тариқасида қуйидагини кўрамиз:
х=24; у=64.
1- чи қадам z=y-x=40 x=24; y=40
2 - чи қадам z=y-x=16 x=16; y=24
3 - чи қадам z=y-x=8 x=8; y=16
4 - чи қадам z=y-x=8 бу ерда z=x=8 ЭКУБ бўлади.
Сонлар массивини ўсиш тартибида тартиблаш масаласини кўриб чиқамиз. Ушбу масалани ечиш усулларидан бири қўшни элементларни ўсиш тартибида аста секин ўрин алмаштирилиши . Бу алгоритмни блок схемасини келтирамиз. Бизга n та элементдан иборат а₁, а₂,…,а_n сонлар массиви берилган бўлсин. Уларни ўсиш тартибида жойлаштиришимиз лозим. Агар дастлабки холатни сақлаб қолиш зарурияти бўлса, у холда биз b_i=а_i бўлган ишчи массиви b₁, b₂,…,b_n ни шакиллантиришимиз мумкин.
Алгоритмининг блок - схемасини тузамиз:
10.1 РАСМ

Начало



Ввод N;A;B


k=1÷n-1


i=1÷n-1






да


C= ; ; =c

нет




Вывод B



Конец

Ушбу алгоритм бажарилиши жараёнини тушунтириш учун a_n=min(a₁,a₂,…,a_n) бўлган холни кўрамиз. Агар k=1 бўлганда i бўйича цикл n-1 марта солиштириш бажариб, b_n,, b_n-1, ларни ўрнини алмаштиради ва a_n ҳам b_n-1 ни ўрнини эгаллайди. k=2 бўлганда яна i бўйича циклда n-1 марта солиштиришлар бажарилиб a_n ни ўрнини b_n-2 эгаллайди ва хоказо, шундан сўнг k=n-1 бўлганда a_{n ,} b₁ ўрнини эгаллайди, яъни зарур бўлган жойини эгаллайди.

Табиийки, ҳисоблаш давомида ҳамма a_i лар ҳам ўз ўрнини эгаллайди. Шундай қилиб, бу алгоритм бўйича (n-1)(n-1) марта солиштиришни амалга ошириш керак. Алгоритмнинг самарадорлиги бажарилган амаллар сонига қараб баҳоланади. Ушбу алгоритмда таққослаш операцияси мураккаб(кўп мехнат талаб қиладиган) амал бўлади, бундан келиб чиқадики алгоритмнинг мураккаблиги (n-1)² тартибида бўлади.
Бу масалани ечишнинг яна бир алгоритми, “ажрат ва хукмронлик қил” тамоили асосида ишлайдиган алгоритм бўлади. Ушбу алгоритмга кўра барча массив иккита (тенг) қисмга бўлинади, ўз навбатида бу қисмлар ҳам икки қисмга бўлинади. Қисмларга бўлиш хар бир қисмда битта элемент қолгунча давом эттирилади. Шундан сўнг, бўлинманинг кичик қисмларнинг ҳар бирида тартиблаштириш амалга оширилади, сўнгра ушбу қисмларни берилган массивга тескари тартибда бирлаштириб борилади. Бу жараён дастлабки массив тартибланган холда олингунча давом этади. Алгортмнинг ишлаш тамойилини (принципини) схематик равишда Мисол ёрдамида тасвирлаймиз, бу ерда берилган массив қуйидаги кўринишда 8;7;6;5;4;3;2;1 бўлади.
10.2 чизма.

8 7 6 5

4 3 2 1

8 7

6 5

4 3

2 1



8

7

6

5

4

3

2

1

7 8

5 6

3 4

1 2

5 6 7 8

1 2 3 4

1 2 3 4 5 6 7 8

Ушбу алгоритмга мувофиқ n сонли массивни тартиблаштириш учун nlog₂n га солиштириш амалини бажариш зарурлигига ишонч хосил қилишқийн эмас. Демак бу усуб янада самаралироқ бўлади. Сонли тўпламни иккига қисмга бўлишда биз “қўпол” қилиб a₁, a₂,…a_m биринчи қисми, a_m+1, a_m+2,…,a_2m иккинчи қисми қилиб бўлиб олдик. Сиз албатта аскарларни бўлиниши каби бўлишингиз мумкин, яъни биринчи турган аскар биринчи қисмга, иккинчи турган аскар иккинчи қисмга ва х.к. “Ажрат ва хукмронлик қил” тамоилини қўллаш сифатида хисоблаш пайдо бўлишидан анча олдин киртилган почта хизматидаги манзилларни индекслаш усулини келтириш мумкин.

Почта индексларига кўра хатлар географик жойлашувига қараб, аввал вилоятлар, кейин шаҳарлар, сўнг туманлар бўйича бўлиниб почта алоқаси бўлимларига юборилади ундан сўнг пўчтачилар орқали манзилга етказилади. Ўзингизни почта индексингизни эслаб кўринг, ундаги хар бир рақам географик бўлинишга эгалигини кўриш мумкин. Шу билан бирга сараловчи автомат индекслар бўйича хатларни алохида пакетларга ажратади.
Яна бир турдаги масалада “Ажрат ва хукмронлик қил” тамоили қўлланилиб,бу рекурсив функциялар ёки алгоритмлардир.Агар рекурсия мавжуд бўлса функция ўз ичида ўзига эга бўлади. Буни шартли равишда қуйидагича ёзиш мумкин: