Citation
Evaluation of traveling salesperson problem algorithms

Material Information

Title:
Evaluation of traveling salesperson problem algorithms
Creator:
Chau, Trang Duyen
Publication Date:
Language:
English
Physical Description:
69 leaves : ; 28 cm

Subjects

Subjects / Keywords:
Traveling salesman problem ( lcsh )
Algorithms ( lcsh )
Algorithms ( fast )
Traveling salesman problem ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 67-69).
Statement of Responsibility:
by Trang Duyen Chau.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
51820554 ( OCLC )
ocm51820554
Classification:
LD1190.E52 2002m .C42 ( lcc )

Downloads

This item is only available as the following downloads:


Full Text

PAGE 3

n

PAGE 10

n i toj n n {(G,C,K) V x V

PAGE 11

K C=[c;J n. n,

PAGE 12

"Del' Handlungsreisende, wie el' sein soil und was er zu thun hat, um AUftriige zu erhalten und eines gliicklichen Elfolgs in seinen Geschifften gewiss zu sein. Von einem alten CommisVoyaeur"

PAGE 13

NP-Complete

PAGE 14

G=(v,E) V arc e E e=(iJ) i e. path {e] e p-l, ek+l circuit {e] e e] e elementary cycle i i, i Hamiltonian Cycle e=(i,j) E lij

PAGE 15

i lij. directed graph Hamiltonian cycle n n?" Hamiltonian Cycle problem [5]

PAGE 16

E) '=(v, E E' D, D E Hamiltonian path G=(v, E) connected spanning tree

PAGE 17

complete graph n. weight optimal Hamilton Cycle minimum weight

PAGE 19

n

PAGE 20

R

PAGE 22

(i, j)

PAGE 27

n,

PAGE 28

i n

PAGE 29

Optimal solution. n r. r

PAGE 30

n n r-opt)

PAGE 31

VI Vn VI i i+ <.i VI V2 Vj Vj-I .. Vi+1 Vj+1 Vj+2 VI. i j, W(Vi Vj) W(Vi+1 Vj+l) W(Vi Vi+l) w(Vj Vj+I),

PAGE 32

two-optimal i n i i n. VI V2 .. Vn VI. W W(VIV2) W(V2V3) W(Vn-I v n ) W(Vn VI). i i+2. VI V2. Vi Vj-I Vi+I Vj+IlJ+2 Vn VI. wij Cij. W, ifw(v;vj) W(Vi+l Vj+I) w(v; Vi+I) w(Vj Wj+I), Cij wij. wij, VIV2 .. VnVj n, i i+1. i

PAGE 35

n x-y

PAGE 40

1* *1 1***************************************************** **********1

PAGE 41

1***************************************************** **********1

PAGE 42

1*****************************************************

PAGE 44

1***************************************************** **********1

PAGE 45

1*****************************************************

PAGE 48

1* *1 1*****************************************************

PAGE 50

1*****************************************************

PAGE 52

1*****************************************************

PAGE 56

1*****************************************************

PAGE 58

1*****************************************************

PAGE 61

1***************************************************** **********1

PAGE 62

1***************************************************** **********1

PAGE 65

1***************************************************** **********1

PAGE 66

1***************************************************** **********1 1*****************************************************

PAGE 68

**********1 1*****************************************************

PAGE 69

**********1 1***************************************************** **********1 1*****************************************************

PAGE 70

**********1