Дискретная математика: Основы теории графов и алгоритмизация задач. Прокушев Л.А. - 42 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

42
Ïðèíöèïû ïîñòðîåíèÿ ìàøèííîãî àëãîðèòìà ïîèñêà òðàíçèòèâíîãî
è îáðàòíîãî òðàíçèòèâíîãî çàìûêàíèé ðàññìîòðèì íà ïðèìåðå ïîëó÷å-
íèÿ
ˆ
Ã
B è
ˆ
Ã
B íà îñíîâå àíàëèçà ìàòðèöû ñìåæíîñòè ãðàôà (ðèñ. 2.5,á).
Ñïðàâà îò ìàòðèöû ñìåæíîñòè S íàõîäèòñÿ âåêòîð-ñòîëáåö äëÿ
ˆ
ÃÂ
,
à âíèçó âåêòîð-ñòðîêà äëÿ
ˆ
ÃÂ
−
. Ðàññìîòðèì ïîðÿäîê çàïîëíåíèÿ ñòîë-
áöà
ˆ
ÃÂ
.
1. Â ïîçèöèþ Â ñòîëáöà
ˆ
ÃÂ
çàïèñûâàåì íîëü (íà÷àëüíàÿ âåðøèíà).
2. Â ñòðîêå Â ìàòðèöû S åäèíèöà íàõîäèòñÿ â ïîçèöèÿõ, ñîîòâåò-
ñòâóþùèõ âåðøèíàì, â êîòîðûå åñòü ïóòü äëèíû 1, ïîýòîìó â ïîçèöèþ
D ñòîëáöà
ˆ
ÃÂ
çàïèñûâàåì 1.
3. Ñòðîêà D ìàòðèöû ñîäåðæèò 1 â ñòîëáöàõ, ñîîòâåòñòâóþùèõ âåð-
øèíàì, êîòîðûå îòñòîÿò â ãðàôå îò âåðøèíû D íà îäíó äóãó, à çíà÷èò,
êðàò÷àéøèé ïóòü äî íèõ îò âåðøèíû  ðàâåí 2 äóãàì.
Åñëè â êëåòêàõ ñòîëáöà
ˆ
ÃÂ
, ñîîòâåòñòâóþùèõ åäèíè÷íûì ïîçèöèÿì
ñòîëáöîâ â ñòðîêå D ìàòðèöû, óæå íàõîäÿòñÿ ÷èñëà, òî îíè íå ìåíÿþòñÿ
(Â, D), à â ïóñòûå êëåòêè Ñ è Å çàïèñûâàåì 2. Òåì ñàìûì èñêëþ÷àþòñÿ
ïåòëè (íàïðèìåð, â âåðøèíå D) è êîíòóðû (íàïðèìåð, äóãà (D,B)), è
ïðîäîëæàåòñÿ ðîñò äåðåâà êðàò÷àéøèõ ïóòåé îò âåðøèíû Â.
4. Ïîâòîðÿåì ï. 3 äëÿ âåðøèí Ñ, Å è äðóãèõ, óâåëè÷èâàÿ äëèíó ïóòè
íà 1, äî òåõ ïîð, ïîêà ýòî âîçìîæíî.
Àíàëîãè÷íî äåéñòâóåì äëÿ ïîëó÷åíèÿ
ˆ
ÃÂ
−
, íî ïðè ýòîì íåîáõîäèìî
òðàíñïîíèðîâàòü ìàòðèöó ñìåæíîñòè (ïîìåíÿòü ñòðîêè è ñòîëáöû ìåñ-
òàìè) è èñïîëüçîâàòü ðàññìîòðåííûé àëãîðèòì èëè âûïîëíÿòü àíàëèç
èñõîäíîé ìàòðèöû ïî ñòîëáöàì. ×èñëà, ïîëó÷åííûå â ñòðîêå
ˆ
ÃÂ
−
, äàþò
ìèíèìàëüíûå äëèíû ïóòåé (÷èñëà äóã) èç òåõ âåðøèí, èç êîòîðûõ ìîæ-
íî ïîïàñòü â âåðøèíó B, íàïðèìåð èç âåðøèíû Å íåëüçÿ ïîïàñòü â Â
íèêàêèì ïóòåì.
2.3.2. Îïèñàíèå àëãîðèòìà ïîèñêà òðàíçèòèâíîãî çàìûêàíèÿ
Ìàøèííûé àëãîðèòì äîëæåí îáåñïå÷èâàòü ïîèñê òðàíçèòèâíîãî çà-
ìûêàíèÿ (âåêòîð Z) äëÿ ëþáîé íà÷àëüíîé âåðøèíû (Ê) ãðàôà. Âîçìîæ-
íûé âàðèàíò àëãîðèòìà ìîæåò âêëþ÷àòü ñëåäóþùèå îñíîâíûå øàãè.
1. Ââîä ìàòðèöû ñìåæíîñòè S, åå ðàçìåðà (n) è íîìåðà íà÷àëüíîé
âåðøèíû (k).
2. Óñòàíîâêà íà÷àëüíîãî çíà÷åíèÿ âåêòîðà Z â öèêëå (i=1(l)n, Z
i
= 1).
3. Óñòàíîâêà Z
k
=0 (íà÷àëüíàÿ âåðøèíà), L=0 (ñ÷åò÷èê äëèíû ïóòè).
4. Öèêë àíàëèçà íåîáðàáîòàííûõ âåðøèí:

Страницы