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

  • Published on
    12-Feb-2017

  • View
    127

  • Download
    1

Embed Size (px)

Transcript

<ul><li><p> NP- 6: </p><p>. </p><p>Computer Science http://logic.pdmi.ras.ru/infclub/</p><p>. (Computer Science ) 6. 1 / 28</p><p>http://logic.pdmi.ras.ru/~infclub/</p></li><li><p>1 TSP2- Metric TSP3/2- Metric TSP TSP</p><p>2 </p><p>. (Computer Science ) 6. 2 / 28</p></li><li><p>1 TSP2- Metric TSP3/2- Metric TSP TSP</p><p>2 </p><p>. (Computer Science ) 6. 2 / 28</p></li><li><p>1 TSP2- Metric TSP3/2- Metric TSP TSP</p><p>2 </p><p>. (Computer Science ) 6. 3 / 28</p></li><li><p> G = (V ,E ), (u, v) c(u, v). (travelling salesman problem, TSP) . (metric TSP) , :</p><p>c(u,w) c(u, v) + c(v ,w) u, v ,w V .</p><p>. (Computer Science ) 6. 4 / 28</p></li><li><p> G = (V ,E ), (u, v) c(u, v).</p><p> (travelling salesman problem, TSP) . (metric TSP) , :</p><p>c(u,w) c(u, v) + c(v ,w) u, v ,w V .</p><p>. (Computer Science ) 6. 4 / 28</p></li><li><p> G = (V ,E ), (u, v) c(u, v). (travelling salesman problem, TSP) .</p><p> (metric TSP) , :</p><p>c(u,w) c(u, v) + c(v ,w) u, v ,w V .</p><p>. (Computer Science ) 6. 4 / 28</p></li><li><p> G = (V ,E ), (u, v) c(u, v). (travelling salesman problem, TSP) . (metric TSP) , :</p><p>c(u,w) c(u, v) + c(v ,w) u, v ,w V .</p><p>. (Computer Science ) 6. 4 / 28</p></li><li><p>NP-</p><p> NP-. n!. ( ) 2n. NP-.</p><p>, 1 2 , </p><p>. (Computer Science ) 6. 5 / 28</p></li><li><p>NP-</p><p> NP-.</p><p> n!. ( ) 2n. NP-.</p><p>, 1 2 , </p><p>. (Computer Science ) 6. 5 / 28</p></li><li><p>NP-</p><p> NP-. n!.</p><p> ( ) 2n. NP-.</p><p>, 1 2 , </p><p>. (Computer Science ) 6. 5 / 28</p></li><li><p>NP-</p><p> NP-. n!. ( ) 2n.</p><p> NP-.</p><p>, 1 2 , </p><p>. (Computer Science ) 6. 5 / 28</p></li><li><p>NP-</p><p> NP-. n!. ( ) 2n. NP-.</p><p>, 1 2 , </p><p>. (Computer Science ) 6. 5 / 28</p></li><li><p>NP-</p><p> NP-. n!. ( ) 2n. NP-.</p><p>, </p><p> 1 2 , </p><p>. (Computer Science ) 6. 5 / 28</p></li><li><p>NP-</p><p> NP-. n!. ( ) 2n. NP-.</p><p>, 1</p><p> 2 , </p><p>. (Computer Science ) 6. 5 / 28</p></li><li><p>NP-</p><p> NP-. n!. ( ) 2n. NP-.</p><p>, 1 2</p><p> , </p><p>. (Computer Science ) 6. 5 / 28</p></li><li><p>NP-</p><p> NP-. n!. ( ) 2n. NP-.</p><p>, 1 2 , </p><p>. (Computer Science ) 6. 5 / 28</p></li><li><p> TSP</p><p>1 TSP2- Metric TSP3/2- Metric TSP TSP</p><p>2 </p><p>. (Computer Science ) 6. 6 / 28</p></li><li><p> TSP</p><p>Dynamic-TSP(G )</p><p> 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}</p><p>. (Computer Science ) 6. 7 / 28</p></li><li><p> TSP</p><p>Dynamic-TSP(G ) S {2, . . . , n} i S Opt[S , i ] , 1, S {i} i</p><p> :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}</p><p>. (Computer Science ) 6. 7 / 28</p></li><li><p> TSP</p><p>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}}</p><p> :min{Opt[{2, . . . , n}, j ] + d(j , 1) : 2 j n}</p><p>. (Computer Science ) 6. 7 / 28</p></li><li><p> TSP</p><p>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}</p><p>. (Computer Science ) 6. 7 / 28</p></li><li><p> TSP</p><p> Dynamic-TSP poly(n)2n.</p><p> 1962- .</p><p>. (Computer Science ) 6. 8 / 28</p></li><li><p> TSP</p><p> Dynamic-TSP poly(n)2n.</p><p> 1962- .</p><p>. (Computer Science ) 6. 8 / 28</p></li><li><p> 2- Metric TSP</p><p>1 TSP2- Metric TSP3/2- Metric TSP TSP</p><p>2 </p><p>. (Computer Science ) 6. 9 / 28</p></li><li><p> 2- Metric TSP</p><p>2- </p><p>Approx-TSP(G )</p><p> T G T </p><p>. (Computer Science ) 6. 10 / 28</p></li><li><p> 2- Metric TSP</p><p>2- </p><p>Approx-TSP(G ) T G</p><p> T </p><p>. (Computer Science ) 6. 10 / 28</p></li><li><p> 2- Metric TSP</p><p>2- </p><p>Approx-TSP(G ) T G T </p><p>. (Computer Science ) 6. 10 / 28</p></li><li><p> 2- Metric TSP</p><p>2- </p><p>Approx-TSP(G ) T G T </p><p>. (Computer Science ) 6. 10 / 28</p></li><li><p> 2- Metric TSP</p><p>Approx-TSP(G )</p><p> T G T </p><p>a</p><p>b</p><p>c</p><p>d</p><p>e</p><p>f g</p><p>h</p><p>. (Computer Science ) 6. 11 / 28</p></li><li><p> 2- Metric TSP</p><p>Approx-TSP(G ) T G</p><p> T </p><p>a</p><p>b</p><p>c</p><p>d</p><p>e</p><p>f g</p><p>h</p><p>. (Computer Science ) 6. 11 / 28</p></li><li><p> 2- Metric TSP</p><p>Approx-TSP(G ) T G T </p><p>a</p><p>b</p><p>c</p><p>d</p><p>e</p><p>f g</p><p>h</p><p>. (Computer Science ) 6. 11 / 28</p></li><li><p> 2- Metric TSP</p><p>Approx-TSP(G ) T G T </p><p>a</p><p>b</p><p>c</p><p>d</p><p>e</p><p>f g</p><p>h</p><p>. (Computer Science ) 6. 11 / 28</p></li><li><p> 2- Metric TSP</p><p>Approx-TSP(G ) T G T </p><p>a</p><p>b</p><p>c</p><p>d</p><p>e</p><p>f g</p><p>h</p><p>. (Computer Science ) 6. 11 / 28</p></li><li><p> 2- Metric TSP</p><p> Approx-TSP 2-.</p><p> WT , Wopt WT Wopt, - , , 2WT , , 2Wopt</p><p>. (Computer Science ) 6. 12 / 28</p></li><li><p> 2- Metric TSP</p><p> Approx-TSP 2-.</p><p> WT , Wopt WT Wopt, - , , 2WT , , 2Wopt</p><p>. (Computer Science ) 6. 12 / 28</p></li><li><p> 2- Metric TSP</p><p> Approx-TSP 2-.</p><p> WT , Wopt </p><p>WT Wopt, - , , 2WT , , 2Wopt</p><p>. (Computer Science ) 6. 12 / 28</p></li><li><p> 2- Metric TSP</p><p> Approx-TSP 2-.</p><p> WT , Wopt WT Wopt, </p><p> - , , 2WT , , 2Wopt</p><p>. (Computer Science ) 6. 12 / 28</p></li><li><p> 2- Metric TSP</p><p> Approx-TSP 2-.</p><p> WT , Wopt WT Wopt, - , </p><p>, 2WT , , 2Wopt</p><p>. (Computer Science ) 6. 12 / 28</p></li><li><p> 2- Metric TSP</p><p> Approx-TSP 2-.</p><p> WT , Wopt WT Wopt, - , , 2WT , , 2Wopt</p><p>. (Computer Science ) 6. 12 / 28</p></li><li><p> 3/2- Metric TSP</p><p>1 TSP2- Metric TSP3/2- Metric TSP TSP</p><p>2 </p><p>. (Computer Science ) 6. 13 / 28</p></li><li><p> 3/2- Metric TSP</p><p>3/2- </p><p>Approx-TSP-Improved(G )</p><p> T G T T </p><p>. (Computer Science ) 6. 14 / 28</p></li><li><p> 3/2- Metric TSP</p><p>3/2- </p><p>Approx-TSP-Improved(G ) T G</p><p> T T </p><p>. (Computer Science ) 6. 14 / 28</p></li><li><p> 3/2- Metric TSP</p><p>3/2- </p><p>Approx-TSP-Improved(G ) T G T </p><p> T </p><p>. (Computer Science ) 6. 14 / 28</p></li><li><p> 3/2- Metric TSP</p><p>3/2- </p><p>Approx-TSP-Improved(G ) T G T T </p><p>. (Computer Science ) 6. 14 / 28</p></li><li><p> 3/2- Metric TSP</p><p>3/2- </p><p>Approx-TSP-Improved(G ) T G T T </p><p>. (Computer Science ) 6. 14 / 28</p></li><li><p> 3/2- Metric TSP</p><p> Approx-TSP-Improved 3/2-.</p><p> , WT +WP , WP T , WP Wopt/2 A T A: A , G</p><p>. (Computer Science ) 6. 15 / 28</p></li><li><p> 3/2- Metric TSP</p><p> Approx-TSP-Improved 3/2-.</p><p> , WT +WP , WP T , WP Wopt/2 A T A: A , G</p><p>. (Computer Science ) 6. 15 / 28</p></li><li><p> 3/2- Metric TSP</p><p> Approx-TSP-Improved 3/2-.</p><p> , WT +WP , WP T</p><p> , WP Wopt/2 A T A: A , G</p><p>. (Computer Science ) 6. 15 / 28</p></li><li><p> 3/2- Metric TSP</p><p> Approx-TSP-Improved 3/2-.</p><p> , WT +WP , WP T , WP Wopt/2</p><p> A T A: A , G</p><p>. (Computer Science ) 6. 15 / 28</p></li><li><p> 3/2- Metric TSP</p><p> Approx-TSP-Improved 3/2-.</p><p> , WT +WP , WP T , WP Wopt/2 A T</p><p> A: A , G</p><p>. (Computer Science ) 6. 15 / 28</p></li><li><p> 3/2- Metric TSP</p><p> Approx-TSP-Improved 3/2-.</p><p> , WT +WP , WP T , WP Wopt/2 A T A: A , G</p><p>. (Computer Science ) 6. 15 / 28</p></li><li><p> 3/2- Metric TSP</p><p> ()</p><p> , ; , Wopt/2, Wopt/2</p><p>. (Computer Science ) 6. 16 / 28</p></li><li><p> 3/2- Metric TSP</p><p> ()</p><p> , ; </p><p> , Wopt/2, Wopt/2</p><p>. (Computer Science ) 6. 16 / 28</p></li><li><p> 3/2- Metric TSP</p><p> ()</p><p> , ; , </p><p> Wopt/2, Wopt/2</p><p>. (Computer Science ) 6. 16 / 28</p></li><li><p> 3/2- Metric TSP</p><p> ()</p><p> , ; , Wopt/2</p><p>, Wopt/2</p><p>. (Computer Science ) 6. 16 / 28</p></li><li><p> 3/2- Metric TSP</p><p> ()</p><p> , ; , Wopt/2, Wopt/2</p><p>. (Computer Science ) 6. 16 / 28</p></li><li><p> 3/2- Metric TSP</p><p> P =NP, 117116 - .3/2 . , 1 2, 5/6- .</p><p>. (Computer Science ) 6. 17 / 28</p></li><li><p> 3/2- Metric TSP</p><p> P =NP, 117116 - .</p><p>3/2 . , 1 2, 5/6- .</p><p>. (Computer Science ) 6. 17 / 28</p></li><li><p> 3/2- Metric TSP</p><p> P =NP, 117116 - .3/2 .</p><p> , 1 2, 5/6- .</p><p>. (Computer Science ) 6. 17 / 28</p></li><li><p> 3/2- Metric TSP</p><p> P =NP, 117116 - .3/2 . , 1 2, 5/6- .</p><p>. (Computer Science ) 6. 17 / 28</p></li><li><p> TSP</p><p>1 TSP2- Metric TSP3/2- Metric TSP TSP</p><p>2 </p><p>. (Computer Science ) 6. 18 / 28</p></li><li><p> TSP</p><p> P =NP (n) = c N. (n)- .</p><p>, - 1 cn + 1 , , n</p><p>. (Computer Science ) 6. 19 / 28</p></li><li><p> TSP</p><p> P =NP (n) = c N. (n)- .</p><p>, - 1 cn + 1 , , n</p><p>. (Computer Science ) 6. 19 / 28</p></li><li><p> TSP</p><p> P =NP (n) = c N. (n)- .</p><p>, - </p><p> 1 cn + 1 , , n</p><p>. (Computer Science ) 6. 19 / 28</p></li><li><p> TSP</p><p> P =NP (n) = c N. (n)- .</p><p>, - 1</p><p> cn + 1 , , n</p><p>. (Computer Science ) 6. 19 / 28</p></li><li><p> TSP</p><p> P =NP (n) = c N. (n)- .</p><p>, - 1 cn + 1</p><p> , , n</p><p>. (Computer Science ) 6. 19 / 28</p></li><li><p> TSP</p><p> P =NP (n) = c N. (n)- .</p><p>, - 1 cn + 1 , , n</p><p>. (Computer Science ) 6. 19 / 28</p></li><li><p> TSP</p><p> ()</p><p> , (nc + 1) + (n 1) &gt; nc , (n)- , n ( !), P=NP</p><p>. (Computer Science ) 6. 20 / 28</p></li><li><p> TSP</p><p> ()</p><p> , (nc + 1) + (n 1) &gt; nc</p><p> , (n)- , n ( !), P=NP</p><p>. (Computer Science ) 6. 20 / 28</p></li><li><p> TSP</p><p> ()</p><p> , (nc + 1) + (n 1) &gt; nc , (n)- , n </p><p> ( !), P=NP</p><p>. (Computer Science ) 6. 20 / 28</p></li><li><p> TSP</p><p> ()</p><p> , (nc + 1) + (n 1) &gt; nc , (n)- , n ( !), </p><p> P=NP</p><p>. (Computer Science ) 6. 20 / 28</p></li><li><p> TSP</p><p> ()</p><p> , (nc + 1) + (n 1) &gt; nc , (n)- , n ( !), P=NP</p><p>. (Computer Science ) 6. 20 / 28</p></li><li><p>1 TSP2- Metric TSP3/2- Metric TSP TSP</p><p>2 </p><p>. (Computer Science ) 6. 21 / 28</p></li><li><p> n w1, . . . ,wn N p1, . . . , pn N, W . (knapsack problem) I [1..n], </p><p>iI wi W </p><p>iI pi ., maxi[1..n] wi W .</p><p>. (Computer Science ) 6. 22 / 28</p></li><li><p> n w1, . . . ,wn N p1, . . . , pn N, W .</p><p> (knapsack problem) I [1..n], </p><p>iI wi W </p><p>iI pi ., maxi[1..n] wi W .</p><p>. (Computer Science ) 6. 22 / 28</p></li><li><p> n w1, . . . ,wn N p1, . . . , pn N, W . (knapsack problem) I [1..n], </p><p>iI wi W </p><p>iI pi .</p><p>, maxi[1..n] wi W .</p><p>. (Computer Science ) 6. 22 / 28</p></li><li><p> n w1, . . . ,wn N p1, . . . , pn N, W . (knapsack problem) I [1..n], </p><p>iI wi W </p><p>iI pi ., maxi[1..n] wi W .</p><p>. (Computer Science ) 6. 22 / 28</p></li><li><p>Psuedopoly-Knapsack({wi}, {pi},W )</p><p>S :=</p><p>i[1..n] piP := maxi[1..n] pi w(k , p) , , , k [1..n], p S k 1 n w(k , p) p 1 S</p><p>w(0, 0) = 0; w(0, p) =, p &gt; 0w(k + 1, p) = min{w(k, p),w(k, p pk+1) + wk+1}</p><p>return p, w(n, p) W</p><p>. (Computer Science ) 6. 23 / 28</p></li><li><p>Psuedopoly-Knapsack({wi}, {pi},W )S :=</p><p>i[1..n] pi</p><p>P := maxi[1..n] pi w(k , p) , , , k [1..n], p S k 1 n w(k , p) p 1 S</p><p>w(0, 0) = 0; w(0, p) =, p &gt; 0w(k + 1, p) = min{w(k, p),w(k, p pk+1) + wk+1}</p><p>return p, w(n, p) W</p><p>. (Computer Science ) 6. 23 / 28</p></li><li><p>Psuedopoly-Knapsack({wi}, {pi},W )S :=</p><p>i[1..n] pi</p><p>P := maxi[1..n] pi</p><p> w(k , p) , , , k [1..n], p S k 1 n w(k , p) p 1 S</p><p>w(0, 0) = 0; w(0, p) =, p &gt; 0w(k + 1, p) = min{w(k, p),w(k, p pk+1) + wk+1}</p><p>return p, w(n, p) W</p><p>. (Computer Science ) 6. 23 / 28</p></li><li><p>Psuedopoly-Knapsack({wi}, {pi},W )S :=</p><p>i[1..n] pi</p><p>P := maxi[1..n] pi w(k , p) , , , k [1..n], p S</p><p> k 1 n w(k , p) p 1 S</p><p>w(0, 0) = 0; w(0, p) =, p &gt; 0w(k + 1, p) = min{w(k, p),w(k, p pk+1) + wk+1}</p><p>return p, w(n, p) W</p><p>. (Computer Science ) 6. 23 / 28</p></li><li><p>Psuedopoly-Knapsack({wi}, {pi},W )S :=</p><p>i[1..n] pi</p><p>P := maxi[1..n] pi w(k , p) , , , k [1..n], p S k 1 n w(k , p) p 1 S</p><p>w(0, 0) = 0; w(0, p) =, p &gt; 0w(k + 1, p) = min{w(k, p),w(k, p pk+1) + wk+1}</p><p>return p, w(n, p) W</p><p>. (Computer Science ) 6. 23 / 28</p></li><li><p>Psuedopoly-Knapsack({wi}, {pi},W )S :=</p><p>i[1..n] pi</p><p>P := maxi[1..n] pi w(k , p) , , , k [1..n], p S k 1 n w(k , p) p 1 S</p><p>w(0, 0) = 0; w(0, p) =, p &gt; 0</p><p>w(k + 1, p) = min{w(k, p),w(k, p pk+1) + wk+1}return p, w(n, p) W</p><p>. (Computer Science ) 6. 23 / 28</p></li><li><p>Psuedopoly-Knapsack({wi}, {pi},W )S :=</p><p>i[1..n] pi</p><p>P := maxi[1..n] pi w(k , p) , , , k [1..n], p S k 1 n w(k , p) p 1 S</p><p>w(0, 0) = 0; w(0, p) =, p &gt; 0w(k + 1, p) = min{w(k, p),w(k, p pk+1) + wk+1}</p><p>return p, w(n, p) W</p><p>. (Computer Science ) 6. 23 / 28</p></li><li><p>Psuedopoly-Knapsack({wi}, {pi},W )S :=</p><p>i[1..n] pi</p><p>P := maxi[1..n] pi w(k , p) , , , k [1..n], p S k 1 n w(k , p) p 1 S</p><p>w(0, 0) = 0; w(0, p) =, p &gt; 0w(k + 1, p) = min{w(k, p),w(k, p pk+1) + wk+1}</p><p>return p, w(n, p) W</p><p>. (Computer Science ) 6. 23 / 28</p></li><li><p>, , nS , n2P ., , pi .: . , . ? . , .</p><p>. (Computer Science ) 6. 24 / 28</p></li><li><p>, , nS , n2P .</p><p>, , pi .: . , . ? . , .</p><p>. (Computer Science ) 6. 24 / 28</p></li><li><p>, , nS , n2P ., , pi .</p><p>: . , . ? . , .</p><p>. (Computer Science ) 6. 24 / 28</p></li><li><p>, , nS , n2P ., , pi .: . , .</p><p> ? . , .</p><p>. (Computer Science ) 6. 24 / 28</p></li><li><p>, , nS , n2P ., , pi .: . , . ?</p><p> . , .</p><p>. (Computer Science ) 6. 24 / 28</p></li><li><p>, , nS , n2P ., , pi .: . , . ? .</p><p> , .</p><p>. (Computer Science ) 6. 24 / 28</p></li><li><p>, , nS , n2P ., , pi .: . , . ? . , .</p><p>. (Computer Science ) 6. 24 / 28</p></li><li><p>, , , K = P(1+1/)n pi K : pi = pi/K Psuedopoly-Knapsack n2max pi n3P(1+ 1/)/P , </p><p>. (Computer Science ) 6. 25 / 28</p></li><li><p>, , , </p><p> K = P(1+1/)n pi K : pi = pi/K Psuedopoly-Knapsack n2max pi n3P(1+ 1/)/P , </p><p>. (Computer Science ) 6. 25 / 28</p></li><li><p>, , , K = P(1+1/)n</p><p> pi K : pi = pi/K Psuedopoly-Knapsack n2max pi n3P(1+ 1/)/P , </p><p>. (Computer Science ) 6. 25 / 28</p></li><li><p>, , , K = P(1+1/)n pi K : pi = pi/K</p><p> Psuedopoly-Knapsack n2max pi n3P(1+ 1/)/P , </p><p>. (Computer Science ) 6. 25 / 28</p></li><li><p>, , , K = P(1+1/)n pi K : pi = pi/K Psuedopoly-Knapsack </p><p> n2max pi n3P(1+ 1/)/P , </p><p>. (Computer Science ) 6. 25 / 28</p></li><li><p>, , , K = P(1+1/)n pi K : pi = pi/K Psuedopoly-Knapsack n2max pi n3P(1+ 1/)/P</p><p> , </p><p>. (Computer Science ) 6. 25 / 28</p></li><li><p>, , , K = P(1+1/)n pi K : pi = pi/K Psuedopoly-Knapsack n2max pi n3P(1+ 1/)/P , </p><p>. (Computer Science ) 6. 25 / 28</p></li><li><p> A , , A Aopt Kn: , ; 1 , K pi pi</p><p>. (Computer Science ) 6. 26 / 28</p></li><li><p> A , </p><p>, A Aopt Kn: , ; 1 , K pi pi</p><p>. (Computer Science ) 6. 26 / 28...</p></li></ul>

Recommended

View more >