1 BEGIN
2 FOR v
∈
V DO WGN[r] := 0; num := 0; { инициализациялау }
3 d := 0; СТЕК[0] := 0; {d – стектегі элемент саны }
4 FOR r
∈
V DO
5 IF WGN[r] = 0 THEN цикл(v)
6 END.
Алгоритмнің есептелу күрделілігін бағалайық. Қадамдардың жалпы
саны, циклдердің есептеулерін санамастан, тереңдікке іздеуге негізделген
барлық алгоритмдердей 0(n+m) ретіне ие. Бұған барлық циклдердің
ұзындықтарының қосындысын қосу керек. Бұл ұзындық (m-n+1) аспайды, ол
алгоритмдердің 0(nm+n) (немесе 0(nm), егер m=0 болатын жағдайды есепке
алмасақ) қосындыларын береді.
8.6 Гафтағы Эйлер жолдары
Графтағы Эйлер жолы — графтың әрбір қабырғасы арқылы бір рет
өтетін, яғни қандай да бір і үшін {ν
i
,ν
i+1
} сияқты әрбір e
∈
E қабырғасы бір рет
қана шығатын V
1
,..., V
m+1
жол. Егер ν
1
= ν
m+1
, ондай жол эйлер циклі деп
аталады.
Эйлер жолының жеткілікті және керек шарты: графтағы Эйлер
жолы тек граф байланысты болса және тақ дәрежелі екі шыңы ғана болса
ғана орынды.
Егер графта тақ дәрежелі шың болмаса, онда әрбір эйлер жолы
эйлер циклі болып табылады.
G = - ТІЗІМ[r], v
∈
V тізімдерімен берілген байланысты
граф болсын. Графтан эйлер циклін табу алгоритмін былай құрайық. Екі
СТЕК1 пен СТЕК2 стектерін пайдаланайық.
Графтың ерікті ν
0
шыңын таңдайық және сол шыңнан кезекті жол
құрайық. Бұл жолдың шыңдарын СТЕК1-ге орналастырамыз, ал
қабырғаларды графтан жоямыз. Бұл әрекеттерді жолды ұзарту үшін жаңа
шың қоса алмайтын жағдайға жеткенімізше қайталаймыз. Яғни ТІЗІМ[v]=
∅
.
Онда ν = ν
0
болу керек, әйтпесе бұл ν шыңы – тақ дәрежелі екендігін
білдіруші еді. Сөйтіп, біздің графтан цикл жойылады, ал ол стектің шыңдары
СТЕК1-де орналасады. Осындай әдіспен модификацияланған графта ерікті
шыңның дәрежесі жұп болып қалады. ν = ν
0
шыңы СТЕК1-ден СТЕК2-ге
көшіріледі, ал процесс СТЕК1-гі (егер тізімі бос болмаса) жоғарғы шыңнан
бастап қайталанады. Енді СТЕК1-ге осы шың арқылы өтетін цикл тағы да
орналастырылады, т.с.с. Процесс СТЕК1 босап қалғанша қайталанады.
СТЕК2-ге орналастырылған шыңдар қандай да бір жолды
құрайтыны анық. ν шыңы ТІЗІМ[ν]
≠
∅
болғанда ғана СТЕК2-ге көшіріледі,
яғни бұл шыңға инцидентті барлық қабырғалар СТЕК1-де көрсетілсе
(көршілес шыңдармен жұп құрып).
Осыдан алгоритм аяқталған кезде СТЕК2-де эйлер циклі болатындығы
шығады.
Алгоритм
1 Begin
2 СТЕК1:=
∅
; СТЕК2:=
∅
3 v:= графтың ерікті шыңы
4 СТЕК <= v;
5 WHILE СТЕК1 =
∅
do BEGIN
6 v:= top(СТЕК1);
7 IF ТІЗІМ =
∅
8 THEN BEGIN
8.7 Қайтымды алгоритмдер
Енді графтың әрбір шыңы арқылы (қабырғасы арқылы емес) өтетін
жолдарды табу мәселесін қарастырайық. Мұндай қасиеті бар жол гамильтон
жолы деп аталады, ал цикл - гамильтон циклі деп аталады. Графтағы
гамильтон жолы мен ондай жол жоқ графтың мысалдары 31-суретте
көрсетілген. Мәселелердің ұқастығына қарамастан, оларды шешу жолдары
әртүрлі.
а) Графтағы Гамильтон жолы б) Гамильтон жолы жоқ
31-сур. рафтың түрлері
Эйлер жолдарынан айырмашылығы - өмір сүрудің керекті және
жеткілікті шарттары белгісіз. Сонымен бірге ерікті графтағы гамильтон
жолының бар-жоғын n-нен (графтағы шыңдар саны) басталатын жиынтықпен
шектелген қадам саны арқылы тексеретін алгоритм де белгісіз.
Графтағы гамильтон жолын табудың алгоритмі болып барлық
мүмкіндіктерді қарастыру табылады: шыңдардың барлық түрлі n! Шыңдарды
генерациялаймыз, әрқайсысы үшін ол гамильтон жолын таба алатындығын
тексереміз. Мұндай әрекеттер тым болмаса n!n қадамды керек етеді, ал
мұндай функция ерікті көпмүшеліктен де, тіпті а
n
(а>1) түріндегі
экспоненциалды функциядан да тезірек өседі.
Алайда толық қарап шығу текті алгоритмдердегі қадам санын
азайтатын жалпы әдіс бар. Бұл әдісті қолдану үшін ізделінетін шешу < x
1
,...,
x
n
> тізбегі түрінде болу керек. Әдіс идеясы келесіде.
Шешуімізді бос тізбектен, яғни ұзындығы 0 болатын тізбектен
бастаймыз. Қандай да бір < x
1
,..., x
i
> шешуі болған кезде x
i+1
-дің <
x
1
,...,.x
i
,x
i+1
> (мүмкін < x
1
,...,.x
i
,x
i+1
> өзі шешім болатын шығар) қандай да бір
мәнге дейін кеңейтуге болатындығын бірден айта алмайтын мәнін табу
керек. Егер де осындай болжанған, бірақ қолданылмаған x
i+1
мәні болса, онда
оны біз шешуімізге қосып, < x
1
,...,.x
i
,x
i+1
> тізбегі үшін процесті
жалғастырамыз . Егер ол болмаса, онда < x
1
,...,x
i-1
> шешіміне оралып,
процесті жаңа, бірақ әлі қолданылмаған x
i
мәнін іздеп жалғастырамыз.
Мұндай алгоритмдер қайтымды алгоритмдер (backtracking) деп аталады.
Нақтырақ айтқанда, әрбір k > 0 үшін ішінен бөліктік шешімнің k-ші
координатасы үшін талапкерлерді таңдайтын қандай да бір А
k
жиынтығы бар.
Біздің мәселеміздің әрбір бүтін санды < x
1
,...,x
n
> шешімі үшін және әрбір
kk
жиынтығында х^ элементі болу керек (іс жүзінде А
k
құрамында
бүтін санды шешімдерінің k-ші координатасында шығатын «артық»
элементтері болу мүмкін).
Сонымен қоса, < x
1
,...,x
i
> бөліктік шешімге сәйкестікке Р< x
1
,...,x
i
>
қояды, егер < x
1
,...,x
i
> тізбегін шешімге дейін кеңейтуге болмаса false,
және Р< x
1
,...,x
i
>
= егер x
i
мәні < x
1
,...,x
i-1
>. бөліктік шешіміне жіберілсе
true. Бұл < x
1
,...,x
i-1
> міндетті түрде толық шешімге дейін кеңейтілетіндігін
білдірмейді.
Бұл процесті алгоритмнің келесі схемасы түрінде жазуға болады
BEGIN k:=l;
WHILE k > 0 DO
IF әлі қолданылмаған Р(х[1],..., x[k-l], у) болатын у А
k
элементі
болса,
∈
THEN
BEGIN
x[k] := у; {у элементі қолданылған} IF
бүтін санды шешім
THEN write(x[l],..., x[k]);
k:=k+l;
END ELSE {неғұрлым қысқа
бөліктік шешімге қайтып келу;
A
k
жиынтығының барлық элементтері қайтадан
қолданылмаған болып қалады }
k:=k-1
END.
Бұл алгоритм барлық шешімдерін A
K
жиынтықтары – аяқталатын және
x
1
A
1, …,
x
n
∈
A
n
үшін P< x
1
,...,x
i
> = false болатын n бар деген болжамнан
табатын болады. Соңғы шарт барлық шешімдердің ұзындығы n-нен кем
болатындығын көрсетеді. Жалпы қасиетін көрсетуге болады.
∈
S > 0 және < x
1
,...,x
s-1
> - алгоритммен құрылған қандай да бір бөліктік
шешім болсын. Онда k = s, X[i] = X
i
, 1 < i ^ s болатын 3-циклдің
итерациясынан бастап, алгоритм < x
1
,...,x
s-1
> тізбегінің кеңейтілуі болып
келетін барлық бүтін санды шешімдерді генерациялайды және k = s – 1
болатын қалыпқа келеді.
Соңғы қасиет қайтымды алгоритмнің рекурсивті нұсқасына әкеліп
соқтырады.
1
PROCEDURE AP(k);
{ Х[1],..., X[k-l] тізбегінің кеңейтілуі болып келетін барлық
шешімдерді генерациялау; Х массиві - глобалды}
Достарыңызбен бөлісу: |
