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

  • View
    127

  • Download
    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

    ()

    , ; ,

Recommended

View more >