Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
8
ROZDZIAŁ10WPROWADZENIE
wtakisposób,żebystarczyłodopierwszegoiwkażdymztychprzy-
kładówmamydoczynieniazprocesemoptymalizacji,chociażróżnesą
problemyikryteriaoptymalizacjiiOczywiście,jeślimożliwychwarian-
tówjestniewielemożnakażdyznichsprawdzićiwybraćnajlepszyze
względunaprzyjętekryteriaiJednymzklasycznychproblemówopty-
malizacyjnychjestproblemkomiwojażera,którywyjeżdżazpewnego
miasta,odwiedzatylkorazwszystkiemiastajakiezaplanowałiwra-
cadotego,zktóregorozpocząłpodróżiNależyzminimalizowaćczas
przejazdu(bądźkosztczypokonanąodległość)iwzadaniusymetrycz-
nymczasprzejazdu(koszt,odległość)jesttakisamwjednąidrugą
stronę,czylizmiastaAdomiastaBjedziemytaksamodługo,jak
zmiastaBdoAiMimożeproblemwydajesięprosty,toilośćmoż-
liwychmarszrutwynosi
(n11)!
2
,codaje12marszrutdla
n=5
miast,
181440dla10i60822550204416000dla20iRozwiązanieproblemu
komiwojażeradla16miastwojewódzkichwPolscewymagałobyprze-
analizowania653837184000możliwychwariantów(rysi1i1)iObecny
rekordtorozwiązaniezadaniakomiwojażerawzastosowaniachVLSI
w2006ridla
n=85900.
Podobnierzeczsięma,gdymamypracowni-
Tabela1i1lRozwiązaniaproblemukomiwojażeraI3I
rozwiązanie
czasCPU
data
n
problem
optymalne
[
s
]
[
TPSunit
]
25XII1999
2103
owierceniaPCB
80450
11179253
29I2000
5915
owierceniaPCB
565530
2301520
27II2000
7397
PLAdlaAT&T
23260728
423787
28IX199911849
owierceniaPCB
923288
13094345
8V199813509
miastawUSA
19982859131052087
20IV200115112miastaniemieckie
∼
=
66000km
1573084712713600
V200424978miastawSzwecji
∼
=
72500km
855597
200685900
projektVLSI
142382641
