( ) 338 8570 255 Tel: 048 858 3577, Fax: 048 858 3716 Email: tohru@nls.ics.saitama-u.ac.jp URL: http://www.nls.ics.saitama-u.ac.jp/ tohru/ 2006.11.29 @ p.1/38
1. 1 2006.11.29 @ p.2/38
1. 1 2. (a) H16 (b) 50 90 2006.11.29 @ p.2/38
? 1. y = f (x) or or 2. 2006.11.29 @ p.3/38
? 1. y = f (x) or or 2. 2006.11.29 @ p.3/38
1.? y = f (x) or y = f (x 1, x 2,..., x n ) or 2. 2006.11.29 @ p.3/38
1.? y = f (x) or y = f (x 1, x 2,..., x n ) or 2. 2006.11.29 @ p.3/38
3? 2006.11.29 @ p.4/38
3? 2006.11.29 @ p.4/38
3? 2006.11.29 @ p.4/38
3? 2006.11.29 @ p.4/38
3 TDR TDR? 2006.11.29 @ p.4/38
3 TDR TDR TDL 52 TDL? 2006.11.29 @ p.4/38
3 TDR TDR TDL 52 TDS 35 TDL TDS? 2006.11.29 @ p.4/38
3 TDR TDR TDL 52 TDS 35 TDL TDS 87? 2006.11.29 @ p.4/38
3 TDR TDR TDL 52 TDS 35 TDL TDS 87? 2006.11.29 @ p.4/38
S 1 S!!! S! S 672( )!!! 672? 2006.11.29 @ p.5/38
S 4 318 318? 2006.11.29 @ p.6/38
7 3 ( ) 3? 2006.11.29 @ p.7/38
( ) 7 3 ( ) 3? 2006.11.29 @ p.7/38
TDR?! 2006.11.29 @ p.8/38
TDR? (Traveling Salesman Problem, TSP)! 2006.11.29 @ p.8/38
TDR? (Traveling Salesman Problem, TSP)! 2006.11.29 @ p.8/38
N N ( ) N ( ) G = (V, E) ( ) c : E R 1 ( ) 2006.11.29 @ p.9/38
N N ( ) 2006.11.29 @ p.10/38
TSP (att48) http://www.iwr.euni-heidelberg.de/groups/comopt/software/tsplib95/ 2006.11.29 @ p.11/38
TSP (att532) http://www.iwr.euni-heidelberg.de/groups/comopt/software/tsplib95/ 2006.11.29 @ p.12/38
TSP (usa13509) 2006.11.29 @ p.13/38
TSP (d15112) http://www.iwr.euni-heidelberg.de/groups/comopt/software/tsplib95/ 2006.11.29 @ p.14/38
TSP (sw24978) 2006.11.29 @ p.15/38
TSP (pla85900) 2006.11.29 @ p.16/38
TSP 1. Solving Traveling Salesman Problem http://www.math.princeton.edu/tsp/ 2. TSPLIB (16 85900 ) http://www.iwr.uni-heidelberg.de/groups/comopt/software/tsplib95/ 3. TSPBIB http://www.densis.fee.unicamp.br/ moscato/tspbib_home.html 2006.11.29 @ p.17/38
TSP? TSP TSP 1. ( ) 2. 3. 4. ( ) 5. 6. VLSI ( ) = TSP 2006.11.29 @ p.18/38
TSP? TSP TSP 1. ( ) 2. 3. 4. ( ) 5. 6. VLSI ( ) = TSP 2006.11.29 @ p.18/38
TSP? TSP TSP 1. ( ) 2. 3. 4. ( ) 5. 6. VLSI ( ) = TSP 2006.11.29 @ p.18/38
TSP? TSP TSP 1. ( ) 2. 3. 4. ( ) 5. 6. VLSI ( ) = TSP ( ) 2006.11.29 @ p.18/38
TSP?? = 2006.11.29 @ p.19/38
TSP?? = 2006.11.29 @ p.19/38
TSP?? = 2006.11.29 @ p.19/38
TSP?? = 2006.11.29 @ p.19/38
2006.11.29 @ p.20/38
TSP?? = = N 2006.11.29 @ p.21/38
TSP?? = = N 2006.11.29 @ p.21/38
TSP?? = N = 13 = N 2006.11.29 @ p.21/38
TSP?? = N = 13 (N 1)!/2 = N 2006.11.29 @ p.21/38
TSP?? = N = 13 (N 1)!/2 = N 2006.11.29 @ p.21/38
(vs ) ; km ( CX 9 2000.10.9 12.18 ) 2006.11.29 @ p.22/38
(vs ) 80 k=0 2 k = 2 81 2 2.4 10 24 = 8.9 10 17 = 3.5 10 11 ; km ( CX 9 2000.10.9 12.18 ) 2006.11.29 @ p.22/38
(vs ) 80 k=0 2 k = 2 81 2 2.4 10 24 = 8.9 10 17 = 3.5 10 11 42 ; km ( CX 9 2000.10.9 12.18 ) 2006.11.29 @ p.22/38
(vs ) 80 k=0 2 k = 2 81 2 2.4 10 24 = 8.9 10 17 = 3.5 10 11 42 ; 0.1 2 42 = 40 km ( CX 9 2000.10.9 12.18 ) 2006.11.29 @ p.22/38
(vs ) 80 k=0 2 k = 2 81 2 2.4 10 24 = 8.9 10 17 = 3.5 10 11 42 ; 0.1 2 42 = 40 km ( CX 9 2000.10.9 12.18 ) 2006.11.29 @ p.22/38
TSP N! N! = 2πN ( N e ) N ( 1 + 1 ( )) 12N + 1 288N 139 1 2 51840N + O 3 N 4 N! N N : N : N N (exponential time algorithm) 2006.11.29 @ p.23/38
TSP N (N 1)!/2 4 3 5 12 6 60 7 360 8 2,520 9 20,160 10 181,440 18 11 1,814,400 180 12 19,958,400 1995 13 239,500,800 2 14 3,113,510,400 31 15 43,589,145,600 435 16 653,837,184,000 6538 17 10,461,394,944,000 10 18 177,834,714,048,000 177 19 3,201,185,852,864,000 3201 20 60,822,550,204,416,000 6. 30 4,420,880,996,869,850,977,271,808,000,000 44. 53 40,329,087,585,471,939,285,830,318,428,201,883,487,644,752,720,441,638,912,000,000,000,000 4 100 466631077219720763408496194281333502453579841321908107342964819476087999966149578044707319880782591431268489604136118791255926054584320000000000000000000000. 1000 2.011936300385468 10 2564 10000 1.423129840458527 10 35655... 2006.11.29 @ p.24/38
N N 2 N 3 N 5 2 N 3 N N! 10 0.1µ 1µ 100µ 1µ 59µ 3.6 m 20 0.4µ 8µ 3.2m 1 m 3.49 77.1 30 0.9µ 27µ 24.3m 1.07 57.2 5.6 10 5 40 1.6µ 64µ 0.102 18.3 386 1.72 10 21 50 2.5µ 125µ 0.313 313 23 6.43 10 37 100 10µ 1 m 10 2679.8 1.1 10 21 1.97 10 131 f : femto (10 15 ) p : pico (10 12 ) n : nano (10 9 ) µ : micro (10 6 ) P : Peta (10 15 ), T : Tera (10 12 ) G : Giga (10 9 ) 1 10 9 ( ) 150 N = 20 N = 15 N = 12 :, 2000 2006.11.29 @ p.25/38
TSP?? = N = 13 (N 1)!/2 = N TSP ( ) 2006.11.29 @ p.26/38
TSP?? = N = 13 (N 1)!/2 = N TSP N = 13 ( N = 17 ) 2006.11.29 @ p.26/38
TSP?? = N = 13 (N 1)!/2 = N TSP N = 13 ( N = 17 ) 2006.11.29 @ p.26/38
TSP?? = N = 13 (N 1)!/2 = N TSP N = 13 ( N = 17 ) 2006.11.29 @ p.26/38
(algorithm) (Abu Ja far Mohammed ibn Mûsâ al-khowârizmi) cf. (algebra) ( ) (countable) an algorithm for... ing 2006.11.29 @ p.27/38
(Polynomial time algorithm) N N (exponential time algorithm) N N 2006.11.29 @ p.28/38
(Polynomial time algorithm) N N (exponential time algorithm) N N 2006.11.29 @ p.28/38
(Polynomial time algorithm) N N (exponential time algorithm) N N 2006.11.29 @ p.28/38
(Polynomial time algorithm) N N (exponential time algorithm) N N 2006.11.29 @ p.28/38
(Polynomial time algorithm) N N (exponential time algorithm) N N 2006.11.29 @ p.28/38
(Polynomial time algorithm) N N (exponential time algorithm) N N 2006.11.29 @ p.28/38
(Polynomial time algorithm) N N (exponential time algorithm) N N 2006.11.29 @ p.28/38
( ) (polynomial time algorithm) (exponential time algorithm) ( ) : (Polynomial Time Solvable) : (Nondeterministic Polynomial Time Solvable) 1 Time Solvable 2 3 2006.11.29 @ p.29/38
( ) (polynomial time algorithm) (exponential time algorithm) ( ) P : (Polynomial Time Solvable) : (Nondeterministic Polynomial Time Solvable) 1 Time Solvable 2 3 2006.11.29 @ p.29/38
( ) (polynomial time algorithm) (exponential time algorithm) ( ) P : (Polynomial Time Solvable) NP : (Nondeterministic Polynomial Time Solvable) 1 Time Solvable 2 3 2006.11.29 @ p.29/38
( ) (polynomial time algorithm) (exponential time algorithm) ( ) P : (Polynomial Time Solvable) NP : (Nondeterministic Polynomial Time Solvable) 1 Not-Polynomial Time Solvable 2 3 2006.11.29 @ p.29/38
( ) (polynomial time algorithm) (exponential time algorithm) ( ) P : (Polynomial Time Solvable) NP : (Nondeterministic Polynomial Time Solvable) 1 Not-Polynomial Time Solvable 2 NP 3 NP 2006.11.29 @ p.29/38
1. (deterministic algorithm) 2. (nondeterministic algorithm)! 2006.11.29 @ p.30/38
http://karai.vis.ne.jp/ 2006.11.29 @ p.31/38
http://karai.vis.ne.jp/ 2006.11.29 @ p.31/38
http://karai.vis.ne.jp/ 2006.11.29 @ p.31/38
http://karai.vis.ne.jp/ 2006.11.29 @ p.31/38
P? NP? 1. ( P ) 2. = cf. 2006.11.29 @ p.32/38
P? NP? 1. ( P ) 2. = cf. 2006.11.29 @ p.32/38
P? NP? 1. ( P ) 2. = (P ) cf. 2006.11.29 @ p.32/38
P? NP? 1. ( P ) 2. = (P ) cf. 2006.11.29 @ p.32/38
P? NP? 1. ( P ) 2. = (P ) cf. 2006.11.29 @ p.32/38
P = NP P NP 1 P = NP P NP ( ) 2 P 3 ( ) (Clay Mathematics Institute) (Millennium Problems) 2006.11.29 @ p.33/38
P = NP P NP P = NP P NP 1 P NP ( ) 2 P 3 ( ) (Clay Mathematics Institute) (Millennium Problems) 2006.11.29 @ p.33/38
P = NP P NP P = NP P NP 1 P NP ( ) 2 P NP P 3 ( ) (Clay Mathematics Institute) (Millennium Problems) 2006.11.29 @ p.33/38
P = NP P NP P = NP P NP 1 P NP ( ) 2 P NP P 3 (+100 ) (Clay Mathematics Institute) (Millennium Problems) 2006.11.29 @ p.33/38
Millennium Problems In order to celebrate mathematics in the new millennium, the Clay Mathematics Institute of Cambridge, Massachusetts (CMI) has named seven Prize Problems. The Scientific Advisory Board of CMI selected these problems, focusing on important classic questions that have resisted solution over the years. The Board of Directors of CMI designated a 7 million prize fund for the solution to these problems, with 1 million allocated to each. During the Millennium Meeting held on May 24, 2000 at the Collége de France, Timothy Gowers presented a lecture entitled The Importance of Mathematics, aimed for the general public, while John Tate and Michael Atiyah spoke on the problems. The CMI invited specialists to formulate each problem. 1. Birch and Swinnerton-Dyer Conjecture 2. Hodge Conjecture 3. Navier-Stokes Equations 4. P vs NP 5. Poincaré Conjecture 6. Riemann Hypothesis 7. Yang-Mills Theory 2006.11.29 @ p.34/38
( ) : sw24978@tsp CPU 8 1. 2. : 2-opt, 3-opt, λ-opt Lin-Kernighan 2006.11.29 @ p.35/38
1. (a) 2. (a) (b) (c) (d) P NP 3. (a) (b) 2006.11.29 @ p.36/38
OS Windows Windows setup UNIX? Makefile? configure? ( ) CG goo excite 2006.11.29 @ p.37/38
OS Windows Windows setup UNIX? Makefile? configure? ( ) CG goo excite 2006.11.29 @ p.37/38
OS Windows Windows setup UNIX? Makefile? configure? ( ) CG goo excite 2006.11.29 @ p.37/38
OS Windows Windows setup UNIX? Makefile? configure? ( ) CG goo excite 2006.11.29 @ p.37/38
: tohru@nls.ics.saitama-u.ac.jp : 5F 506 : 048 858 3577 PDF http://www.nls.ics.saitama-u.ac.jp/ tohru/lectures/ : saidai : ics 2006.11.29 @ p.38/38