# Алгоритмы для NP-трудных задач, осень 2009: Приближенные алгоритмы

• View
127

1

Embed Size (px)

Transcript

• NP- 6:

.

Computer Science http://logic.pdmi.ras.ru/infclub/

. (Computer Science ) 6. 1 / 28

http://logic.pdmi.ras.ru/~infclub/

• 1 TSP2- Metric TSP3/2- Metric TSP TSP

2

. (Computer Science ) 6. 2 / 28

• 1 TSP2- Metric TSP3/2- Metric TSP TSP

2

. (Computer Science ) 6. 2 / 28

• 1 TSP2- Metric TSP3/2- Metric TSP TSP

2

. (Computer Science ) 6. 3 / 28

• G = (V ,E ), (u, v) c(u, v). (travelling salesman problem, TSP) . (metric TSP) , :

c(u,w) c(u, v) + c(v ,w) u, v ,w V .

. (Computer Science ) 6. 4 / 28

• G = (V ,E ), (u, v) c(u, v).

(travelling salesman problem, TSP) . (metric TSP) , :

c(u,w) c(u, v) + c(v ,w) u, v ,w V .

. (Computer Science ) 6. 4 / 28

• G = (V ,E ), (u, v) c(u, v). (travelling salesman problem, TSP) .

(metric TSP) , :

c(u,w) c(u, v) + c(v ,w) u, v ,w V .

. (Computer Science ) 6. 4 / 28

• G = (V ,E ), (u, v) c(u, v). (travelling salesman problem, TSP) . (metric TSP) , :

c(u,w) c(u, v) + c(v ,w) u, v ,w V .

. (Computer Science ) 6. 4 / 28

• NP-

NP-. n!. ( ) 2n. NP-.

, 1 2 ,

. (Computer Science ) 6. 5 / 28

• NP-

NP-.

n!. ( ) 2n. NP-.

, 1 2 ,

. (Computer Science ) 6. 5 / 28

• NP-

NP-. n!.

( ) 2n. NP-.

, 1 2 ,

. (Computer Science ) 6. 5 / 28

• NP-

NP-. n!. ( ) 2n.

NP-.

, 1 2 ,

. (Computer Science ) 6. 5 / 28

• NP-

NP-. n!. ( ) 2n. NP-.

, 1 2 ,

. (Computer Science ) 6. 5 / 28

• NP-

NP-. n!. ( ) 2n. NP-.

,

1 2 ,

. (Computer Science ) 6. 5 / 28

• NP-

NP-. n!. ( ) 2n. NP-.

, 1

2 ,

. (Computer Science ) 6. 5 / 28

• NP-

NP-. n!. ( ) 2n. NP-.

, 1 2

,

. (Computer Science ) 6. 5 / 28

• NP-

NP-. n!. ( ) 2n. NP-.

, 1 2 ,

. (Computer Science ) 6. 5 / 28

• TSP

1 TSP2- Metric TSP3/2- Metric TSP TSP

2

. (Computer Science ) 6. 6 / 28

• TSP

Dynamic-TSP(G )

S {2, . . . , n} i S Opt[S , i ] , 1, S {i} i :Opt[S , i ] = min{Opt[S {i}, j ] + d(i , j) : j S {i}} :min{Opt[{2, . . . , n}, j ] + d(j , 1) : 2 j n}

. (Computer Science ) 6. 7 / 28

• TSP

Dynamic-TSP(G ) S {2, . . . , n} i S Opt[S , i ] , 1, S {i} i

:Opt[S , i ] = min{Opt[S {i}, j ] + d(i , j) : j S {i}} :min{Opt[{2, . . . , n}, j ] + d(j , 1) : 2 j n}

. (Computer Science ) 6. 7 / 28

• TSP

Dynamic-TSP(G ) S {2, . . . , n} i S Opt[S , i ] , 1, S {i} i :Opt[S , i ] = min{Opt[S {i}, j ] + d(i , j) : j S {i}}

:min{Opt[{2, . . . , n}, j ] + d(j , 1) : 2 j n}

. (Computer Science ) 6. 7 / 28

• TSP

Dynamic-TSP(G ) S {2, . . . , n} i S Opt[S , i ] , 1, S {i} i :Opt[S , i ] = min{Opt[S {i}, j ] + d(i , j) : j S {i}} :min{Opt[{2, . . . , n}, j ] + d(j , 1) : 2 j n}

. (Computer Science ) 6. 7 / 28

• TSP

Dynamic-TSP poly(n)2n.

1962- .

. (Computer Science ) 6. 8 / 28

• TSP

Dynamic-TSP poly(n)2n.

1962- .

. (Computer Science ) 6. 8 / 28

• 2- Metric TSP

1 TSP2- Metric TSP3/2- Metric TSP TSP

2

. (Computer Science ) 6. 9 / 28

• 2- Metric TSP

2-

Approx-TSP(G )

T G T

. (Computer Science ) 6. 10 / 28

• 2- Metric TSP

2-

Approx-TSP(G ) T G

T

. (Computer Science ) 6. 10 / 28

• 2- Metric TSP

2-

Approx-TSP(G ) T G T

. (Computer Science ) 6. 10 / 28

• 2- Metric TSP

2-

Approx-TSP(G ) T G T

. (Computer Science ) 6. 10 / 28

• 2- Metric TSP

Approx-TSP(G )

T G T

a

b

c

d

e

f g

h

. (Computer Science ) 6. 11 / 28

• 2- Metric TSP

Approx-TSP(G ) T G

T

a

b

c

d

e

f g

h

. (Computer Science ) 6. 11 / 28

• 2- Metric TSP

Approx-TSP(G ) T G T

a

b

c

d

e

f g

h

. (Computer Science ) 6. 11 / 28

• 2- Metric TSP

Approx-TSP(G ) T G T

a

b

c

d

e

f g

h

. (Computer Science ) 6. 11 / 28

• 2- Metric TSP

Approx-TSP(G ) T G T

a

b

c

d

e

f g

h

. (Computer Science ) 6. 11 / 28

• 2- Metric TSP

Approx-TSP 2-.

WT , Wopt WT Wopt, - , , 2WT , , 2Wopt

. (Computer Science ) 6. 12 / 28

• 2- Metric TSP

Approx-TSP 2-.

WT , Wopt WT Wopt, - , , 2WT , , 2Wopt

. (Computer Science ) 6. 12 / 28

• 2- Metric TSP

Approx-TSP 2-.

WT , Wopt

WT Wopt, - , , 2WT , , 2Wopt

. (Computer Science ) 6. 12 / 28

• 2- Metric TSP

Approx-TSP 2-.

WT , Wopt WT Wopt,

- , , 2WT , , 2Wopt

. (Computer Science ) 6. 12 / 28

• 2- Metric TSP

Approx-TSP 2-.

WT , Wopt WT Wopt, - ,

, 2WT , , 2Wopt

. (Computer Science ) 6. 12 / 28

• 2- Metric TSP

Approx-TSP 2-.

WT , Wopt WT Wopt, - , , 2WT , , 2Wopt

. (Computer Science ) 6. 12 / 28

• 3/2- Metric TSP

1 TSP2- Metric TSP3/2- Metric TSP TSP

2

. (Computer Science ) 6. 13 / 28

• 3/2- Metric TSP

3/2-

Approx-TSP-Improved(G )

T G T T

. (Computer Science ) 6. 14 / 28

• 3/2- Metric TSP

3/2-

Approx-TSP-Improved(G ) T G

T T

. (Computer Science ) 6. 14 / 28

• 3/2- Metric TSP

3/2-

Approx-TSP-Improved(G ) T G T

T

. (Computer Science ) 6. 14 / 28

• 3/2- Metric TSP

3/2-

Approx-TSP-Improved(G ) T G T T

. (Computer Science ) 6. 14 / 28

• 3/2- Metric TSP

3/2-

Approx-TSP-Improved(G ) T G T T

. (Computer Science ) 6. 14 / 28

• 3/2- Metric TSP

Approx-TSP-Improved 3/2-.

, WT +WP , WP T , WP Wopt/2 A T A: A , G

. (Computer Science ) 6. 15 / 28

• 3/2- Metric TSP

Approx-TSP-Improved 3/2-.

, WT +WP , WP T , WP Wopt/2 A T A: A , G

. (Computer Science ) 6. 15 / 28

• 3/2- Metric TSP

Approx-TSP-Improved 3/2-.

, WT +WP , WP T

, WP Wopt/2 A T A: A , G

. (Computer Science ) 6. 15 / 28

• 3/2- Metric TSP

Approx-TSP-Improved 3/2-.

, WT +WP , WP T , WP Wopt/2

A T A: A , G

. (Computer Science ) 6. 15 / 28

• 3/2- Metric TSP

Approx-TSP-Improved 3/2-.

, WT +WP , WP T , WP Wopt/2 A T

A: A , G

. (Computer Science ) 6. 15 / 28

• 3/2- Metric TSP

Approx-TSP-Improved 3/2-.

, WT +WP , WP T , WP Wopt/2 A T A: A , G

. (Computer Science ) 6. 15 / 28

• 3/2- Metric TSP

()

, ; , Wopt/2, Wopt/2

. (Computer Science ) 6. 16 / 28

• 3/2- Metric TSP

()

, ;

, Wopt/2, Wopt/2

. (Computer Science ) 6. 16 / 28

• 3/2- Metric TSP

()

, ; ,

Wopt/2, Wopt/2

. (Computer Science ) 6. 16 / 28

• 3/2- Metric TSP

()

, ; , Wopt/2

, Wopt/2

. (Computer Science ) 6. 16 / 28

• 3/2- Metric TSP

()

, ; ,