No label defined (Q3771995)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4031431
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4031431 |
Statements
1987
0 references
optimal travelling salesman tours
0 references
optimality preserving transformations
0 references
contraction
0 references
vertex elimination
0 references
expansion
0 references
vertex addition
0 references
heuristics
0 references
0.7708340287208557
0 references
0.7708339095115662
0 references
0.767073392868042
0 references
0.7637174129486084
0 references
0.7506983876228333
0 references
[For the entire collection see Zbl 0627.00024.] Bei einer optimalen Travelling-Salesman-Tour werden bei zwei Transformationen des Datensatzes die Bedingungen untersucht, unter denen die Optimalität der Rundreise erhalten bleibt. Unter den Knoten des Datensatzes wird ein Knoten der optimalen Tour gestrichen (Kontraktion), und zu den n Knoten des Datensatzes wird ein zusätzlicher Knoten hinzugefügt (Expansion). Diese Art der Untersuchung erstreckt sich auf symmetrische Distanzmatrizen, wobei abstrakte Datensätze und euklidische Datensätze betrachtet werden. Im euklidischen Fall werden allgemeine Aussagen zur Gestalt der optimalen Tour und eine schnelle Heuristik hergeleitet.
0 references