4 І. Негізгі бөлім
Графтардаығы қысқа жолды іздеу
жүктеу/скачать 3,23 Mb.
|
| 1.2. Графтардаығы қысқа жолды іздеу.
Графтардағы қысқа жолды іздеу әдістері графтар теориясының негізгі классикалық есептерінің бірі болып табылады. Графтардағы қысқа жолды іздеу есебі дегеніміз - графтағы жолды құрайтын қабырғалар салмақтарының қосындысы минималданатын екі нүктенің (төбенің) арасындағы ең қысқа жолды іздеу есебі болып табылады. Қысқа (қарапайым, жай) тізбекті геодезиялық тізбек деп те атайды. Қысқа жол туралы есептің әртүрлі қойылу жағдайлары бар. Графтағы қысқа жолды іздеу есебі бағытталған, бағытталмаған немесе аралас графтар үшін анықталуы мүмкін. Бұл жұмыста қарапайым түрде бағытталмаған граф үшін есептің қойылуы қарастырылады. Бағытталған немесе аралас графтар үшін қосымша түрде қабырғалардың бағыттары ескерілуі керек. Графтағы қысқа жолды іздеу есебіне ұқсас болатын есептегіш геометриядағы евклидтік қысқа жолды іздеу есебі, коммивояжер есебі, канадалық саяхатшы есебі, сызықтық программалау есептері т.б. бар. Қарастырылып отырған есептің әртүрлі қойылуларына сәйкес графтағы қысқа жолды іздеу есебін шешудің көптеген алгоритмдері белгілі. Олардың ішінен Дейкстра, Флойд-Уоршелл, Беллман-Форд, Джонсон, Ли (толқындық алгоритм), Килдала алгоритмдерін атауға болады. [1] Сипатталатын алгоритм Дейкстра алгоритмі деп аталады. Дейкстра алгоритмі 1959 жылы нидерландтық оқымысты Эдсгер Дейкстраның ойлап тапқан графтардағы алгоритмі. Бұл алгоритм көмегімен қажетті ақпараттар берілген жағдайда теріс салмақты (теріс мәнді) қабырғалары жоқ графтардың бір төбесінен басқа төбелеріне дейінгі ең қысқа ара қашықтық табылады. Мысалы, сол кезде қажетті ақпараттар берілген жағдайда осы алгоритмді пайдаланып, бір қаладан басқа қалаларға барудың тиімді жолдар тізбегін анықтауға, кай елге мұнайды экспортқа шығару тиімділігін анықтауға мүмкіндік болды. Алгоритм программалауда, және көптеген технологияларда, мысалы OSPF және ІS-ІSмаршруттау хаттамаларында кең түрде қолданылады (OSPF - ағылшынша Open Shortest Path First –каналдың (link-state technology) жағдайын бақылау технологиясына негізделген және қысқа жолды табу үшін Дейкстра алгоритмін (Dijkstra’s algorithm) қолданатын динамикалық маршруттау хаттамасы. IS-IS - қосылыстар жағдайына негізделген маршруттау хаттамасы, алынған ақпаратты алып қор жасақтайды, мұнда да ең тиімді маршрутты есептеу үшін Дейкстра алгоритмі қолданылады). Бұл алгоритмнің бірнеше үлгілері (нұсқалары) бар. Дейкстра (1) алгоритмінің ең қысқа жолдың ұзындығын ғана емес жолдың өзін де анықтайтын қосымша қасиеті бар. Бұл ең қысқа жолдың әрбір төбесі үшін жолдың алдыңғы төбесін көрсетіп отыратын көрсеткіш көмегімен жүзеге асырылады. Сонымен, егер А мен В-ның арасындағы ең қысқа жолдың ұзындығы табылса, онда ең қысқа жолдың бойымен кері бағытта В-дан А-ға қарай қозғала отырып, жолдың өзін табуға болады. Мынадай теореманы тұжырымдаймыз. Теорема. Егер a = v1 және b = v n болғанда v1 , v2 ,.., vi , vi+1 ,...., vj ,vj+1 ,..., vn - а мен b төбелері арасындағы ең қысқа жол (ара қашықтық) болса, онда бұл жолдың i v және j v төбелерінің арасындағы vi ,vi+1 ,...,vj бөлігі де vi және vj төбелерінің арасындағы ең қысқа жол болады. Дейкстра (1) алгоритмі. Дейкстраның бірінші алгоритмінің тұжырымдамасын, одан соң оның қолданылу жағдайларын қарастырамыз. Алгоритмге сәйкес v1 төбесінен vn төбесіне дейінгі ең қысқа ара қашықтық іздестіріледі. v1 төбесінен басталады және v1 төбесінен бастап онымен сыбайлас болатын әрбір төбеге дейінгі 108 ара қашықтық табылады. v1 төбесіне дейінгі ара қашықтық ең аз болатын төбені таңдаймыз, айталық бұл i v төбесі болсын. Бұдан соң, v1 төбесінен бастап vi төбесі арқылы өтетін жол бойынан vi төбесімен сыбайлас болатын әрбір төбеге дейінгі қашықтықты табамыз. Егер бұл қашықтық ағымдағы төбелердің әрқайсысына тағайындалған ара қашықтықтан аз болса, онда олармен ағымдағы ара қашықтықты алмастырамыз. Қайтадан алдыңғы таңдалған төбеден басқа v1 төбесіне жақын төбені таңдап, процесті қайталап жүргіземіз. жүктеу/скачать 3,23 Mb. Достарыңызбен бөлісу:
|