Algorytm wstawiania najbliższego miasta, Studia, Stopień 2 Semestr II, Badania operacyjne, Badania op, Badania ...
[ Pobierz całość w formacie PDF ]
Algorytmwstawianianajbli»szego
miasta
Wtrakcierealizacjialgorytmudopuszczamydorozwa»a«cyklezawieraj¡cejedenlubdwawierz-
chołki.
Dane:
Pełnygrafwa»ony(
K
n
,w
).
Wynik:
CyklHamiltona
H
zawieraj¡cywszystkiewierzchołkigrafu
K
n
.
START
1.Wybierzwierzchołek
v
2
V
(
K
n
)izbudujcykl
C
zło»onyztegowierzchołka;
2.Dopóki
V
(
K
n
)
\
V
(
C
)
6
=
;
wykonuj
znajd¹par¦wierzchołków(
u
0
,v
0
)
2
V
(
C
)
×
(
V
(
K
n
)
\
V
(
C
)),dlaktórejspełniona
jestrówno±¢
w
(
u
0
,v
0
)=min
{
w
(
u,v
):(
u,v
)
2
V
(
C
)
×
(
V
(
K
n
)
\
V
(
C
))
}
;
dlawierzchołków
u
−
1
,
u
1
s¡siaduj¡cychwcyklu
C
zwierzchołkiem
u
0
wybierz
ten,dlaktóregoliczba
w
(
u
i
,v
0
)+
w
(
v
0
,u
0
)
−
w
(
u
0
,u
i
),
i
2{−
1
,
1
}
jestmniejsza
(je»eliobieobliczoneliczbys¡równe,wybierzdowolnyzdwóchbadanychwierz-
chołków);wstawwierzchołek
v
0
docyklu
C
pomi¦dzywybranywierzchołek
u
i
oraz
wierzchołek
u
0
;
3.Przyjmij
H
:=
C
.
STOP
Twierdzenie1.
Niech
(
K
n
,w
)
b¦dziepełnymgrafemwa»onymspełniaj¡cymwarunektrójk¡ta.
Je»eliHjestrozwi¡zaniemproblemukomiwoja»eradlategografu,aH
jestcyklemotrzymanym
zapomoc¡powy»szegoalgorytmu,to
w
(
H
)
¬
2
w
(
H
)
.
1
[ Pobierz całość w formacie PDF ]