Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги
Запропоновано ефективну паралельну реалiзацiю алгоритму Рамалiнгама для динамiчного оброблення пiдграфа найкоротших шляхiв орiєнтованого графа пiсля додавання до нього однiєї дуги за допомогою моделi асоцiативних паралельних систем з вертикальним обробленням iнформацiї (STAR-машини). Асоцiативна вер...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84107 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / А.Ш. Непомнящая // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 45-57. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84107 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841072015-07-04T03:01:22Z Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги Непомнящая, А.Ш. Кибернетика Запропоновано ефективну паралельну реалiзацiю алгоритму Рамалiнгама для динамiчного оброблення пiдграфа найкоротших шляхiв орiєнтованого графа пiсля додавання до нього однiєї дуги за допомогою моделi асоцiативних паралельних систем з вертикальним обробленням iнформацiї (STAR-машини). Асоцiативна версiя цього алгоритму описана у виглядi процедури InsertNewArc, коректнiсть якої доводиться. Наведено основні переваги асоцiативної версiї iнкрементального алгоритму Рамалiнгама. In this paper, we propose an efficient parallel implementation of the Ramalingam algorithm for the dynamic update of the single-sink shortest path subgraph of a directed graph after adding an edge with the use of the model of associative (content addressable) parallel systems with vertical processing (STAR-machine). An associative version of this algorithm is described as the InsertNewArc procedure, whose correctness is proved. We also present the main advantages of the associative version of the Ramalingam incremental algorithm. 2012 Article Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / А.Ш. Непомнящая // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 45-57. — Бібліогр.: 14 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84107 519.172 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Непомнящая, А.Ш. Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги Кибернетика и системный анализ |
| description |
Запропоновано ефективну паралельну реалiзацiю алгоритму Рамалiнгама для динамiчного оброблення пiдграфа найкоротших шляхiв орiєнтованого графа пiсля додавання до нього однiєї дуги за допомогою моделi асоцiативних паралельних систем з вертикальним обробленням iнформацiї (STAR-машини). Асоцiативна версiя цього алгоритму описана у виглядi процедури InsertNewArc, коректнiсть якої доводиться. Наведено основні переваги асоцiативної версiї iнкрементального алгоритму Рамалiнгама. |
| format |
Article |
| author |
Непомнящая, А.Ш. |
| author_facet |
Непомнящая, А.Ш. |
| author_sort |
Непомнящая, А.Ш. |
| title |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_short |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_full |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_fullStr |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_full_unstemmed |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_sort |
ассоциативная версия алгоритма рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84107 |
| citation_txt |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / А.Ш. Непомнящая // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 45-57. — Бібліогр.: 14 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT nepomnâŝaâaš associativnaâversiâalgoritmaramalingamadlâdinamičeskojobrabotkipodgrafakratčajšihputejposledobavleniâkgrafunovojdugi |
| first_indexed |
2025-07-06T11:03:38Z |
| last_indexed |
2025-07-06T11:03:38Z |
| _version_ |
1836895246853603328 |
| fulltext |
ÓÄÊ 519.172
À.Ø. ÍÅÏÎÌÍßÙÀß
ÀÑÑÎÖÈÀÒÈÂÍÀß ÂÅÐÑÈß ÀËÃÎÐÈÒÌÀ ÐÀÌÀËÈÍÃÀÌÀ
ÄËß ÄÈÍÀÌÈ×ÅÑÊÎÉ ÎÁÐÀÁÎÒÊÈ ÏÎÄÃÐÀÔÀ ÊÐÀÒ×ÀÉØÈÕ
ÏÓÒÅÉ ÏÎÑËÅ ÄÎÁÀÂËÅÍÈß Ê ÃÐÀÔÓ ÍÎÂÎÉ ÄÓÃÈ
Êëþ÷åâûå ñëîâà: îðèåíòèðîâàííûé âçâåøåííûé ãðàô, ïîäãðàô êðàò÷àéøèõ
ïóòåé, ìàòðèöà ñìåæíîñòè, èíêðåìåíòàëüíûé àëãîðèòì, àññîöèàòèâíûé ïà-
ðàëëåëüíûé ïðîöåññîð.
ÂÂÅÄÅÍÈÅ
Çàäà÷à íàõîæäåíèÿ êðàò÷àéøèõ ïóòåé âîçíèêàåò â ðàçëè÷íûõ ïðèëîæåíèÿõ.
Èçâåñòíû äâå âåðñèè ýòîé ïðîáëåìû: íàõîæäåíèå êðàò÷àéøèõ ïóòåé èç îäíîé
âåðøèíû (the single-source shortest paths problem) è ìåæäó êàæäîé ïàðîé âåðøèí
(the all-pairs shortest paths problem). Äèíàìè÷åñêàÿ âåðñèÿ ïðîáëåìû íàõîæäåíèÿ
êðàò÷àéøèõ ïóòåé èç îäíîé âåðøèíû ñîñòîèò â îáðàáîòêå èíôîðìàöèè î êðàò-
÷àéøèõ ïóòÿõ ïðè èçìåíåíèè ãðàôà áåç åãî ïîëíîãî ïåðåâû÷èñëåíèÿ ïîñëå êàæ-
äîãî ëîêàëüíîãî èçìåíåíèÿ â íåì. Òèïè÷íûìè îïåðàöèÿìè äëÿ ýòîãî âèäà ïðåîá-
ðàçîâàíèé ÿâëÿþòñÿ äîáàâëåíèå èëè óäàëåíèå îäíîé äóãè ëèáî èçìåíåíèå åå
âåñà. Åñëè ãðàô ïðåäñòàâëÿåò êîììóíèêàöèîííóþ èëè òðàíñïîðòíóþ ñåòü, òî äî-
áàâëåíèå èëè óäàëåíèå äóãè îòðàæàåò òàêèå èçìåíåíèÿ â ñåòè, êàê äîáàâëåíèå
èëè óäàëåíèå ñâÿçåé âî âðåìÿ ñóùåñòâîâàíèÿ ñåòè. Àëãîðèòì íàçûâàåòñÿ ïîëíî-
ñòüþ äèíàìè÷åñêèì (fully dynamic), åñëè îí ïîçâîëÿåò âûïîëíÿòü ëþáóþ ïîñëå-
äîâàòåëüíîñòü óïîìÿíóòûõ âûøå îïåðàöèé. Àëãîðèòì íàçûâàåòñÿ èíêðåìåíòàëü-
íûì, åñëè îí äîïóñêàåò òîëüêî äîáàâëåíèå äóãè èëè óìåíüøåíèå åå âåñà, è äåê-
ðåìåíòàëüíûì, åñëè ïðîèñõîäèò òîëüêî óäàëåíèå äóãè èëè óâåëè÷åíèå åå âåñà.
 ðàáîòàõ [1, 2] äëÿ ãðàôîâ ñ ïðîèçâîëüíûìè âåùåñòâåííûìè âåñàìè äóã ïî-
ñòðîåíû ïîëíîñòüþ äèíàìè÷åñêèå àëãîðèòìû äëÿ îáðàáîòêè êðàò÷àéøèõ ïóòåé
èç îäíîé âåðøèíû. Ïðè ýòîì ïðåäïîëàãàåòñÿ, ÷òî ãðàô íå èìååò öèêëîâ îòðèöà-
òåëüíîé äëèíû äî è ïîñëå îáðàáîòêè âõîäíîé èíôîðìàöèè. Àâòîðû èñïîëüçóþò
ìîäåëü, ó÷èòûâàþùóþ ñëîæíîñòü âûõîäíîé èíôîðìàöèè ïîñëå ìîäèôèêàöèè
âõîäà. Ñëîæíîñòü äèíàìè÷åñêîãî àëãîðèòìà îöåíèâàåòñÿ ñóììîé ÷èñëà àôôåêò-
íûõ âåðøèí, êîòîðûå ìîäèôèöèðóþò ñâîå êðàò÷àéøåå ðàññòîÿíèå îò êîðíÿ s ïî-
ñëå ïðåîáðàçîâàíèÿ âõîäíîé èíôîðìàöèè, è ÷èñëà äóã, ó êîòîðûõ ïî êðàéíåé
ìåðå îäíà èç âåðøèí ÿâëÿåòñÿ àôôåêòíîé.
 [3] ïîñòðîåíû ïîëóäèíàìè÷åñêèå àëãîðèòìû äëÿ îáðàáîòêè êðàò÷àéøèõ
ðàññòîÿíèé è äåðåâà êðàò÷àéøèõ ïóòåé (sp-tree) êàê â îðèåíòèðîâàííîì, òàê è
â íåîðèåíòèðîâàííîì ãðàôàõ ñ ïîëîæèòåëüíûìè âåùåñòâåííûìè âåñàìè ðåáåð.
Äåêðåìåíòàëüíûå àëãîðèòìû ïðèìåíÿþòñÿ äëÿ ïëàíàðíûõ ãðàôîâ, à èíêðåìåí-
òàëüíûå — äëÿ ïðîèçâîëüíûõ. Âðåìåííàÿ ñëîæíîñòü àëãîðèòìîâ îöåíèâàåòñÿ
â òåðìèíàõ àìîðòèçèðîâàííîãî âðåìåíè.
 ñòàòüå [4] ïîñòðîåíû ïîëíîñòüþ äèíàìè÷åñêèå àëãîðèòìû äëÿ îáðàáîòêè
êðàò÷àéøèõ ðàññòîÿíèé è äåðåâà êðàò÷àéøèõ ïóòåé êàê â îðèåíòèðîâàííîì, òàê
è â íåîðèåíòèðîâàííîì ãðàôàõ ñ ïîëîæèòåëüíûìè äåéñòâèòåëüíûìè âåñàìè ðå-
áåð ïîñëå âûïîëíåíèÿ ïðîèçâîëüíîé ïîñëåäîâàòåëüíîñòè ïðåîáðàçîâàíèé ðåáåð.
Ñòîèìîñòü îïåðàöèè îáðàáîòêè çàäàåòñÿ êàê ôóíêöèÿ îò ÷èñëà ïðåîáðàçîâàíèé
âûõîäíûõ äàííûõ ñ èñïîëüçîâàíèåì ïîíÿòèÿ k-îãðàíè÷åííîé âû÷èñëÿþùåé
ôóíêöèè (k-bounded accounting function).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 45
� À.Ø. Íåïîìíÿùàÿ, 2012
 [5] ïîñòðîåí ïîëíîñòüþ äèíàìè÷åñêèé àëãîðèòì äëÿ îáðàáîòêè êðàò÷àé-
øèõ ïóòåé èç êîðíÿ s â îðèåíòèðîâàííîì ãðàôå ñ ïðîèçâîëüíûìè âåñàìè äóã.
Èñïîëüçóþòñÿ äâà íîâûõ àëãîðèòìà: äëÿ óäàëåíèÿ äóãè è óâåëè÷åíèÿ åå âåñà (êî-
òîðûé ÿâíî ðàáîòàåò ñ öèêëàìè íóëåâîé äëèíû), à òàêæå äëÿ äîáàâëåíèÿ äóãè è
óìåíüøåíèÿ åå âåñà (â êîòîðîì ÿâíî èñïîëüçóþòñÿ öèêëû îòðèöàòåëüíîé äëèíû).
Ñëîæíîñòü îïåðàöèè îáðàáîòêè çàäàåòñÿ êàê ôóíêöèÿ îò ñòðóêòóðû ãðàôà è ÷èñ-
ëà îáðàáîòîê âûõîäíîé èíôîðìàöèè. Âñå óïîìÿíóòûå âûøå àëãîðèòìû
èñïîëüçóþò äèíàìè÷åñêóþ âåðñèþ àëãîðèòìà Äåéêñòðû [6].
 ðàáîòå [7] ïðèâåäåíû äâà èíêðåìåíòàëüíûõ ìåòîäà, êîòîðûå ïîçâîëÿþò
ïðåîáðàçîâàòü õîðîøî èçâåñòíûå ñòàòè÷åñêèå àëãîðèòìû Äåéêñòðû, Áåëëìà-
íà–Ôîðäà è Èñîïî–Ïåéïà â íîâûå äèíàìè÷åñêèå àëãîðèòìû äëÿ îáðàáîòêè äåðå-
âà êðàò÷àéøèõ ïóòåé ïîñëå èçìåíåíèÿ âåñà îäíîé äóãè.
 íàñòîÿùåé ñòàòüå ðàññìîòðåíû îðèåíòèðîâàííûé âçâåøåííûé ãðàô G
ñ âûäåëåííûì ñòîêîì è ïîäãðàô êðàò÷àéøèõ ïóòåé SP G( ), ñîñòîÿùèé èç âñåõ
êðàò÷àéøèõ ïóòåé èç êàæäîé âåðøèíû â ñòîê. Ïîñòðîåíà àññîöèàòèâíàÿ âåðñèÿ
àëãîðèòìà Ðàìàëèíãàìà [1] äëÿ äèíàìè÷åñêîé îáðàáîòêè SP G( ) ïîñëå äîáàâ-
ëåíèÿ îäíîé äóãè ê ãðàôó G.  êà÷åñòâå ìîäåëè âû÷èñëåíèÿ èñïîëüçîâàíà
STAR-ìàøèíà [8], êîòîðàÿ ìîäåëèðóåò ðàáîòó àññîöèàòèâíûõ (êîíòåêñòíî-àäðå-
ñóåìûõ) ïàðàëëåëüíûõ ñèñòåì òèïà SIMD ñ ïîñëåäîâàòåëüíî-ïîðàçðÿäíîé (âåð-
òèêàëüíîé) îáðàáîòêîé èíôîðìàöèè è ïðîñòûìè îäíîáèòîâûìè ïðîöåññîðíûìè
ýëåìåíòàìè. Òàêàÿ àðõèòåêòóðà íàèëó÷øèì îáðàçîì ïðèñïîñîáëåíà ê ðåøåíèþ
çàäà÷ íå÷èñëîâîé îáðàáîòêè, ê êîòîðûì îòíîñÿòñÿ ðåëÿöèîííûå áàçû äàííûõ,
áàçû çíàíèé, òåîðèÿ ãðàôîâ, ýêñïåðòíûå ñèñòåìû è îáðàáîòêà ñåéñìè÷åñêèõ äàí-
íûõ. Ïðåäëîæåíà ïðîñòàÿ è åñòåñòâåííàÿ ñòðóêòóðà äàííûõ, ïîçâîëÿþùàÿ ïî-
ñòðîèòü íà STAR-ìàøèíå ýôôåêòèâíóþ ïàðàëëåëüíóþ ðåàëèçàöèþ èíêðåìåí-
òàëüíîãî àëãîðèòìà Ðàìàëèíãàìà. Àññîöèàòèâíàÿ âåðñèÿ ýòîãî àëãîðèòìà îïèñà-
íà â âèäå ïðîöåäóðû InsertNewArc, êîððåêòíîñòü êîòîðîé äîêàçûâàåòñÿ.
Ïðîöåäóðà âûïîëíÿåòñÿ íà STAR-ìàøèíå ñ òðóäîåìêîñòüþ O hk( ), ãäå h — ÷èñëî
áèòîâ äëÿ êîäèðîâàíèÿ áåñêîíå÷íîñòè, à k — ÷èñëî âåðøèí, äëÿ êîòîðûõ â
SP G( ) èçìåíÿþòñÿ êðàò÷àéøèå ðàññòîÿíèÿ äî ñòîêà ïîñëå äîáàâëåíèÿ ê ãðàôó G
íîâîé äóãè. Ïðè ýòîì ïðåäïîëàãàåòñÿ, ÷òî êàæäàÿ ýëåìåíòàðíàÿ îïåðàöèÿ
STAR-ìàøèíû âûïîëíÿåòñÿ çà åäèíèöó âðåìåíè. Ïðèâåäåíû îñíîâíûå äîñòîèí-
ñòâà àññîöèàòèâíîé âåðñèè èíêðåìåíòàëüíîãî àëãîðèòìà Ðàìàëèíãàìà.
ÌÎÄÅËÜ ÀÑÑÎÖÈÀÒÈÂÍÎÃÎ ÏÀÐÀËËÅËÜÍÎÃÎ ÏÐÎÖÅÑÑÎÐÀ
Îïèøåì êðàòêî èñïîëüçóåìóþ ìîäåëü (ïîäðîáíîå îïèñàíèå è cðàâíåíèå åå ñ
äðóãèìè ìîäåëÿìè àññîöèàòèâíîé îáðàáîòêè ïðèâåäåíû â [9]). Ìîäåëü îïðå-
äåëÿåòñÿ êàê àáñòðàêòíàÿ STAR-ìàøèíà òèïà SIMD ñ âåðòèêàëüíîé îáðàáîò-
êîé èíôîðìàöèè, îñíîâíûìè êîìïîíåíòàìè êîòîðîé ÿâëÿþòñÿ:
� ïîñëåäîâàòåëüíîå óñòðîéñòâî óïðàâëåíèÿ, ãäå çàïèñàíû ïðîãðàììà è ñêà-
ëÿðíûå êîíñòàíòû;
� óñòðîéñòâî àññîöèàòèâíîé îáðàáîòêè, ñîñòîÿùåå èç p îäíîðàçðÿäíûõ ïðî-
öåññîðíûõ ýëåìåíòîâ;
� ìàòðè÷íàÿ ïàìÿòü.
Âõîäíûå äàííûå, çàïèñàííûå â äâîè÷íîì êîäå, ïîìåùàþòñÿ â ìàòðè÷íóþ
ïàìÿòü â âèäå äâóìåðíûõ òàáëèö, ïðè÷åì êàæäàÿ åäèíèöà äàííûõ õðàíèòñÿ â îò-
äåëüíîé ñòðîêå è îáðàáàòûâàåòñÿ îòäåëüíûì ïðîöåññîðíûì ýëåìåíòîì. Ñòðîêè â
òàáëèöàõ íóìåðóþòñÿ ñâåðõó âíèç, à ñòîëáöû — ñëåâà íàïðàâî.  ìàòðè÷íóþ
ïàìÿòü ìîæíî çàãðóæàòü íåñêîëüêî òàáëèö.
Óñòðîéñòâî àññîöèàòèâíîé îáðàáîòêè ïðåäñòàâëÿåò ñîáîé ñîâîêóïíîñòü h
âåðòèêàëüíûõ îäíîðàçðÿäíûõ ðåãèñòðîâ äëèíîé p, êàæäûé èç êîòîðûõ ìîæíî
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
ïðåäñòàâèòü êàê ìàññèâ, ñîñòîÿùèé èç îäíîãî ñòîëáöà. Îáðàáîòêà èíôîðìàöèè
ïðîèñõîäèò ñëåäóþùèì îáðàçîì. Èç äàííîé òàáëèöû â îïðåäåëåííîì ïîðÿäêå èç-
âëåêàþòñÿ îäíîðàçðÿäíûå ñòîëáöû è ïîìåùàþòñÿ â âåðòèêàëüíûå ðåãèñòðû óñòðîé-
ñòâà àññîöèàòèâíîé îáðàáîòêè, â êîòîðîì âûïîëíÿþòñÿ ïîáèòîâûå îïåðàöèè. Ðå-
çóëüòàò âûïîëíåíèÿ ëþáîé îïåðàöèè çàïèñûâàåòñÿ ëèáî â íåêîòîðûé ðåãèñòð, ëèáî
â îïðåäåëåííûé ñòîëáåö îáðàáàòûâàåìîé òàáëèöû, ëèáî â ìàòðè÷íóþ ïàìÿòü.
×òîáû ìîäåëèðîâàòü îáðàáîòêó èíôîðìàöèè â ìàòðè÷íîé ïàìÿòè, STAR-ìà-
øèíà èñïîëüçóåò òèïû äàííûõ slice, word è table. Ñ ïîìîùüþ ïåðåìåííîé òèïà
slice, êîòîðóþ äàëåå áóäåì íàçûâàòü ñëàéñîì, ìîäåëèðóåòñÿ äîñòóï ê òàáëèöå ïî
ñòîëáöàì, à ñ ïîìîùüþ ïåðåìåííîé òèïà word — äîñòóï ïî ñòðîêàì. Ñ êàæäîé
ïåðåìåííîé òèïà table àññîöèèðóåòñÿ ìàòðèöà èç n ñòðîê è k ñòîëáöîâ, ãäå n p� .
Ñ êàæäûì ñëàéñîì àññîöèèðóåòñÿ ïîñëåäîâàòåëüíîñòü èç p êîìïîíåíòîâ, ïðè-
íàäëåæàùèõ ìíîæåñòâó { }0 1, .
Ïóñòü X è Y — ñëàéñû, i j, — ïåðåìåííûå òèïà integer. Ïðèâåäåì íåêîòî-
ðûå îïåðàöèè è ïðåäèêàòû äëÿ ñëàéñîâ:
� SET( )Y çàïèñûâàåò â ñëàéñ Y âñå åäèíèöû;
� CLR( )Y çàïèñûâàåò â ñëàéñ Y âñå íóëè;
� Y i( ) âûäåëÿåò i-é êîìïîíåíò â ñëàéñå Y (1 � �i p);
� FND( )Y âûäàåò ïîðÿäêîâûé íîìåð i ïîçèöèè ïåðâîé (èëè ñòàðøåé) åäèíè-
öû â ñëàéñå Y , ãäå i � 0;
� STEP( )Y âûäàåò òàêîé æå ðåçóëüòàò, êàê è îïåðàöèÿ FND( )Y , è çàòåì «ãà-
ñèò» (ñáðàñûâàåò) ñòàðøóþ åäèíèöó;
� CONVERT( )Y âîçâðàùàåò ñòðîêó, êàæäûé i-é áèò êîòîðîé ñîâïàäàåò ñ Y i( ).
Ýòà îïåðàöèÿ ïðèìåíÿåòñÿ, êîãäà ñòðîêà îäíîé ìàòðèöû èñïîëüçóåòñÿ êàê áèòî-
âûé ñòîëáåö â äðóãîé ìàòðèöå.
Îïåðàöèè FND( )Y , STEP( )Y è CONVERT( )Y ïðèìåíÿþòñÿ òîëüêî â ïðàâîé
÷àñòè îïåðàòîðà ïðèñâàèâàíèÿ, â òî âðåìÿ êàê îïåðàöèÿ Y i( ) ìîæåò èñïîëüçî-
âàòüñÿ â ëþáîé ÷àñòè ýòîãî îïåðàòîðà.
Äëÿ âûïîëíåíèÿ ïàðàëëåëèçìà ïî äàííûì îáùåïðèíÿòûì ñïîñîáîì ââî-
äÿòñÿ ñëåäóþùèå ïîáèòîâûå ëîãè÷åñêèå îïåðàöèè: X Yand — êîíúþíêöèÿ,
X Yor — äèçúþíêöèÿ, not X — îòðèöàíèå, X Yxor — ñðàâíåíèå ïî ìîäóëþ
äâà. Òàêæå èñïîëüçóåòñÿ ïðåäèêàò SOME( )Y , êîòîðûé âîçâðàùàåò çíà÷åíèå true
òîãäà è òîëüêî òîãäà, êîãäà â ñëàéñå Y èìååòñÿ õîòÿ áû îäèí êîìïîíåíò «1».
Óñëîâèìñÿ, ÷òî Y � � îçíà÷àåò, ÷òî ïðåäèêàò SOME( )Y âîçâðàùàåò çíà÷åíèå
true.
Çàìåòèì, ÷òî ïðåäèêàò SOME( )Y è âñå îïåðàöèè äëÿ ñëàéñîâ òàêæå
ïðèìåíÿþòñÿ äëÿ ïåðåìåííûõ òèïà word.
 íàñòîÿùåé ñòàòüå èñïîëüçîâàíà íîâàÿ âåðñèÿ ÿçûêà STAR.  íåé ðàñøèðåí
ñïèñîê ïðåäèêàòîâ è îïåðàöèé äëÿ ïåðåìåííûõ òèïà word. Ñëåäóÿ Ïîòòåðó [10],
äëÿ ïåðåìåííûõ u è v òèïà word îáùåïðèíÿòûì ñïîñîáîì ââåäåíû ïðåäèêàòû:
LESS ( , )u v , EQ( , )u v , NOTEQ( , )u v è GREAT( , )u v .
Äëÿ ïåðåìåííûõ u è v òèïà word ââåäåì îïåðàöèþ ïîáèòîâîãî ñëîæåíèÿ
ADD( , )u v , êîòîðàÿ ìîæåò èñïîëüçîâàòüñÿ òîëüêî â ïðàâîé ÷àñòè îïåðàòîðà ïðè-
ñâàèâàíèÿ.
Äëÿ ïåðåìåííîé u òèïà word ââåäåì îïåðàöèþ REP( , , , )i j u u0 , êîòîðàÿ â çà-
äàííîé ñòðîêå u çàìåíÿåò åå ïîäñòðîêó u i u i u j( ) ( ) ( )�1 � íà ñòðîêó u0 äëèíîé
j i �1 è çàïèñûâàåò ðåçóëüòàò çàìåíû â ñòðîêó u.
Ïóñòü T — ïåðåìåííàÿ òèïà table. Èñïîëüçóåì îïåðàöèè ROW( , )i T è
COL( , )i T , êîòîðûå â ìàòðèöå T âûäåëÿþò i-þ ñòðîêó è i-é ñòîëáåö ñîîòâåòñòâåííî.
Çàìåòèì, ÷òî îïåðàòîðû ÿçûêà STAR ââîäÿòñÿ òàê æå, êàê â ÿçûêå Pascal.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 47
Ïðèâåäåì ãðóïïó áàçîâûõ ïðîöåäóð [11, 12], êîòîðûå âûïîëíÿþòñÿ ñ òðóäî-
åìêîñòüþ O k( ), ãäå k — ÷èñëî áèòîâûõ ñòîëáöîâ â cîîòâåòñòâóþùåé ìàòðèöå,
à òàêæå óêàæåì ñ ïîìîùüþ ãëîáàëüíîãî ñëàéñà X ïîçèöèè àíàëèçèðóåìûõ ñòðîê
â ñîîòâåòñòâóþùèõ ïðîöåäóðàõ:
� MATCH( , , , )T X v Z îäíîâðåìåííî îïðåäåëÿåò ïîçèöèè ñòðîê â çàäàííîé
ìàòðèöå T , ñîâïàäàþùèå ñ çàäàííîé ñòðîêîé v, è âîçâðàùàåò ñëàéñ Z, â êîòîðîì
Z i( ) ' '
1, òîãäà è òîëüêî òîãäà, êîãäà ROW( , )i T v
è X i( ) ' '
1;
� MIN( , , )T X Z îäíîâðåìåííî îïðåäåëÿåò ïîçèöèè ñòðîê â çàäàííîé ìàòðèöå
T , ñîäåðæàùèõ ìèíèìàëüíûé ýëåìåíò, è âîçâðàùàåò ñëàéñ Z, â êîòîðîì Z i( ) ' '
1,
òîãäà è òîëüêî òîãäà, êîãäà ROW( , )i T — ìèíèìàëüíûé ýëåìåíò è X i( ) ' '
1;
� SETMIN( , , , )T F X Z îäíîâðåìåííî îïðåäåëÿåò ïîçèöèè ñòðîê ìàòðèöû T ,
êîòîðûå ìåíüøå ñîîòâåòñòâóþùèõ ñòðîê ìàòðèöû F , è âîçâðàùàåò ñëàéñ Z, â êî-
òîðîì Z i( ) ' '
1, òîãäà è òîëüêî òîãäà, êîãäà ROW ROW( , ) ( , )i T i F� è X i( ) ' '
1;
� HIT( , , , )T F X Z îäíîâðåìåííî îïðåäåëÿåò ïîçèöèè èäåíòè÷íûõ ñòðîê ìàò-
ðèö T è F , èñïîëüçóÿ ñëàéñ X , è âîçâðàùàåò ñëàéñ Z, â êîòîðîì Z i( ) ' '
1, òîãäà è
òîëüêî òîãäà, êîãäà ROW ROW( , ) ( , )i T i F
è X i( ) ' '
1;
� TMERGE( , , )T X F çàïèñûâàåò ñòðîêè ìàòðèöû T , îòìå÷åííûå ' '1 â ñëàéñå
X , â ñîîòâåòñòâóþùèå còðîêè ìàòðèöû F , ïðè ýòîì îñòàëüíûå ñòðîêè ìàòðèöû F
íå ìåíÿþòñÿ;
� TCOPY1( , , , )T j h F çàïèñûâàåò h còîëáöîâ èç ìàòðèöû T , íà÷èíàÿ ñ
( ( ) )1 1� j h -ãî ñòîëáöà, â ðåçóëüòèðóþùóþ ìàòðèöó F , ãäå j � 1;
� CLEAR( , )h T çàïèñûâàåò íóëè â êàæäûé i-é ñòîëáåö çàäàííîé ìàòðèöû T ,
ãäå 1 � �i h;
� ADDV( , , , )T F X R çàïèñûâàåò â ìàòðèöó R ðåçóëüòàò îäíîâðåìåííîãî ñëî-
æåíèÿ ñîîòâåòñòâóþùèõ ñòðîê ìàòðèö T è F , ïîçèöèè êîòîðûõ îòìå÷åíû ' '1
â ñëàéñå X . Ýòîò àëãîðèòì èñïîëüçóåò òàáë. 5.1 èç [13];
� ADDC( , , , )T X v F îäíîâðåìåííî äîáàâëÿåò äâîè÷íîå ñëîâî v ê ñòðîêàì
ìàòðèöû T , îòìå÷åííûõ ' '1 â ñëàéñå X , è çàïèñûâàåò ðåçóëüòàò â ñîîòâåòñòâóþ-
ùèå ñòðîêè ìàòðèöû F , â îñòàëüíûå ñòðîêè ìàòðèöû F çàïèñûâàþòñÿ íóëè;
� SUBTC( , , , )T X v F îäíîâðåìåííî âû÷èòàåò äâîè÷íîå ñëîâî v èç ñòðîê ìàò-
ðèöû T , îòìå÷åííûõ ' '1 â ñëàéñå X , è çàïèñûâàåò ðåçóëüòàò â ñîîòâåòñòâóþùèå
ñòðîêè ìàòðèöû F , â îñòàëüíûå ñòðîêè ìàòðèöû F çàïèñûâàþòñÿ íóëè. Ýòîò àë-
ãîðèòì èñïîëüçóåò òàáë. 5.2 èç [13].
ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß
Ïóñòü G V E wt
( , , ) — îðèåíòèðîâàííûé âçâåøåííûé ãðàô, â êîòîðîì
V n
{ , , , }1 2 � — ìíîæåñòâî âåðøèí, E V V�
— ìíîæåñòâî îðèåíòèðîâàííûõ
ðåáåð (äóã) è wt — ôóíêöèÿ âåñà. Ïîëàãàåì, ÷òî | |V n
è | |E m
.
Ðàññìîòðèì ãðàôû ñ âûäåëåííîé âåðøèíîé s, íàçûâàåìîé ñòîêîì.
Îáîçíà÷èì e i j
( , ) äóãó, êîòîðàÿ îðèåíòèðîâàíà îò âåðøèíû i äî âåðøèíû j.
Ïðè ýòîì âåðøèíà i íàçûâàåòñÿ ãîëîâîé äóãè e (èëè îòöîì), à âåðøèíà j — åå õâîñ-
òîì (èëè ñûíîì). Åñëè ( , )i j E� , òî âåðøèíà j íàçûâàåòñÿ ñìåæíîé ñ âåðøèíîé i.
Ìàòðèöåé ñìåæíîñòè íàçîâåì êâàäðàòíóþ ìàòðèöó A aij
[ ] ðàçìåðà n n
,
ýëåìåíòû êîòîðîé îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì: aij
1 , åñëè âåðøèíà i
ñìåæíà ñ âåðøèíîé j, è aij
0 — â ïðîòèâíîì ñëó÷àå.
Ðàññìîòðèì ãðàôû, äóãè êîòîðûõ èìåþò ïîëîæèòåëüíûé âåñ. Áóäåì ñ÷è-
òàòü, ÷òî wt i j( , )
�, åñëè ( , )i j E� .
Äëÿ ðàññìàòðèâàåìîé çàäà÷è çíà÷åíèå áåñêîíå÷íîñòè âûáèðàåòñÿ ñëåäóþ-
ùèì îáðàçîì:
i
n
ic
�
1
, ãäå ci — ìàêñèìàëüíûé âåñ äóã, âûõîäÿùèõ èç âåðøèíû i
â ãðàôå G. Îáîçíà÷èì h ÷èñëî áèòîâ äëÿ êîäèðîâàíèÿ ýòîé ñóììû.
48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Ïóòåì èç âåðøèíû v1 ê âåðøèíå s â ãðàôå G íàçîâåì ïîñëåäîâàòåëüíîñòü âåð-
øèí v v v sk1 2, , ,�
, â êîòîðîé ( , )v v Ei i� �1 äëÿ 1 1� �i k – è k �1. Êðàò÷àéøèì
ïóòåì èç âåðøèíû i ê ñòîêó íàçîâåì ïóòü ñ ìèíèìàëüíîé ñóììîé âåñîâ åãî äóã.
Îáîçíà÷èì dist l( ) äëèíó êðàò÷àéøåãî ïóòè èç âåðøèíû l ê ñòîêó. Ïóñòü
SP G( ) — ïîäãðàô êðàò÷àéøèõ ïóòåé èç âñåõ âåðøèí ãðàôà G ê ñòîêó.
Ñëåäóÿ Ðàìàëèíãàìó [1], ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ è ïîíÿòèÿ.
Îáîçíà÷èì out ree lSP Gdeg ( ) ( ) ÷èñëî äóã, êîòîðûå âûõîäÿò èç âåðøèíû l â SP G( ).
Ïóñòü Succ u z u z E( ) { / }
� � è Pred u x x u E( ) { / }
� � .
Ïóñòü äóãà ( , )i j äîáàâëÿåòñÿ â ïîäãðàô êðàò÷àéøèõ ïóòåé SP G( ) . Âåðøèíà u
íàçûâàåòñÿ àôôåêòíîé â SP( )G òîãäà è òîëüêî òîãäà, êîãäà dist u i( , ) � wt i j( , ) �
� �dist j dist uold old( ) ( ), ãäå dist u i( , ) — äëèíà êðàò÷àéøåãî ïóòè èç âåðøèíû u ê
âåðøèíå i â íîâîì ãðàôå, wt i j( , ) — âåñ äóãè ( , )i j è dist jold ( ) (ñîîòâåòñòâåííî
dist uold ( )) — äëèíà êðàò÷àéøåãî ïóòè èç âåðøèíû j (ñîîòâåòñòâåííî u) ê ñòîêó
ïåðåä äîáàâëåíèåì äóãè ( , )i j ê ãðàôó G.
ÈÍÊÐÅÌÅÍÒÀËÜÍÛÉ ÀËÃÎÐÈÒÌ ÐÀÌÀËÈÍÃÀÌÀ ÄËß ÎÁÐÀÁÎÒÊÈ ÏÎÄÃÐÀÔÀ
ÊÐÀÒ×ÀÉØÈÕ ÏÓÒÅÉ Ñ ÎÄÍÈÌ ÑÒÎÊÎÌ
Àëãîðèòì Ðàìàëèíãàìà äëÿ äèíàìè÷åñêîé îáðàáîòêè ïîäãðàôà êðàò÷àéøèõ
ïóòåé ïîñëå äîáàâëåíèÿ äóãè ( , )i j ê ãðàôó G èñïîëüçóåò ñòðóêòóðó äàííûõ
êó÷ó PriorityQueue (î÷åðåäü ñ ïðèîðèòåòàìè), â êîòîðîé êàæäîé àôôåêòíîé
âåðøèíå áóäåò ïðèñâîåí êëþ÷. Êëþ÷îì äëÿ àôôåêòíîé âåðøèíû u áóäåò
êðàò÷àéøåå ðàññòîÿíèå îò íåå äî âåðøèíû i. Ïåðâîíà÷àëüíî PriorityQueue
�.
Àëãîðèòì ðàáîòàåò ñëåäóþùèì îáðàçîì.
Âíà÷àëå äóãà ( , )i j äîáàâëÿåòñÿ ê ãðàôó G. Åñëè wt i j dist j dist i( , ) ( ) ( )�
, òî
äóãà ( , )i j äîáàâëÿåòñÿ ê SP G( ) è out ree iSPdeg ( ) óâåëè÷èâàåòñÿ íà åäèíèöó.
Åñëè wt i j dist j dist i( , ) ( ) ( )� � , òî dist i wt i j dist j( ): ( , ) ( )
� è âåðøèíà i âêëþ÷à-
åòñÿ â êó÷ó PriorityQueue ñ êëþ÷îì, ðàâíûì íóëþ.
Êàæäàÿ àôôåêòíàÿ âåðøèíà îáðàáàòûâàåòñÿ ñëåäóþùèì îáðàçîì. Íà êàæ-
äîé èòåðàöèè â òåêóùåé êó÷å âûáèðàåòñÿ àôôåêòíàÿ âåðøèíà, ñêàæåì u, c ìèíè-
ìàëüíûì êëþ÷îì.
Çàòåì èç SP G( ) óäàëÿþòñÿ âñå äóãè âèäà ( , )u x è out ree uSPdeg ( ):
0.
Äàëåå äëÿ êàæäîé âåðøèíû x Succ u� ( ) ïðîâåðÿåòñÿ ñïðàâåäëèâîñòü ñîîòíî-
øåíèÿ wt u x dist x dist u( , ) ( ) ( )�
. Åñëè îíî âûïîëíÿåòñÿ, òî â ïîäãðàô êðàò÷àéøèõ
ïóòåé SP G( ) äîáàâëÿåòñÿ äóãà ( , )u x è out ree uSPdeg ( ) óâåëè÷èâàåòñÿ íà åäèíèöó.
Äëÿ êàæäîé âåðøèíû y Pred u� ( ) ïðîâåðÿåòñÿ ñïðàâåäëèâîñòü ñîîòíîøåíèÿ
wt y u dist u dist y( , ) ( ) ( )�
. Åñëè îíî âûïîëíÿåòñÿ, òî â SP G( ) äîáàâëÿåòñÿ äóãà
( , )y u è outdegree ySP ( ) óâåëè÷èâàåòñÿ íà åäèíèöó.  ïðîòèâíîì ñëó÷àå ïðîâåðÿ-
åòñÿ ñïðàâåäëèâîñòü íåðàâåíñòâà wt y u dist u dist y( , ) ( ) ( )� � . Åñëè îíî âûïîëíÿåò-
ñÿ, òî dist y wt y u dist u( ): ( , ) ( )
� è âåðøèíà y âêëþ÷àåòñÿ â êó÷ó PriorityQueue
ñ êëþ÷îì, ðàâíûì êðàò÷àéøåìó ðàññòîÿíèþ îò âåðøèíû y äî âåðøèíû i. Åñëè
y �PriorityQueue, òî ïðåäûäóùèé êëþ÷ äëÿ y çàìåíÿåòñÿ íà ìåíüøåå çíà÷åíèå.
Àëãîðèòì çàâåðøèòñÿ, êîãäà áóäóò îáðàáîòàíû âñå àôôåêòíûå âåðøèíû.
Ïðèâåäåì âðåìåííóþ ñëîæíîñòü èíêðåìåíòàëüíîãî àëãîðèòìà Ðàìàëèíãàìà.
Ïóñòü k — ÷èñëî àôôåêòíûõ âåðøèí â ïîäãðàôå êðàò÷àéøèõ ïóòåé ïîñëå äîáàâ-
ëåíèÿ ê ãðàôó íîâîé äóãè, à r — ÷èñëî àôôåêòíûõ âåðøèí è àôôåêòíûõ äóã,
ó êîòîðûõ ïî êðàéíåé ìåðå îäíà èç âåðøèí ÿâëÿåòñÿ àôôåêòíîé. Òîãäà àëãîðèòì
Ðàìàëèíãàìà âûïîëíÿåò O k r k r(( ) ( ))� �log àðèôìåòè÷åñêèõ îïåðàöèé.
Íåòðóäíî çàìåòèòü, ÷òî â ïðîöåññå âûïîëíåíèÿ èíêðåìåíòàëüíîãî àëãîðèò-
ìà Ðàìàëèíãàìà ñòðîèòñÿ äåðåâî ñ êîðíåì i, ñîñòîÿùåå èç àôôåêòíûõ âåðøèí,
ïðè÷åì èç êàæäîé àôôåêòíîé âåðøèíû r ñóùåñòâóåò åäèíñòâåííûé ïóòü ê âåð-
øèíå i. Ïåðâîíà÷àëüíî äåðåâî ñîñòîèò èç êîðíÿ i. Íà êàæäîé èòåðàöèè â ñòðîÿ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 49
ùååñÿ äåðåâî äîáàâëÿåòñÿ òà àôôåêòíàÿ âåðøèíà l, äëÿ êîòîðîé dist l dist i( ) ( )
èìååò ìèíèìàëüíîå çíà÷åíèå.
Îáîçíà÷èì Ti äåðåâî, êîòîðîå áóäåò ïîñòðîåíî â ïðîöåññå äèíàìè÷åñêîé îá-
ðàáîòêè ïîäãðàôà êðàò÷àéøèõ ïóòåé ïîñëå äîáàâëåíèÿ äóãè ( , )i j ê ãðàôó G.
ÀÑÑÎÖÈÀÒÈÂÍÀß ÂÅÐÑÈß ÈÍÊÐÅÌÅÍÒÀËÜÍÎÃÎ ÀËÃÎÐÈÒÌÀ ÐÀÌÀËÈÍÃÀÌÀ
×òîáû ïîñòðîèòü àññîöèàòèâíóþ âåðñèþ èíêðåìåíòàëüíîãî àëãîðèòìà Ðàìà-
ëèíãàìà äëÿ äèíàìè÷åñêîé îáðàáîòêè ïîäãðàôà êðàò÷àéøèõ ïóòåé, èñïîëüçóåì
ñëåäóþùóþ ñòðóêòóðó äàííûõ:
� ìàòðèöà ñìåæíîñòè G ðàçìåðà n n
, êàæäûé i-é ñòîëáåö êîòîðîé õðàíèò
ñ ïîìîùüþ ' '1 âñåõ ñûíîâåé âåðøèíû i;
� ìàòðèöà ñìåæíîñòè SP ðàçìåðà n n
, êàæäûé i-é ñòîëáåö êîòîðîé õðàíèò
ñ ïîìîùüþ ' '1 ñûíîâåé âåðøèíû i, ïðèíàäëåæàùèõ ïîäãðàôó êðàò÷àéøèõ ïóòåé;
� ìàòðèöà Weight ðàçìåðà n hn
, ýëåìåíòàìè êîòîðîé ÿâëÿþòñÿ âåñà äóã. Îíà
ñîñòîèò èç n ïîëåé, ïðè÷åì êàæäîå ïîëå ñîñòîèò èç h áèòîâ. Âåñ äóãè ( , )i j çàïè-
ñûâàåòñÿ â j-þ ñòðîêó i-ãî ïîëÿ;
� ìàòðèöà Cost ðàçìåðà n hn
, ýëåìåíòàìè êîòîðîé ÿâëÿþòñÿ âåñà äóã. Îíà
ñîñòîèò èç n ïîëåé, ïðè÷åì êàæäîå ïîëå ñîñòîèò èç h áèòîâ. Âåñ äóãè ( , )i j çàïè-
ñûâàåòñÿ â i-þ ñòðîêó j-ãî ïîëÿ;
� ìàòðèöà Dist ðàçìåðà n h
, êàæäàÿ i-ÿ ñòðîêà êîòîðîé õðàíèò êðàò÷àéøåå
ðàññòîÿíèå îò âåðøèíû i äî ñòîêà.
Çàìåòèì, ÷òî êàæäîå i-å ïîëå ìàòðèöû Weight õðàíèò âåñà äóã, âûõîäÿùèõ èç
âåðøèíû i, òîãäà êàê i-å ïîëå ìàòðèöû Cost õðàíèò âåñà äóã, çàõîäÿùèõ â âåðøèíó i.
Ïðèâåäåì ñëåäóþùåå ñâîéñòâî ìàòðèö G è SP.
Ñâîéñòâî 1.  êàæäîé i -é ñòðîêå ìàòðèö G è SP îòìå÷åíû ' '1 ãîëîâû äóã, çà-
õîäÿùèõ â âåðøèíó i.
Ïóñòü äóãà ( , )i j äîáàâëåíà ê ãðàôó G.
Àññîöèàòèâíûé ïàðàëëåëüíûé àëãîðèòì (ñêàæåì, àëãîðèòì À) äëÿ îáðàáîò-
êè äóã, âûõîäÿùèõ èç àôôåêòíîé âåðøèíû k, âûïîëíÿåò ñëåäóþùèå øàãè.
Øàã 1. Ñ ïîìîùüþ ñëàéñà (ñêàæåì, Z) ñîõðàíèòü ïîçèöèè âñåõ äóã, êîòîðûå
â ãðàôå G âûõîäÿò èç âåðøèíû k.
Øàã 2. Îäíîâðåìåííî îïðåäåëèòü äëèíó ðàçëè÷íûõ ïóòåé, âåäóùèõ èç âåð-
øèíû k ê ñòîêó s è âêëþ÷àþùèõ äóãó, îòìå÷åííóþ ' '1 â ñëàéñå Z.
Øàã 3. Ñ ïîìîùüþ ñëàéñà (ñêàæåì, Y ) ñîõðàíèòü ïîçèöèè òåõ äóã ( , )k l , äëÿ
êîòîðûõ dist k wt k l dist l( ) ( , ) ( )
� .
Øàã 4. Âêëþ÷èòü â ìàòðèöó SP ïîçèöèè äóã, îòìå÷åííûõ ' '1 â ñëàéñå Y .
Íà STAR-ìàøèíå ýòîò àëãîðèòì ðåàëèçîâàí â âèäå ïðîöåäóðû
UpdateOutgoingArcs.
Àññîöèàòèâíûé ïàðàëëåëüíûé àëãîðèòì (ñêàæåì, àëãîðèòì B) äëÿ îáðàáîò-
êè äóã, çàõîäÿùèõ â àôôåêòíóþ âåðøèíó k, âûïîëíÿåò ñëåäóþùèå øàãè.
Øàã 1. Ñ ïîìîùüþ ñëàéñà (ñêàæåì, Z) ñîõðàíèòü ãîëîâû äóã, êîòîðûå â ãðà-
ôå G çàõîäÿò â àôôåêòíóþ âåðøèíó k.
Øàã 2. Äëÿ âñåõ âåðøèí l, îòìå÷åííûõ ' '1 â ñëàéñå Z, îäíîâðåìåííî îïðåäå-
ëèòü íîâûå êðàò÷àéøèå ðàññòîÿíèÿ îò l äî ñòîêà â êàæäîì ïóòè, íà÷èíàþùèìñÿ
äóãîé ( , )l k .
Øàã 3. Äîáàâèòü â ìàòðèöó SP ïîçèöèè òåõ äóã âèäà ( , )r k , äëÿ êîòîðûõ
dist r wt r k dist k( ) ( , ) ( )
� .
Øàã 4. Ñ ïîìîùüþ ñëàéñà (ñêàæåì, Y ) ñîõðàíèòü ïîçèöèè òåõ âåðøèí r, îò-
ìå÷åííûõ ' '1 â ñëàéñå Z, äëÿ êîòîðûõ dist r dist rnew old( ) ( )� . Çàòåì çàïèñàòü
dist rnew ( ) â ñîîòâåòñòâóþùèå ñòðîêè ìàòðèöû Dist.
50 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Íà STAR-ìàøèíå ýòîò àëãîðèòì ðåàëèçîâàí â âèäå ïðîöåäóðû
UpdateIncomingArcs.
Ðàññìîòðèì àññîöèàòèâíûé ïàðàëëåëüíûé àëãîðèòì äëÿ äèíàìè÷åñêîé îá-
ðàáîòêè ïîäãðàôà êðàò÷àéøèõ ïóòåé ïîñëå äîáàâëåíèÿ ê ãðàôó G íîâîé äóãè
( , )i j ñ âåñîì v0. Ïóñòü ïåðåìåííàÿ v2 õðàíèò êðàò÷àéøåå ðàññòîÿíèå îò âåðøèíû
i äî ñòîêà â èñõîäíîì SP G( ). Àëãîðèòì èñïîëüçóåò ñëàéñ Z1, êîòîðûé õðàíèò ïî-
çèöèè òåêóùèõ àôôåêòíûõ âåðøèí, è ìàòðèöó Queue ðàçìåðà n h
, êàæäàÿ l-ÿ
ñòðîêà êîòîðîé õðàíèò êðàò÷àéøåå ðàññòîÿíèå îò âåðøèíû l äî âåðøèíû i â
òåêóùåì ïîäãðàôå êðàò÷àéøèõ ïóòåé.
Àëãîðèòì âûïîëíÿåò ñëåäóþùèå øàãè.
Øàã 1. Äîáàâèòü ïîçèöèþ äóãè ( , )i j â ìàòðèöó G, à åå âåñ v0 äîáàâèòü â ìàò-
ðèöû Weight è Cost.
Øàã 2. Îïðåäåëèòü ðàññòîÿíèå (ñêàæåì, v3) îò âåðøèíû i äî ñòîêà, êîãäà
ïóòü ïðîõîäèò ÷åðåç âåðøèíó j.
Øàã 3. Åñëè v v2 3
, òî äîáàâèòü ïîçèöèþ äóãè ( , )i j â ìàòðèöó SP. Çàòåì ïå-
ðåéòè íà âûõîä.
Øàã 4. Åñëè v v3 2� , òî çàïèñàòü çíà÷åíèå v3 â i-þ ñòðîêó ìàòðèöû Dist, óñòà-
íîâèòü äëÿ àôôåêòíîé âåðøèíû i ìàêñèìàëüíûé ïðèîðèòåò â ìàòðèöå Queue è
âêëþ÷èòü âåðøèíó i â ñëàéñ (cêàæåì, Z1).
Øàã 5. Ïîêà Z1 � �, îáðàáîòàòü àôôåêòíûå âåðøèíû ñ ó÷åòîì èõ íîâûõ ðàñ-
ñòîÿíèé äî ñòîêà ñëåäóþùèì îáðàçîì:
� âûäåëèòü â ìàòðèöå Queue âåðøèíó ñ ìàêñèìàëüíûì ïðèîðèòåòîì (ñêà-
æåì, k) è óäàëèòü åå èç ñëàéñà Z1;
� îäíîâðåìåííî óäàëèòü èç ìàòðèöû SP âñå äóãè, âûõîäÿùèå èç âåðøèíû k;
� c ïîìîùüþ àëãîðèòìà À íàéòè ïîçèöèè äóã âèäà ( , )k l , äëÿ êîòîðûõ
dist k wt k l dist l( ) ( , ) ( )
� , è äîáàâèòü èõ â ìàòðèöó SP;
� c ïîìîùüþ àëãîðèòìà B ñíà÷àëà îäíîâðåìåííî íàéòè ïîçèöèè òåõ äóã âèäà
( , )r k , äëÿ êîòîðûõ dist r wt r k dist k( ) ( , ) ( )
� , è äîáàâèòü èõ â ìàòðèöó SP. Çàòåì
îäíîâðåìåííî íàéòè ïîçèöèè íîâûõ àôôåêòíûõ âåðøèí l è çàïèñàòü dist lnew ( )
â ñîîòâåòñòâóþùèå ñòðîêè ìàòðèöû Dist;
� äëÿ íîâûõ àôôåêòíûõ âåðøèí l îäíîâðåìåííî âû÷èñëèòü çíà÷åíèÿ dist l( )
— dist i( ) è çàïèñàòü èõ â ñîîòâåòñòâóþùèå ñòðîêè ìàòðèöû Queue;
� âêëþ÷èòü íîâûå àôôåêòíûå âåðøèíû â ñëàéñ Z1.
Íà STAR-ìàøèíå ýòîò àëãîðèòì ðåàëèçîâàí â âèäå ïðîöåäóðû InsertNewArc.
ÏÐÅÄÑÒÀÂËÅÍÈÅ ÍÀ STAR-ÌÀØÈÍÅ ÀÑÑÎÖÈÀÒÈÂÍÎÉ ÂÅÐÑÈÈ
ÈÍÊÐÅÌÅÍÒÀËÜÍÎÃÎ ÀËÃÎÐÈÒÌÀ ÐÀÌÀËÈÍÃÀÌÀ
Ðàññìîòðèì äâå âñïîìîãàòåëüíûå ïðîöåäóðû, ðåàëèçóþùèå àëãîðèòìû A è B,
à çàòåì îñíîâíóþ ïðîöåäóðó äëÿ äèíàìè÷åñêîé îáðàáîòêè ïîäãðàôà êðàò÷àé-
øèõ ïóòåé ïîñëå äîáàâëåíèÿ ê èñõîäíîìó ãðàôó íîâîé äóãè.
Âñïîìîãàòåëüíàÿ ïðîöåäóðà UpdateOutgoingArcs. Çíàÿ òåêóùóþ îáðàáà-
òûâàåìóþ âåðøèíó k, ÷èñëî áèòîâ h äëÿ êîäèðîâàíèÿ áåñêîíå÷íîñòè è òåêóùèå
ìàòðèöû G, SP, Weight è Dist, ïðîöåäóðà âîçâðàùàåò îáðàáîòàííóþ ìàòðèöó SP.
procedure UpdateOutgoingArcs(h,k: integer; G: table; Weight: table;
Dist: table; var SP: table);
/* Çäåñü h — ÷èñëî áèòîâ äëÿ êîäèðîâàíèÿ áåñêîíå÷íîñòè, k — íîìåð
îáðàáàòûâàåìîé âåðøèíû. */
var W1,W2: table; v: word(Dist); Y, Z: slice(G);
1. Begin Z := COL(k,G);
2. TCOPY1(Weight,h,k,W1);
3. ADDV(W1,Dist,Z,W2);
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 51
/* Ìàòðèöà W 2 õðàíèò ðàçëè÷íûå ðàññòîÿíèÿ îò âåðøèíû k äî ñòîêà. */
4. v:=ROW(k,Dist);
/* Còðîêà v õðàíèò êðàò÷àéøåå ðàññòîÿíèå îò âåðøèíû k äî ñòîêà. */
5. MATCH(W2,Z,v,Y);
/*  ñëàéñå Y îòìå÷åíû ' '1 òå âåðøèíû l ãðàôà G,
äëÿ êîòîðûõ dist k wt k l dist l( ) ( , ) ( )
� . */
6. COL(k,SP):=Y;
/* Äóãè âèäà ( , )k l äîáàâëÿþòñÿ â SP. */
7. End;
Óòâåðæäåíèå 1. Ïóñòü çàäàíû ÷èñëî áèòîâ h äëÿ êîäèðîâàíèÿ áåñêîíå÷íîñ-
òè è íîìåð îáðàáàòûâàåìîé âåðøèíû k, à òàêæå òåêóùèå ìàòðèöû G, SP, Weight
è Dist. Òîãäà ïîñëå âûïîëíåíèÿ ïðîöåäóðû UpdateOutgoingArcs â ìàòðèöó SP äî-
áàâÿòñÿ òå äóãè âèäà ( , )k l , äëÿ êîòîðûõ âûïîëíèòñÿ ñîîòíîøåíèå
dist k wt k l dist l( ) ( , ) ( )
� . (1)
Äîêàçàòåëüñòâî. Îò ïðîòèâíîãî. Ïóñòü â ãðàôå G åñòü äóãà ( , )k r , êîòîðàÿ
óäîâëåòâîðÿåò ñîîòíîøåíèþ (1), îäíàêî ïîñëå çàâåðøåíèÿ ïðîöåäóðû
UpdateOutgoingArcs ýòà äóãà íå áóäåò âêëþ÷åíà â ìàòðèöó SP. Äîêàæåì, ÷òî ýòî
ïðîòèâîðå÷èò âûïîëíåíèþ íàøåé ïðîöåäóðû.
Äåéñòâèòåëüíî, òàê êàê ( , )k r G� , òî ïîñëå âûïîëíåíèÿ ñòðîêè 1 Z r( ) ' '
1.
Ïîñëå âûïîëíåíèÿ ñòðîê 2 è 3 â r-é ñòðîêå ìàòðèöû W2 áóäåò çàïèñàíà äëèíà
ïóòè èç âåðøèíû k ê ñòîêó, âêëþ÷àþùåãî äóãó ( , )k r . Ïî ïðåäïîëîæåíèþ äóãà
( , )k r óäîâëåòâîðÿåò ñîîòíîøåíèþ (1). Ïîýòîìó ïîñëå âûïîëíåíèÿ ïðîöåäóðû
MATCH ïîëó÷èì Y r( ) ' '
1. Òîãäà ïîñëå âûïîëíåíèÿ ñòðîêè 6 äóãà ( , )k r áóäåò äî-
áàâëåíà â ìàòðèöó SP. Ýòî ïðîòèâîðå÷èò íàøåìó äîïóùåíèþ.
Âñïîìîãàòåëüíàÿ ïðîöåäóðà UpdateIncomingArcs. Çíàÿ òåêóùóþ îáðàáà-
òûâàåìóþ âåðøèíó k, ÷èñëî áèòîâ h äëÿ êîäèðîâàíèÿ áåñêîíå÷íîñòè è òåêóùèå
ìàòðèöû G, SP, Cost è Dist, ïðîöåäóðà âîçâðàùàåò ñëàéñ Y è îáðàáîòàííûå ìàò-
ðèöû Dist è SP.
procedure UpdateIncomingArcs(h,k: integer; G: table; Cost: table;
var Y: slice(G); var Dist: table; var SP: table);
var X,Z: slice(G);
v: word(G);
v1: word(Dist);
W,W1: table;
1. Begin v := ROW(k,G); Z := CONVERT(v);
/* Ñëàéñ Z õðàíèò ãîëîâû äóã, êîòîðûå çàõîäÿò â âåðøèíó k. */
2. v1 := ROW(k,Dist);
/* Còðîêà v1 õðàíèò êðàò÷àéøåå ðàññòîÿíèå îò k äî s. */
3. TCOPY1(Cost,k,h,W1);
/* Ìàòðèöà W1 õðàíèò k-å ïîëå ìàòðèöû Cost. */
4. ADDC(W1,Z,v1,W);
/*  êàæäîé l-é ñòðîêå ìàòðèöû W, îòìå÷åííîé ' '1 â ñëàéñå Z, çàïèñàíî
íîâîå ðàññòîÿíèå îò l äî ñòîêà. */
5. HIT(W,Dist,Z,X);
/*  ñëàéñå X îòìå÷åíû ' '1 ïîçèöèè òåõ ñòðîê ìàòðèöû Dist, â êîòîðûõ
dist l wt l k dist k( ) ( , ) ( )
� . */
6. v := CONVERT(X);
7. ROW(k,SP) := v;
/* Â ìàòðèöó SP äîáàâëÿþòñÿ äóãè âèäà ( , )r k , äëÿ êîòîðûõ
dist r wt r k dist k( ) ( , ) ( )
� . */
8. SETMIN(W,Dist,Z,Y);
/*  ñëàéñå Y îòìå÷åíû ' '1 ïîçèöèè òåõ âåðøèí, ó êîòîðûõ íîâîå
ðàññòîÿíèå äî ñòîêà óìåíüøèëîñü. */
52 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
9. TMERGE(W,Y,Dist);
/*  l-þ ñòðîêó ìàòðèöû Dist çàïèñûâàåòñÿ íîâîå çíà÷åíèå dist l( ) òîãäà è
òîëüêî òîãäà, êîãäà Y l( ) ' '
1. */
10. End;
Óòâåðæäåíèå 2. Ïóñòü çàäàíû ÷èñëî áèòîâ h äëÿ êîäèðîâàíèÿ áåñêîíå÷íîñ-
òè è íîìåð òåêóùåé îáðàáàòûâàåìîé âåðøèíû k, à òàêæå çàäàíû òåêóùèå ìàòðè-
öû G, SP, Cost è Dist. Òîãäà ïðîöåäóðà UpdateIncomingArcs âîçâðàùàåò ñëàéñ Y è
èçìåíåííûå ìàòðèöû Dist è SP. Ïðè ýòîì â ìàòðèöó SP äîáàâëÿþòñÿ äóãè âèäà
( , )l k , äëÿ êîòîðûõ dist l wt l k dist k( ) ( , ) ( )
� , ñëàéñ Y õðàíèò ãîëîâû òåõ äóã ( , )r k ,
äëÿ êîòîðûõ dist r dist rnew old( ) ( )� , è íîâûå ðàññòîÿíèÿ dist rnew ( ) çàïèñûâàþòñÿ â
ìàòðèöó Dist.
Äîêàçàòåëüñòâî. Áóäåì äîêàçûâàòü îò ïðîòèâíîãî. Ïóñòü âíà÷àëå ( , )l k G�
è dist l wt l k dist k( ) ( , ) ( )
� . Îäíàêî ïîñëå çàâåðøåíèÿ ïðîöåäóðû UpdateIncomingArcs
äóãà ( , )l k íå áóäåò äîáàâëåíà â ìàòðèöó SP. Äîêàæåì, ÷òî ýòî ïðîòèâîðå÷èò âû-
ïîëíåíèþ íàøåé ïðîöåäóðû.
Äåéñòâèòåëüíî, ñîãëàñíî ñâîéñòâó 1 â k-é ñòðîêå ìàòðèöû G îòìå÷åíû ' '1 òå
âåðøèíû, èç êîòîðûõ âûõîäèò äóãà â âåðøèíó k. Ïîýòîìó â ðåçóëüòàòå âûïîëíå-
íèÿ ñòðîêè 1 ñëàéñ Z õðàíèò ãîëîâû äóã, êîòîðûå çàõîäÿò â âåðøèíó k. Òàê êàê
( , )l k G� , òî Z l( ) ' '
1. Ïîñëå âûïîëíåíèÿ ñòðîêè 2 ïåðåìåííàÿ v1 õðàíèò êðàò÷àé-
øåå ðàññòîÿíèå îò âåðøèíû k äî ñòîêà. Ïîñëå âûïîëíåíèÿ ñòðîêè 3 â l-é ñòðîêå
ìàòðèöû W1 áóäåò çàïèñàí âåñ äóãè ( , )l k . Íåïîñðåäñòâåííî ïðîâåðÿåòñÿ, ÷òî
ïîñëå âûïîëíåíèÿ ñòðîêè 4 â l-é ñòðîêå ìàòðèöû W, îòìå÷åííîé ' '1 â ñëàéñå Z,
áóäåò çàïèñàíî íîâîå êðàò÷àéøåå ðàññòîÿíèå îò âåðøèíû l äî ñòîêà, ïðè÷åì
êðàò÷àéøèé ïóòü íà÷èíàåòñÿ äóãîé ( , )l k . Ïî ïðåäïîëîæåíèþ dist l wt l k( ) ( , )
�
�dist k( ). Ïîýòîìó ïîñëå âûïîëíåíèÿ ñòðîê 5 è 6 ïîëó÷àåì v l( ) ' '
1. Òîãäà ïîñëå
âûïîëíåíèÿ ñòðîêè 7 l-é áèò k-é ñòðîêè ìàòðèöû SP áóäåò ðàâåí ' '1. Ýòî îçíà÷àåò,
÷òî äóãà ( , )l k äîáàâëåíà â ìàòðèöó SP. Ýòî ïðîòèâîðå÷èò íàøåìó äîïóùåíèþ.
Ïóñòü òåïåðü ( , )r k G� è dist r dist rnew old( ) ( )� . Îäíàêî ïîñëå çàâåðøåíèÿ
ïðîöåäóðû UpdateIncomingArcs r-ÿ ñòðîêà â ìàòðèöå Dist íå èçìåíèëàñü. Äîêà-
æåì, ÷òî ýòî ïðîòèâîðå÷èò âûïîëíåíèþ ýòîé ïðîöåäóðû.
Äåéñòâèòåëüíî, ïîñêîëüêó dist r dist rnew old( ) ( )� , òî ïîñëå âûïîëíåíèÿ áàçîâîé ïðî-
öåäóðû SETMIN( , , , )W Dist Z Y (ñòðîêà 8) ïîëó÷àåì Y r( ) ' '
1. Òîãäà ïîñëå âûïîëíåíèÿ
ñòðîêè 9 ïîëó÷àåì ROW new( , ) ( )r Dist dist r
. Ýòî ïðîòèâîðå÷èò íàøåìó äîïóùåíèþ.
Óòâåðæäåíèå 2 äîêàçàíî.
Îñíîâíàÿ ïðîöåäóðà InsertNewArc. Ïðèâåäåì äèíàìè÷åñêóþ îáðàáîòêó
ïîäãðàôà êðàò÷àéøèõ ïóòåé ïîñëå äîáàâëåíèÿ ê èñõîäíîìó ãðàôó íîâîé äóãè.
procedure InsertNewArc(h,i,j: integer; v0: word(Dist);
var Weight,Cost: table; var G, SP: table; var Dist: table);
/* Äóãà ( , )i j âåñîì v0 äîáàâëÿåòñÿ â ãðàô G, h — ÷èñëî áèòîâ äëÿ
êîäèðîâàíèÿ áåñêîíå÷íîñòè. */
var v1,v2,v3: word(Dist);
v4: word(Weight);
k: integer;
X,Y,Y1,Z1,Z2: slice(G);
W1,W2,Queue: table;
1. Begin CLR(Z1); CLR(Y1);
2. CLEAR(h,Queue);
3. X := COL(i,G); X(j) := ' '1; COL(i,G) := X;
/* Äóãà ( , )i j äîáàâëÿåòñÿ â ãðàô G. */
4. v4:=ROW(j,Weight);
5. REP(1+(i –1)h,ih,v0,v4);
6. ROW(j,Weight) := v4;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 53
/* Âåñ äóãè ( , )i j äîáàâëÿåòñÿ â ìàòðèöó Weight. */
7. v4 := ROW(i,Cost);
8. REP(1+(j –1)h,jh,v0,v4);
9. ROW(i,Cost) := v4;
/* Âåñ äóãè ( , )i j äîáàâëÿåòñÿ â ìàòðèöó Cost. */
10. v1 := ROW(j,Dist); v2 := ROW(i,Dist);
/* Çäåñü v1 õðàíèò dist jold ( ) , à v2 õðàíèò dist iold ( ) .*/
11. v3 := ADD(v0,v1);
/* Çäåñü v3 — ðàññòîÿíèå îò âåðøèíû i äî ñòîêà, êîãäà ïóòü ïðîõîäèò
÷åðåç âåðøèíó j. */
12. if EQ(v3,v2) then
13. begin X := COL(i,SP); X(j) := ' '1 ;
14. COL(i,SP) := X;
/* Äóãà ( , )i j äîáàâëÿåòñÿ â ìàòðèöó SP. */
15. end;
16. if LESS(v3,v2) then
17. begin ROW(i,Dist) := v3; Z1(i) := ' '1 ;
/* Äëÿ âåðøèíû i â ìàòðèöå Queue óñòàíàâëèâàåòñÿ ìàêñèìàëüíûé
ïðèîðèòåò. */
18. end;
19. while SOME (Z1) do
20. begin MIN(Queue,Z1,Z2);
21. k := FND(Z2); Z1(k) := ' '0 ;
22. COL(k,SP) := Y1;
/* Èç ìàòðèöû SP óäàëÿþòñÿ âñå äóãè, âûõîäÿùèå èç k. */
23. UpdateOutgoingArcs(h,k,G,Weight,Dist,SP);
/* Â ìàòðèöó SP äîáàâëÿþòñÿ òå äóãè âèäà ( , )k l ,
äëÿ êîòîðûõ dist k wt k l dist l( ) ( , ) ( )
� . */
24. UpdateIncomingArcs(h,k,G,Cost,Y,Dist,SP);
25. v2:=ROW(i,Dist);
/* Ñòðîêà v2 õðàíèò òåêóùåå êðàò÷àéøåå ðàññòîÿíèå îò âåðøèíû i äî ñòîêà. */
26. SUBTC(Dist,Y,v2,W2);
/*  êàæäîé l-é ñòðîêå ìàòðèöû W2, îòìå÷åííîé ' '1 â ñëàéñå Y , õðàíèòñÿ
âåëè÷èíà dist(l) – dist(i). */
27. TMERGE(W2,Y,Queue);
/* Â ìàòðèöó Queue çàïèñûâàþòñÿ ïðèîðèòåòû äëÿ íîâûõ àôôåêòíûõ
âåðøèí. */
28. Z1 := Z1 or Y;
/* Íîâûå àôôåêòíûå âåðøèíû äîáàâëÿþòñÿ â ñëàéñ Z1. */
29. end;
30. End;
Òåîðåìà. Ïóñòü îðèåíòèðîâàííûé âçâåøåííûé ãðàô çàäàí â âèäå ìàòðèöû
ñìåæíîñòè G è ìàòðèöû âåñîâ Weight. Ïóñòü òàêæå çàäàíû ìàòðèöû Cost, SP è
Dist è ÷èñëî áèòîâ h äëÿ êîäèðîâàíèÿ áåñêîíå÷íîñòè. Ïóñòü äóãà ( , )i j äîáàâëÿåò-
ñÿ ê çàäàííîìó ãðàôó. Òîãäà ïîñëå âûïîëíåíèÿ ïðîöåäóðû InsertNewArc äóãà
( , )i j áóäåò äîáàâëåíà ê ìàòðèöå SP, à åå âåñ áóäåò âêëþ÷åí â ìàòðèöû Weight è
Cost. Êðîìå òîãî, ìàòðèöû Dist è SP áóäóò îáðàáîòàíû ñîãëàñíî àëãîðèòìàì A è Â.
Äîêàçàòåëüñòâî. Áóäåì äîêàçûâàòü èíäóêöèåé ïî ÷èñëó àôôåêòíûõ âåðøèí l,
êîòîðûå âêëþ÷àþòñÿ â ñòðîÿùååñÿ äåðåâî ñ êîðíåì i.
Áàçèñ èíäóêöèè ïðîâåðÿåì äëÿ ñëó÷àÿ l � 1, ò.å. â ãðàôå G íèêàêàÿ äóãà íå
çàõîäèò â âåðøèíó i.
Íåïîñðåäñòâåííî ïðîâåðÿåòñÿ, ÷òî ïîñëå âûïîëíåíèÿ ñòðîê 1–9 äóãà ( , )i j
äîáàâëÿåòñÿ â ìàòðèöó G, à åå âåñ — â ìàòðèöû Weight è Cost. Â ðåçóëüòàòå âû-
ïîëíåíèÿ ñòðîê 10 è 11 ïåðåìåííàÿ v3 áóäåò õðàíèòü íîâîå êðàò÷àéøåå ðàññòîÿ-
íèå îò âåðøèíû i äî ñòîêà, êîãäà ýòîò ïóòü ïðîõîäèò ÷åðåç âåðøèíó j.
54 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Òåïåðü ñðàâíèì íîâîå ðàññòîÿíèå îò âåðøèíû i äî ñòîêà ñ òåì ðàññòîÿíèåì,
êîòîðîå õðàíèòñÿ â ïåðåìåííîé v2. Åñëè v v3 2� , òî íè÷åãî íå íàäî ïåðåñ÷èòû-
âàòü. Ïîýòîìó ðàññìîòðèì ñëåäóþùèå äâà ñëó÷àÿ.
Ñëó÷àé 1. Ïóñòü v v3 2
. Òîãäà òåêóùåãî äåðåâà íåò. Ïîñëå âûïîëíåíèÿ
ñòðîê 13–15 ïîçèöèÿ äóãè ( , )i j äîáàâëÿåòñÿ â ìàòðèöó SP. Çàòåì ïåðåõîäèì ê âû-
ïîëíåíèþ ñòðîêè 19. Òàê êàê ïîñëå âûïîëíåíèÿ ñòðîêè 1 ñëàéñ Z1 ñîñòîèò èç íó-
ëåé è åãî ñîäåðæèìîå íå ìåíÿëîñü äî âûïîëíåíèÿ ñòðîêè 19, òî öèêë while
SOME(Z1) do (ñòðîêè 19–30) íå áóäåò âûïîëíÿòüñÿ. Ïîýòîìó ïîïàäàåì íà êîíåö
ïðîöåäóðû InsertNewArc.
Ñëó÷àé 2. Ïóñòü v v3 2� . Òîãäà äåðåâî ñîñòîèò èç åäèíñòâåííîé âåðøèíû i.
Ïîñëå âûïîëíåíèÿ ñòðîê 17 è 18 íîâîå êðàò÷àéøåå ðàññòîÿíèå îò âåðøèíû i äî
ñòîêà çàïèñûâàåòñÿ â i-þ ñòðîêó ìàòðèöû Dist è Z i1 1( ) ' '
. Ïîñëå ýòîãî âûïîëíÿåò-
ñÿ öèêë while doSOME( )Z1 (ñòðîêà 19). Íåïîñðåäñòâåííî ïðîâåðÿåòñÿ, ÷òî ïîñëå
âûïîëíåíèÿ ñòðîê 20 è 21 k i
è ñëàéñ Z1 ñîñòîèò èç íóëåé. Ïîñëå âûïîëíåíèÿ
ñòðîêè 22 i-é ñòîëáåö ìàòðèöû SP ñîñòîèò èç íóëåé ââèäó âûïîëíåíèÿ îïåðàöèè
CLR( )Y1 â ñòðîêå 1. Ïîýòîìó âñå äóãè, âûõîäÿùèå èç âåðøèíû i, óäàëÿþòñÿ èç
ìàòðèöû SP. Ïî óòâåðæäåíèþ 1 ïîñëå âûïîëíåíèÿ âñïîìîãàòåëüíîé ïðîöåäóðû
UpdateOutgoingArcs (ñòðîêà 23) â ìàòðèöó SP áóäóò äîáàâëåíû òå äóãè âèäà ( , )i l ,
äëÿ êîòîðûõ dist i wt i l dist l( ) ( , ) ( )
� .  ÷àñòíîñòè, äóãà ( , )i j áóäåò äîáàâëåíà â
ìàòðèöó SP, ïîñêîëüêó íîâîå ðàññòîÿíèå v3 ñîâïàäàåò ñ òåêóùèì êðàò÷àéøèì
ðàññòîÿíèåì îò âåðøèíû i äî ñòîêà, êîòîðîå çàïèñàíî â i-é ñòðîêå ìàòðèöû Dist.
Ïî ïðåäïîëîæåíèþ òîëüêî âåðøèíà i ÿâëÿåòñÿ àôôåêòíîé. Ïîýòîìó ïîñëå âû-
ïîëíåíèÿ âñïîìîãàòåëüíîé ïðîöåäóðû UpdateIncomingArcs (ñòðîêà 24) ðåçóëüòè-
ðóþùèé ñëàéñ Y áóäåò íóëåâûì. Ïîýòîìó ñòðîêè 27 è 28 íå áóäóò âûïîëíÿòüñÿ.
Òàê êàê ïîñëå âûïîëíåíèÿ ñòðîêè 29 ñëàéñ Z1 áóäåò íóëåâûì, ïîïàäàåì íà êîíåö
ïðîöåäóðû InsertNewArc.
Çíà÷èò, åñëè l
1 è v v3 2� , òî âíà÷àëå íîâîå êðàò÷àéøåå ðàññòîÿíèå v3 îò
âåðøèíû i äî ñòîêà çàïèñûâàåòñÿ â i-þ ñòðîêó ìàòðèöû Dist. Çàòåì èç ìàòðèöû
SP óäàëÿþòñÿ âñå äóãè, âûõîäÿùèå èç âåðøèíû i. Ïîñëå ýòîãî â SP äîáàâëÿþòñÿ
âñå äóãè âèäà ( , )i p , äëÿ êîòîðûõ dist i wt i p dist p( ) ( , ) ( )
� .
Øàã èíäóêöèè. Ïóñòü òåîðåìà âåðíà äëÿ ñëó÷àÿ, êîãäà èç òåêóùåãî äåðåâà
T óäàëÿåòñÿ íå áîëåå l âåðøèí. Äîêàæåì ñïðàâåäëèâîñòü óòâåðæäåíèÿ, êîãäà èç
òåêóùåãî äåðåâà áóäåò óäàëåíî l �1 àôôåêòíûõ âåðøèí.
Êàê è ïðè äîêàçàòåëüñòâå ñëó÷àÿ 2 áàçèñà èíäóêöèè, ïîñëå âûïîëíåíèÿ
ñòðîê 1–11 è 16–18 äóãà ( , )i j äîáàâëÿåòñÿ â ìàòðèöó G, à åå âåñ — â ìàòðèöû
Weight è Cost, ïåðåìåííàÿ v3 õðàíèò íîâîå êðàò÷àéøåå ðàññòîÿíèå îò âåðøèíû i
äî ñòîêà, çíà÷åíèå v3 çàïèñûâàåòñÿ â i-þ ñòðîêó ìàòðèöû Dist è äëÿ âåðøèíû i
óñòàíàâëèâàåòñÿ ìàêñèìàëüíûé ïðèîðèòåò â ìàòðèöå Queue.
Ïîñëå âûïîëíåíèÿ ñòðîê 20–22 ïîëó÷àåì, ÷òî k i
, Z1
� è èç ìàòðèöû SP
óäàëÿþòñÿ âñå äóãè, âûõîäÿùèå èç âåðøèíû i.
Ïî óòâåðæäåíèþ 1 ïîñëå âûïîëíåíèÿ âñïîìîãàòåëüíîé ïðîöåäóðû
UpdateOutgoingArcs (ñòðîêà 23) â ìàòðèöó SP äîáàâëÿþòñÿ òå äóãè âèäà ( , )i p ,
äëÿ êîòîðûõ dist i wt i p dist p( ) ( , ) ( )
� .
Ïî óòâåðæäåíèþ 2 ïîñëå âûïîëíåíèÿ âñïîìîãàòåëüíîé ïðîöåäóðû
UpdateIncomingArcs (ñòðîêà 24) ñëàéñ Y õðàíèò ãîëîâû òåõ äóã ( , )r i , äëÿ êîòîðûõ
dist r dist rnew old( ) ( )� , íîâûå ðàññòîÿíèÿ dist rnew ( ) çàïèñûâàþòñÿ â ìàòðèöó Dist è
äóãè âèäà ( , )r i , äëÿ êîòîðûõ dist r wt r i dist i( ) ( , ) ( )
� , äîáàâëÿþòñÿ â ìàòðèöó SP.
Ïîñëå âûïîëíåíèÿ ñòðîê 25–29 ïîëó÷àåì, ÷òî Z Y1
è ïðèîðèòåòû äëÿ íîâûõ
àôôåêòíûõ âåðøèí, îòìå÷åííûõ ‘1’ â ñëàéñå Y , çàïèñûâàþòñÿ â ìàòðèöó Queue.
Ïî èíäóêòèâíîìó ïðåäïîëîæåíèþ ïîñëå òîãî, êàê èç òåêóùåãî äåðåâà T áó-
äóò óäàëåíû ïåðâûå l àôôåêòíûõ âåðøèí, äëÿ êàæäîé àôôåêòíîé âåðøèíû r â ìàò-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 55
ðèöó SP áóäóò äîáàâëåíû äóãè âèäà ( , )p r , äëÿ êîòîðûõ dist p wt p r( ) ( , )
�
� dist r( ), è äóãè âèäà ( , )r q , äëÿ êîòîðûõ dist r wt r q dist q( ) ( , ) ( )
� , à â r-é ñòðîêå
ìàòðèöû Dist áóäåò çàïèñàíî íîâîå êðàò÷àéøåå ðàññòîÿíèå îò âåðøèíû r äî ñòî-
êà. Ïîñëå òîãî êàê â ìàòðèöå Queue áóäóò îáðàáîòàíû ïåðâûå l àôôåêòíûõ âåð-
øèí, â ñëàéñå Z1 îñòàíåòñÿ åäèíñòâåííûé áèò ‘1’, óêàçûâàþùèé ïîçèöèþ ( )l �1 -é
àôôåêòíîé âåðøèíû. Ïîñêîëüêó Z1 � �, îáðàáàòûâàåì ýòó àôôåêòíóþ âåðøèíó
êàê è ïðè äîêàçàòåëüñòâå áàçèñà èíäóêöèè. Òàê êàê Z1 ñòàíîâèòñÿ íóëåâûì ñëàé-
ñîì, ïåðåõîäèì íà êîíåö ïðîöåäóðû.
Òåîðåìà äîêàçàíà.
Îöåíèì âðåìÿ âûïîëíåíèÿ ïðîöåäóðû InsertNewArc. Ïóñòü h — ÷èñëî áèòîâ
äëÿ êîäèðîâàíèÿ áåñêîíå÷íîñòè, à k — ÷èñëî àôôåêòíûõ âåðøèí, êîòîðûå ïîÿâ-
ëÿþòñÿ ïîñëå äîáàâëåíèÿ äóãè ( , )i j ê ãðàôó G. Íåïîñðåäñòâåííî ïðîâåðÿåòñÿ, ÷òî
âñïîìîãàòåëüíûå ïðîöåäóðû UpdateOutgoingArcs è UpdateIncomingArcs, à òàêæå
âñå áàçîâûå ïðîöåäóðû, êîòîðûå èñïîëüçóþòñÿ â ïðîöåäóðå InsertNewArc, âû-
ïîëíÿþòñÿ çà âðåìÿ O h( ). Òàê êàê â ïðîöåäóðå InsertNewArc îñíîâíîé öèêë while
SOME(Z1) do (ñòðîêè 19–30) âûïîëíÿåòñÿ k ðàç, òî ýòà ïðîöåäóðà âûïîëíÿåòñÿ
ñ òðóäîåìêîñòüþ O hk( ).
Ñðàâíèì âûïîëíåíèå èíêðåìåíòàëüíîãî àëãîðèòìà Ðàìàëèíãàìà è åãî àññî-
öèàòèâíîé âåðñèè:
� àëãîðèòì Ðàìàëèíãàìà èñïîëüçóåò êó÷ó, ýëåìåíòàìè êîòîðîé ÿâëÿþòñÿ àô-
ôåêòíûå âåðøèíû ñ êëþ÷îì, à àññîöèàòèâíàÿ âåðñèÿ — ìàòðèöó Queue, êàæäàÿ
r-ÿ ñòðîêà êîòîðîé õðàíèò ðàññòîÿíèå îò âåðøèíû r äî âåðøèíû i;
� â àëãîðèòìå Ðàìàëèíãàìà äëÿ êàæäîé àôôåêòíîé âåðøèíû u èç SP G( ) ïî-
ñëåäîâàòåëüíî óäàëÿþòñÿ âñå äóãè âèäà ( , )u x . Â àññîöèàòèâíîé âåðñèè ïîçèöèè
òàêèõ äóã îäíîâðåìåííî óäàëÿþòñÿ èç SP G( );
� â àëãîðèòìå Ðàìàëèíãàìà äëÿ êàæäîé âåðøèíû x Succ u� ( ) äóãà ( , )u x äî-
áàâëÿåòñÿ â SP G( ) òîãäà è òîëüêî òîãäà, êîãäà âûïîëíÿåòñÿ ñîîòíîøåíèå
wt u x dist x dist u( , ) ( ) ( )�
. Â àññîöèàòèâíîé âåðñèè ïîçèöèè äóã, âûõîäÿùèõ èç
âåðøèíû u è óäîâëåòâîðÿþùèõ ýòîìó ñîîòíîøåíèþ, îäíîâðåìåííî äîáàâëÿþòñÿ
â ïîäãðàô êðàò÷àéøèõ ïóòåé SP G( );
� â àëãîðèòìå Ðàìàëèíãàìà êàæäàÿ âåðøèíà y Pred u� ( ) âêëþ÷àåòñÿ â êó÷ó
PriorityQueue òîãäà è òîëüêî òîãäà, êîãäà âûïîëíÿåòñÿ íåðàâåíñòâî wt y u( , ) �
� �dist u dist y( ) ( ). Â àññîöèàòèâíîé âåðñèè îäíîâðåìåííî îïðåäåëÿþòñÿ ãîëîâû
äóã, çàõîäÿùèõ â âåðøèíó u è óäîâëåòâîðÿþùèõ ýòîìó íåðàâåíñòâó. Òàêèå âåð-
øèíû îäíîâðåìåííî âêëþ÷àþòñÿ â ìíîæåñòâî àôôåêòíûõ âåðøèí, à èõ ïðèîðè-
òåòû îäíîâðåìåííî çàïèñûâàþòñÿ â ñîîòâåòñòâóþùèå ñòðîêè ìàòðèöû Queue;
� â àëãîðèòìå Ðàìàëèíãàìà äëÿ êàæäîé âåðøèíû y � Pred( )u äóãà ( , )y u äî-
áàâëÿåòñÿ â SP G( ) òîãäà è òîëüêî òîãäà, êîãäà âûïîëíÿåòñÿ ñîîòíîøåíèå
wt y u dist u dist y( , ) ( ) ( )�
. Â àññîöèàòèâíîé âåðñèè îäíîâðåìåííî îïðåäåëÿþòñÿ
ïîçèöèè äóã, çàõîäÿùèõ â âåðøèíó u è óäîâëåòâîðÿþùèõ ýòîìó ñîîòíîøåíèþ.
Ïîçèöèè ýòèõ äóã îäíîâðåìåííî äîáàâëÿþòñÿ â SP G( ).
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåíà ïðîñòàÿ è åñòåñòâåííàÿ ñòðóêòóðà äàííûõ, ïîçâîëÿþùàÿ ïîñòðîèòü
ýôôåêòèâíóþ ïàðàëëåëüíóþ ðåàëèçàöèþ èíêðåìåíòàëüíîãî àëãîðèòìà Ðàìà-
ëèíãàìà íà STAR-ìàøèíå, ñîäåðæàùåé íå áîëåå n ïðîöåññîðíûõ ýëåìåíòîâ.
Àññîöèàòèâíàÿ âåðñèÿ ýòîãî àëãîðèòìà îïèñàíà â âèäå ïðîöåäóðû
InsertNewArc, êîððåêòíîñòü êîòîðîé äîêàçàíà. Ïðîöåäóðà âûïîëíÿåòñÿ íà
STAR-ìàøèíå ñ òðóäîåìêîñòüþ O hk( ), ãäå h — ÷èñëî áèòîâ äëÿ êîäèðîâàíèÿ
áåñêîíå÷íîñòè, à k — ÷èñëî àôôåêòíûõ âåðøèí, äëÿ êîòîðûõ íàäî íàõîäèòü
56 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
íîâûå êðàò÷àéøèå ïóòè ê ñòîêó ïîñëå äîáàâëåíèÿ ê ãðàôó íîâîé äóãè. Ýòà
îöåíêà îïòèìàëüíà, ïîñêîëüêó ïàðàìåòð h íå ìåíÿåòñÿ ñ ðîñòîì k, à îáðàáàòû-
âàòü íàäî âñå àôôåêòíûå âåðøèíû. Èíêðåìåíòàëüíûé àëãîðèòì Ðàìàëèíãàìà
èñïîëüçóåò ñîâðåìåííóþ ñòðóêòóðó äàííûõ, íàçûâàåìóþ êó÷åé èëè î÷åðåäüþ
ñ ïðèîðèòåòàìè. Àññîöèàòèâíàÿ âåðñèÿ ýòîãî àëãîðèòìà ýôôåêòèâíî ìîäåëè-
ðóåò îáðàáîòêó î÷åðåäè ñ ïðèîðèòåòàìè íà STAR-ìàøèíå. Äëÿ ïîñòðîåíèÿ
ïðîöåäóðû InsertNewArc ïðèøëîñü ðàñøèðèòü ÿçûê STAR ïóòåì ââåäåíèÿ íî-
âûõ îïåðàöèé è ïðåäèêàòîâ äëÿ ïåðåìåííûõ òèïà word. Ïðèâåäåíû îñíîâíûå
äîñòîèíñòâà àññîöèàòèâíîé âåðñèè èíêðåìåíòàëüíîãî àëãîðèòìà Ðàìàëèíãàìà.
Ïëàíèðóåòñÿ ïîñòðîèòü àññîöèàòèâíóþ âåðñèþ àëãîðèòìà Ôðèãèîíè è
Èòàëüÿíî [14] äëÿ îáðàáîòêè ïëàíàðíîãî ãðàôà ïîñëå äèíàìè÷åñêîãî âêëþ÷åíèÿ
èëè âûêëþ÷åíèÿ íåêîòîðûõ åãî âåðøèí.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. R a m a l i n g a m G . Bounded incremental computation // Lecture Notes in Computer Sciences. —
Heidelberg: Springer. — 1996. — 1089. — 190 p.
2. R a m a l i n g a m G . , R e p s T . An incremental algorithm for a generalization of the shortest
paths problem // J. of Algorithms, Academic Press. — 1996. — 21. — P. 267–305.
3. F r i g i o n i D . , M a r c h e t t i - S p a c c a m e l a A . , N a n n i U . Semi-dynamic algorithms for
maintaining single source shortest paths trees // Algorithmica. — 1998. — 25. — P. 250–274.
4. F r i g i o n i D . , M a r c h e t t i - S p a c c a m e l a A . , N a n n i U . Fully dynamic algorithms for
maintaining shortest paths trees // J. of Algorithms. Academic Press. — 2000. — 34. — P. 351–381.
5. F r i g i o n i D . , M a r c h e t t i - S p a c c a m e l a A . , N a n n i U . Fully dynamic shortest paths in
digraphs with arbitrary arc weights // J. of Algorithms. Elsevier Science. — 2003. — 49.
— P. 86–113.
6. D i j k s t r a E . W . A note on two problems in connection with graphs // Numerische Mathematik.
— 1959. — N 1. — P. 269–271.
7. N a r v ’ a e z P . , S i u K . - Y . , T z e n g H . - Y . New dynamic algorithms for shortest paths tree
computation // IEEE/ACM Trans. Networking. — 2000. — 8. — P. 734–746.
8. N e p o m n i a s c h a y a A . S . Language STAR for associative and parallel computation with verti-
cal data processing // Proc. of the Intern. Conf. Parallel Computing Technologies. — Singapore:
World Scientific, 1991. — P. 258–265.
9. Í å ï î ì í ÿ ù à ÿ À . Ø . , Â ë à ä û ê î Ì . À . Ñðàâíåíèå ìîäåëåé àññîöèàòèâíîãî
âû÷èñëåíèÿ // Ïðîãðàììèðîâàíèå. — 1997. — ¹ 6. — C. 41–50.
10. P o t t e r J . L . Associative computing: a programming paradigm for massively parallel computers.
Kent State University. — New York; London: Plenum Press, 1992. — 286 p.
11. N e p o m n i a s c h a y a A . S . Solution of path problems using associative parallel processors // In-
tern. Conf. on Parallel and Distributed Systems, ICPADS’97. — New York: IEEE Computer Society
Press, 1997. — P. 610–617.
12. N e p o m n i a s c h a y a A . S . , D v o s k i n a M . A . A simple implementation of Dijkstra’s
shortest path algorithm on associative parallel processors // Fundamenta Informaticae. — Amster-
dam: IOS Press. — 2000. — 43. — P. 227–243.
13. Ô î ñ ò å ð Ê . Àññîöèàòèâíûå ïàðàëëåëüíûå ïðîöåññîðû. — Ì.: Ýíåðãîèçäàò / Ïåð. ñ àíãë.,
1981. — 240 ñ.
14. F r i g i o n i D . , I t a l i a n o G . F . Dynamically switching vertices in planar graphs //
Algorithmica. — 2000. — 28, N 1. — P. 76–106.
Ïîñòóïèëà 18.07.2009
Ïîñëå äîðàáîòêè 20.01.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 57
|