Эффективные алгоритмы, осень 2007: Приближённые алгоритмы

  • Published on
    08-Feb-2017

  • View
    82

  • Download
    1

Embed Size (px)

Transcript

<ul><li><p>/ 2: </p><p>. </p><p>Computer Science http://logic.pdmi.ras.ru/infclub/</p><p>. (CS ) 2. 1 / 15</p><p>http://logic.pdmi.ras.ru/~infclub/</p></li><li><p>1 </p><p>. (CS ) 2. 2 / 15</p></li><li><p> A (relative performance guarantee) , I </p><p>I A(I )/OPT(I ) ;I A(I )/OPT(I ) .</p><p> -.</p><p> 1, 1. , 1.</p><p>. (CS ) 2. 3 / 15</p></li><li><p> A (relative performance guarantee) , I </p><p>I A(I )/OPT(I ) ;I A(I )/OPT(I ) .</p><p> -.</p><p> 1, 1. , 1.</p><p>. (CS ) 2. 3 / 15</p></li><li><p> A (relative performance guarantee) , I </p><p>I A(I )/OPT(I ) ;</p><p>I A(I )/OPT(I ) . -.</p><p> 1, 1. , 1.</p><p>. (CS ) 2. 3 / 15</p></li><li><p> A (relative performance guarantee) , I </p><p>I A(I )/OPT(I ) ;I A(I )/OPT(I ) .</p><p> -.</p><p> 1, 1. , 1.</p><p>. (CS ) 2. 3 / 15</p></li><li><p> A (relative performance guarantee) , I </p><p>I A(I )/OPT(I ) ;I A(I )/OPT(I ) .</p><p> -.</p><p> 1, 1. , 1.</p><p>. (CS ) 2. 3 / 15</p></li><li><p> A (relative performance guarantee) , I </p><p>I A(I )/OPT(I ) ;I A(I )/OPT(I ) .</p><p> -.</p><p> 1, 1. , 1.</p><p>. (CS ) 2. 3 / 15</p></li><li><p>1 </p><p>. (CS ) 2. 4 / 15</p></li><li><p> {s1, . . . , sn}. (shortestcommon superstring) u, si .</p><p> NP-.</p><p>. (CS ) 2. 5 / 15</p></li><li><p> {s1, . . . , sn}.</p><p> (shortestcommon superstring) u, si .</p><p> NP-.</p><p>. (CS ) 2. 5 / 15</p></li><li><p> {s1, . . . , sn}. (shortestcommon superstring) u, si .</p><p> NP-.</p><p>. (CS ) 2. 5 / 15</p></li><li><p> {s1, . . . , sn}. (shortestcommon superstring) u, si .</p><p> NP-.</p><p>. (CS ) 2. 5 / 15</p></li><li><p> U = {u1, . . . , un} = {S1, . . . , Sk}, Si U. U: U =</p><p>S S .</p><p> Si pi 0. (set cover problem) , U .</p><p> Hn- .</p><p>. (CS ) 2. 6 / 15</p></li><li><p> U = {u1, . . . , un} = {S1, . . . , Sk}, Si U.</p><p> U: U =</p><p>S S . Si pi 0. (set cover problem) , U .</p><p> Hn- .</p><p>. (CS ) 2. 6 / 15</p></li><li><p> U = {u1, . . . , un} = {S1, . . . , Sk}, Si U. U: U =</p><p>S S .</p><p> Si pi 0. (set cover problem) , U .</p><p> Hn- .</p><p>. (CS ) 2. 6 / 15</p></li><li><p> U = {u1, . . . , un} = {S1, . . . , Sk}, Si U. U: U =</p><p>S S .</p><p> Si pi 0.</p><p> (set cover problem) , U .</p><p> Hn- .</p><p>. (CS ) 2. 6 / 15</p></li><li><p> U = {u1, . . . , un} = {S1, . . . , Sk}, Si U. U: U =</p><p>S S .</p><p> Si pi 0. (set cover problem) , U .</p><p> Hn- .</p><p>. (CS ) 2. 6 / 15</p></li><li><p> U = {u1, . . . , un} = {S1, . . . , Sk}, Si U. U: U =</p><p>S S .</p><p> Si pi 0. (set cover problem) , U .</p><p> Hn- .</p><p>. (CS ) 2. 6 / 15</p></li><li><p>, i , j , k , si k sj k , wijk = si sj [k + 1..|sj |]:</p><p>s6 = abcab X</p><p>bbca Y</p><p>, s2 = bbca Y</p><p>aaccbcac Z</p><p>w6,2,4 = abcab X</p><p>bbca Y</p><p>aaccbcac Z</p><p> s set(s) = {si |si s} set(s) s : U = {s1, . . . , sn}, = {set(si )} {set(wijk)}</p><p>. (CS ) 2. 7 / 15</p></li><li><p> , </p><p> i , j , k , si k sj k , wijk = si sj [k + 1..|sj |]:</p><p>s6 = abcab X</p><p>bbca Y</p><p>, s2 = bbca Y</p><p>aaccbcac Z</p><p>w6,2,4 = abcab X</p><p>bbca Y</p><p>aaccbcac Z</p><p> s set(s) = {si |si s} set(s) s : U = {s1, . . . , sn}, = {set(si )} {set(wijk)}</p><p>. (CS ) 2. 7 / 15</p></li><li><p> , i , j , k , si k sj k , wijk = si sj [k + 1..|sj |]:</p><p>s6 = abcab X</p><p>bbca Y</p><p>, s2 = bbca Y</p><p>aaccbcac Z</p><p>w6,2,4 = abcab X</p><p>bbca Y</p><p>aaccbcac Z</p><p> s set(s) = {si |si s} set(s) s : U = {s1, . . . , sn}, = {set(si )} {set(wijk)}</p><p>. (CS ) 2. 7 / 15</p></li><li><p> , i , j , k , si k sj k , wijk = si sj [k + 1..|sj |]:</p><p>s6 = abcab X</p><p>bbca Y</p><p>, s2 = bbca Y</p><p>aaccbcac Z</p><p>w6,2,4 = abcab X</p><p>bbca Y</p><p>aaccbcac Z</p><p> s set(s) = {si |si s} set(s) s : U = {s1, . . . , sn}, = {set(si )} {set(wijk)}</p><p>. (CS ) 2. 7 / 15</p></li><li><p> , i , j , k , si k sj k , wijk = si sj [k + 1..|sj |]:</p><p>s6 = abcab X</p><p>bbca Y</p><p>, s2 = bbca Y</p><p>aaccbcac Z</p><p>w6,2,4 = abcab X</p><p>bbca Y</p><p>aaccbcac Z</p><p> s set(s) = {si |si s} set(s) s : U = {s1, . . . , sn}, = {set(si )} {set(wijk)}</p><p>. (CS ) 2. 7 / 15</p></li><li><p> , i , j , k , si k sj k , wijk = si sj [k + 1..|sj |]:</p><p>s6 = abcab X</p><p>bbca Y</p><p>, s2 = bbca Y</p><p>aaccbcac Z</p><p>w6,2,4 = abcab X</p><p>bbca Y</p><p>aaccbcac Z</p><p> s set(s) = {si |si s}</p><p> set(s) s : U = {s1, . . . , sn}, = {set(si )} {set(wijk)}</p><p>. (CS ) 2. 7 / 15</p></li><li><p> , i , j , k , si k sj k , wijk = si sj [k + 1..|sj |]:</p><p>s6 = abcab X</p><p>bbca Y</p><p>, s2 = bbca Y</p><p>aaccbcac Z</p><p>w6,2,4 = abcab X</p><p>bbca Y</p><p>aaccbcac Z</p><p> s set(s) = {si |si s} set(s) s</p><p> : U = {s1, . . . , sn}, = {set(si )} {set(wijk)}</p><p>. (CS ) 2. 7 / 15</p></li><li><p> , i , j , k , si k sj k , wijk = si sj [k + 1..|sj |]:</p><p>s6 = abcab X</p><p>bbca Y</p><p>, s2 = bbca Y</p><p>aaccbcac Z</p><p>w6,2,4 = abcab X</p><p>bbca Y</p><p>aaccbcac Z</p><p> s set(s) = {si |si s} set(s) s : U = {s1, . . . , sn}, = {set(si )} {set(wijk)}</p><p>. (CS ) 2. 7 / 15</p></li><li><p> ()</p><p>, , si , 2Hn- </p><p> .</p><p>. (CS ) 2. 8 / 15</p></li><li><p> ()</p><p>, </p><p> , si , 2Hn- </p><p> .</p><p>. (CS ) 2. 8 / 15</p></li><li><p> ()</p><p>, , si</p><p> , 2Hn- </p><p> .</p><p>. (CS ) 2. 8 / 15</p></li><li><p> ()</p><p>, , si , 2Hn-</p><p> .</p><p>. (CS ) 2. 8 / 15</p></li><li><p> ()</p><p>, , si , 2Hn- </p><p> .</p><p>. (CS ) 2. 8 / 15</p></li><li><p> ()</p><p>, , si , 2Hn- </p><p> .</p><p>. (CS ) 2. 8 / 15</p></li><li><p> si (-) s, : s1 si , s1 w1,j ,k , , , .. , </p><p>. (CS ) 2. 9 / 15</p></li><li><p> si (-) s</p><p>, : s1 si , s1 w1,j ,k , , , .. , </p><p>. (CS ) 2. 9 / 15</p></li><li><p> si (-) s, </p><p> : s1 si , s1 w1,j ,k , , , .. , </p><p>. (CS ) 2. 9 / 15</p></li><li><p> si (-) s, : s1 si , s1</p><p> w1,j ,k , , , .. , </p><p>. (CS ) 2. 9 / 15</p></li><li><p> si (-) s, : s1 si , s1 w1,j ,k</p><p> , , , .. , </p><p>. (CS ) 2. 9 / 15</p></li><li><p> si (-) s, : s1 si , s1 w1,j ,k , , , ..</p><p> , </p><p>. (CS ) 2. 9 / 15</p></li><li><p> si (-) s, : s1 si , s1 w1,j ,k , , , .. , </p><p>. (CS ) 2. 9 / 15</p></li><li><p> ()</p><p> , s , s </p><p> .</p><p>. (CS ) 2. 10 / 15</p></li><li><p> ()</p><p> , s</p><p> , s </p><p> .</p><p>. (CS ) 2. 10 / 15</p></li><li><p> ()</p><p> , s , s </p><p> .</p><p>. (CS ) 2. 10 / 15</p></li><li><p> ()</p><p> , s , s </p><p> .</p><p>. (CS ) 2. 10 / 15</p></li><li><p>1 </p><p>. (CS ) 2. 11 / 15</p></li><li><p>, :s1 = abc , s2 = bac , s3 = bcd , s4 = cde wijk :w132 = abcd , w141 = abcde, w241 = bacde, w342 = bcde set(si ) set(wijk), :S1 = set(s1) = {s1}, p1 = 3,S2 = set(s2) = {s2}, p2 = 3,S3 = set(s3) = {s3}, p3 = 3,S4 = set(s4) = {s4}, p4 = 3,S5 = set(w132) = {s1, s3}, p5 = 4S6 = set(w141) = {s1, s3, s4}, p6 = 5,S7 = set(w241) = {s2, s4}, p7 = 5,S8 = set(w342) = {s3, s4}, p8 = 4</p><p>. (CS ) 2. 12 / 15</p></li><li><p>, :s1 = abc , s2 = bac , s3 = bcd , s4 = cde</p><p> wijk :w132 = abcd , w141 = abcde, w241 = bacde, w342 = bcde set(si ) set(wijk), :S1 = set(s1) = {s1}, p1 = 3,S2 = set(s2) = {s2}, p2 = 3,S3 = set(s3) = {s3}, p3 = 3,S4 = set(s4) = {s4}, p4 = 3,S5 = set(w132) = {s1, s3}, p5 = 4S6 = set(w141) = {s1, s3, s4}, p6 = 5,S7 = set(w241) = {s2, s4}, p7 = 5,S8 = set(w342) = {s3, s4}, p8 = 4</p><p>. (CS ) 2. 12 / 15</p></li><li><p>, :s1 = abc , s2 = bac , s3 = bcd , s4 = cde wijk :w132 = abcd , w141 = abcde, w241 = bacde, w342 = bcde</p><p> set(si ) set(wijk), :S1 = set(s1) = {s1}, p1 = 3,S2 = set(s2) = {s2}, p2 = 3,S3 = set(s3) = {s3}, p3 = 3,S4 = set(s4) = {s4}, p4 = 3,S5 = set(w132) = {s1, s3}, p5 = 4S6 = set(w141) = {s1, s3, s4}, p6 = 5,S7 = set(w241) = {s2, s4}, p7 = 5,S8 = set(w342) = {s3, s4}, p8 = 4</p><p>. (CS ) 2. 12 / 15</p></li><li><p>, :s1 = abc , s2 = bac , s3 = bcd , s4 = cde wijk :w132 = abcd , w141 = abcde, w241 = bacde, w342 = bcde set(si ) set(wijk), :S1 = set(s1) = {s1}, p1 = 3,S2 = set(s2) = {s2}, p2 = 3,S3 = set(s3) = {s3}, p3 = 3,S4 = set(s4) = {s4}, p4 = 3,S5 = set(w132) = {s1, s3}, p5 = 4S6 = set(w141) = {s1, s3, s4}, p6 = 5,S7 = set(w241) = {s2, s4}, p7 = 5,S8 = set(w342) = {s3, s4}, p8 = 4</p><p>. (CS ) 2. 12 / 15</p></li><li><p>, U = {si}i[1..4], = {Si}i[1..8], Si pi S6 S2 S6 = set(w141) S2 = set(s2), w141 s2, abcdebac , </p><p>. (CS ) 2. 13 / 15</p></li><li><p>, U = {si}i[1..4], = {Si}i[1..8], Si pi</p><p> S6 S2 S6 = set(w141) S2 = set(s2), w141 s2, abcdebac , </p><p>. (CS ) 2. 13 / 15</p></li><li><p>, U = {si}i[1..4], = {Si}i[1..8], Si pi S6 S2</p><p> S6 = set(w141) S2 = set(s2), w141 s2, abcdebac , </p><p>. (CS ) 2. 13 / 15</p></li><li><p>, U = {si}i[1..4], = {Si}i[1..8], Si pi S6 S2 S6 = set(w141) S2 = set(s2), w141 s2, abcdebac , </p><p>. (CS ) 2. 13 / 15</p></li><li><p> ?</p><p> ?</p><p>2Hn- .</p><p>. (CS ) 2. 14 / 15</p></li><li><p> ?</p><p> ?2Hn- .</p><p>. (CS ) 2. 14 / 15</p></li><li><p> !</p><p>. (CS ) 2. 15 / 15</p></li></ul>

Recommended

View more >