2 BEGIN
3
FOR Р(х[1],..., x[k-l], у) болатын y
∈
A
k
үшін DO
4 BEGIN
X[k]:=y;
5
IF x[l], ..., X[k] бүтін санды шешім бар
6 THEN
write(X[l],....
X[k]);
7 AP(k+l)
8 END
9 END;
G = графында гамильтон циклін табу үшін қайтымды
алгоритмді қолданайық. Мұндай циклдердің әрқайсысын x
1
= x
n+1
=
V
0
болатын, мұндағы
V
0
–
графтың қандай да бір орнатылған шыңы және 1 < i < j
< n үшін x
i
x
j
болатын < x
1
, x
2
,
...,x
n+1
> тізбегі түрінде көрсетуге болады.
Осыған сәйкес А
k
= V болады.
≠
G = графын ТІЗІМ[v], v
∈
V инциденттілік тізімдерімен
көрсетейік. Онда < x
1
,...,x
k-1
> тізбегінің кеңейтулері болып келетін барлық
гамильтон циклдерін табатын процедура
1 PROCEDURE
гамильт(К); { Х массивы - глобалды}
2 BEGIN
3 FOR
у
∈
ТІЗІМ[x[k-1]] DO
4
IF(k = n+1) and (y = v0)
5
THEN write(x[l],..., x[n], v0)
6
ELSE IF DOP[y] THEN
7 BEGIN
8
x[k] := y; DOP[y] := false;
9 гамильт(к+1);
10
DOP[y] := true
11 END
12 END;
Негізгі бағдарлама:
BEGIN
FOR v
∈
V DO DOP[v] := true; { инициализациялау }
X[1] := v0; {v0 – графтың ерікті орнатылған шыңы }
DOP[v0]:- false;
гамильт(2)
END.
Көптеген қосымшалар үшін қайтымды алгоритмнің қадам саны толық
қарастыруға қарағанда аз болса да, мәселе көлемділігінің өсу экспонентасы
бойынша өседі. Бұл барлық шешімдерді емес, бір ғана шешімді іздеген кезде
де дұрыс болады.
8.8 Графтан ең қысқа жолдар табу
Доғаларына салмақ қосылған G = графтарын қарастыратын
боламыз. Бұл әрбір (u, v)
∈
E доғасына сәйкестікпен қандай да бір доға
салмағы деп аталатын a(u, v) нақты саны берілген. a(u, v)= , егер (u, v)
∞
доғасы болмаса. Егер шыңдардың
тізбегі G графындағы жолдарды
көрсетсе, онда оның ұзындығы
ретінде анықталады. Бізді
қызықтыратын - s, t
∈
V екі шыңның арасындағы ең қысқа жолды табу.
Ондай жолдың ұзындығын d(s, t) деп белгілеп, s-тен t-ға дейінгі
арақашықтық деп атаймыз (осылай анықталған арақашықтық теріс болуы да
мүмкін). Егер s-тен t-ға баратын бір де жол болмаса, онда d(s, t) =
p
v
v
v
,...,
,
1
0
∑
=
−
P
i
i
i
v
v
a
1
1
)
,
(
∞
деп
болжаймыз. Егер біздің графтың әрбір контуры оң ұзындыққа ие болса, онда
ең қысқа жол әрқашан элементарлы жол болып табылады. Практикалық
келтіру:
1) шыңдар - қалалар, доғалар – ұзындықтары салмақпен берілген қала
арасындағы жолдар. Қалалар арасындағы ең қысқа жолды іздейміз;
2) доға салмағы – шыңдар арасында ақпаратты жіберу бағасы (немесе
уақыты). Онда ақпаратты жіберудің ең арзанын (ең тезін) іздейміз.
Біз жолдарды емес, шыңдар арасындағы арақашықтықты табудың
алгоритмін қарастырамыз. Алайда, барлық контурлардың оң ұзындықтарын
біле отырып, ең қысқа жолдарды оңай табуға болады.
Шындығында, ерікті s, t
∈
V (s
≠
t) үшін d(s, t) = d(s, v) + d(v, t) болатын
v шыңы болады.
Мұндай қасиетке s-тен t-ға апаратын ең қысқа жолдардың соңғының
алдындағы шыңдар ие . Әрі қарай біз сол үшін d(s, v) = d(s, u) + d(u, v)
болатын u шыңын таба аламыз т.с.с. Барлық контурлардың ұзындықтары оң
болу шартынан шығатыны - t, v, u,... тізбегінде қайталану болмайтындығы
және s шыңымен аяқталатындығы. Шыңдарды кері қарай атап шығып, s-тен
t-ға апаратын қысқа жолды табамыз.
Ең қысқа жолды табу алгоритмін t, v, u, ..., s шыңдарын ретпен
орналастырылатын стекті қолдану арқылы құруға болады:
1 BEGIN
2
СТЕК :=
∅
; СТЕК <= t; v := t;
3 WHILE
v
≠
s DO
4 BEGIN
5
u := d[v] = d[u] + a[u, v] болатын шың
6
СТЕК <= u;
7 v
:=u
8 END
9
END
Егер 5-жолдағы шыңды таңдау барлық шыңдарды қарап шығудың
нәтижесінде болса, онда біздің алгоритмнің күрделілігі O(n
2
) болады. Егер
тек қана АЛДЫҢҒЫ[v] тізімінің құрамындағы u-^v болатын барлық u
шыңдарын қарастыратын болсақ, онда күрделілігі 0(т) болады.
8.9 Орнатылған шыңнан өткізілген ең қысқа
жолдар
Екі орнатылған s және t шыңдарының арасындағы арақашықтықты
табатын алгоритмдердің көбінің мәні келесіде.
При данной матрице весов дуг Доғалар салмақтарының a[u, v], u, v
∈
V
матрицалары берілген кезде s шыңынан барлық v
∈
V дейінгі
арақашықтықтарға салынған қандай да бір d[v] жоғарғы шектеулерді
есептейміз.
D[u]+a[u, v]D[v] := D[u]+a[u, v]. Процесс шектеулердің біреуін де әрі қарай жақсарьуға
келмейтін жағдайда тоқтайды. Әрбір D[v] айнымалысының мәні бұл
жағдайда s-тен v-ға бағытталған ең қысқа жолға тең.
Сөйтіп s-тен t-ға дейінгі арақашықтықты есептеу үшін біз s-тен грфтың
барлық шыңдарына дейінгі арақашықтықты табамыз. Осы принципті
қолданатын алгоритмнен эффективтірек ешқандай алгоритм табылмаған.
Алгоритмнің эффективтілігіне (1) шартын тексеруге қолданылатын u, v
шыңдары қандай ретпен алынатындығы үлкен ықпалын тигізетіні айта
кетейік.
Қандай да бір орнатылған s шыңынан графтың басқа шыңдарына
дейінгі арақашықтықты анықтайтын жалпы алгоритмді қарастырайық.
Әдетте бұл алгоритмді Форд-Беллман алгоритмі деп атайды. Алгоритмнің
жұмысы кезінде графта ұзындығы теріс мәнді контурлар жоқ деп болжанады.
1 BEGIN
2 FOR
v
∈
V DO D[v] := a[s, v]; D[s]:= 0;
3
FOR k := 1 TO n-2 DO
4 FOR
v
∈
V \ {s} DO
5 FOR
u
∈
V DO D[v] := min(D[v], D[u]+a[u, v])
6
END;
Алгоритм күрделілігі 0(п
3
) екендігі анық. Іс жүзінде есептеуді 4-
циклдің орындалуы D[v], v
∈
V айнымалыларында ешқандай өзгеріс
тудырмаған жағдайда аяқтауға болады. Бұл kмүмкін, алайда алгоритмнің мұндай модификациясы күрделілігін
өзгертпейді. (m«n
2
) сирек графтары үшін графты АЛДЫҢҒЫ[v], v
∈
V
инциденттілік тізімдермен көрсеткен қолайлы. Бұл жағдайда 5-жолды
FOR u
∈
АЛДЫҢҒЫ [v] DO D[v] := min(D[v], D[u]+a[u, v])
алмастырамыз. Күрделілігі O(n*m) болатын алгоритм аламыз. 32-суретте
Форд-Беллман алгоритмінің жұмысын бейнелейтін мысал көрсетілген.
Мұнда 4,5-циклдер шыңдар номерінің өсу ретімен орындалады.
Достарыңызбен бөлісу: |
