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

  • Published on
    15-Apr-2017

  • View
    126

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p> NP- 10: FPT-</p><p>. </p><p>Computer Science http://logic.pdmi.ras.ru/infclub/</p><p>. (Computer Science ) 10. FPT- 1 / 28</p><p>http://logic.pdmi.ras.ru/~infclub/</p></li><li><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 2 / 28</p></li><li><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 2 / 28</p></li><li><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 2 / 28</p></li><li><p> -</p><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 3 / 28</p></li><li><p> -</p><p> -</p><p> A , f , g : 2A R, ..f (X ) =</p><p>YX g(Y ). </p><p>g(X ) =YX</p><p>(1)|XY |f (Y ) .</p><p>YX</p><p>(1)|XY |f (Y ) =YX</p><p>ZY</p><p>(1)|XY |g(Z ) =</p><p>=ZX</p><p>g(Z )</p><p>ZYX(1)|XY | = g(X )</p><p>( 1, Z = X , ).</p><p>. (Computer Science ) 10. FPT- 4 / 28</p></li><li><p> -</p><p> -</p><p> A , f , g : 2A R, ..f (X ) =</p><p>YX g(Y ). </p><p>g(X ) =YX</p><p>(1)|XY |f (Y ) .</p><p>YX</p><p>(1)|XY |f (Y ) =YX</p><p>ZY</p><p>(1)|XY |g(Z ) =</p><p>=ZX</p><p>g(Z )</p><p>ZYX(1)|XY | = g(X )</p><p>( 1, Z = X , ).. (Computer Science ) 10. FPT- 4 / 28</p></li><li><p> - </p><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 5 / 28</p></li><li><p> - </p><p> : , , , s t. {s, t} X V g(X ) ( ! , ) n 1 s t, X . , g(X ) s t An1, A G [X ].</p><p>. (Computer Science ) 10. FPT- 6 / 28</p></li><li><p> - </p><p> : , , , s t.</p><p> {s, t} X V g(X ) ( ! , ) n 1 s t, X . , g(X ) s t An1, A G [X ].</p><p>. (Computer Science ) 10. FPT- 6 / 28</p></li><li><p> - </p><p> : , , , s t. {s, t} X V g(X ) ( ! , ) n 1 s t, X .</p><p> , g(X ) s t An1, A G [X ].</p><p>. (Computer Science ) 10. FPT- 6 / 28</p></li><li><p> - </p><p> : , , , s t. {s, t} X V g(X ) ( ! , ) n 1 s t, X . , g(X ) s t An1, A G [X ].</p><p>. (Computer Science ) 10. FPT- 6 / 28</p></li><li><p> - </p><p> ()</p><p> f (X ) n 1 s t, X . , f (V ) s t.</p><p>f (V ) =YV</p><p>(1)|VY |g(Y ) .</p><p> , O*(2n) .</p><p>. (Computer Science ) 10. FPT- 7 / 28</p></li><li><p> - </p><p> ()</p><p> f (X ) n 1 s t, X . , f (V ) s t.</p><p>f (V ) =</p><p>YV</p><p>(1)|VY |g(Y ) .</p><p> , O*(2n) .</p><p>. (Computer Science ) 10. FPT- 7 / 28</p></li><li><p> - </p><p> ()</p><p> f (X ) n 1 s t, X . , f (V ) s t.</p><p>f (V ) =YV</p><p>(1)|VY |g(Y ) .</p><p> , O*(2n) .</p><p>. (Computer Science ) 10. FPT- 7 / 28</p></li><li><p> - </p><p> ()</p><p> f (X ) n 1 s t, X . , f (V ) s t.</p><p>f (V ) =YV</p><p>(1)|VY |g(Y ) .</p><p> , O*(2n) .</p><p>. (Computer Science ) 10. FPT- 7 / 28</p></li><li><p> - </p><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 8 / 28</p></li><li><p> - </p><p> (perfect matching) G = (V ,E ) n/2 , . . . O*(2m).</p><p>. (Computer Science ) 10. FPT- 9 / 28</p></li><li><p> - </p><p> (perfect matching) G = (V ,E ) n/2 , .</p><p> . . O*(2m).</p><p>. (Computer Science ) 10. FPT- 9 / 28</p></li><li><p> - </p><p> (perfect matching) G = (V ,E ) n/2 , . .</p><p> . O*(2m).</p><p>. (Computer Science ) 10. FPT- 9 / 28</p></li><li><p> - </p><p> (perfect matching) G = (V ,E ) n/2 , . . . O*(2m).</p><p>. (Computer Science ) 10. FPT- 9 / 28</p></li><li><p> - </p><p> f (Y ) Y , n/2 . f (V ) . g(Y ) n/2 , Y ( Y ). Y g(Y ) , , O*(2n) .</p><p>. (Computer Science ) 10. FPT- 10 / 28</p></li><li><p> - </p><p> f (Y ) Y , n/2 .</p><p> f (V ) . g(Y ) n/2 , Y ( Y ). Y g(Y ) , , O*(2n) .</p><p>. (Computer Science ) 10. FPT- 10 / 28</p></li><li><p> - </p><p> f (Y ) Y , n/2 . f (V ) .</p><p> g(Y ) n/2 , Y ( Y ). Y g(Y ) , , O*(2n) .</p><p>. (Computer Science ) 10. FPT- 10 / 28</p></li><li><p> - </p><p> f (Y ) Y , n/2 . f (V ) . g(Y ) n/2 , Y ( Y ).</p><p> Y g(Y ) , , O*(2n) .</p><p>. (Computer Science ) 10. FPT- 10 / 28</p></li><li><p> - </p><p> f (Y ) Y , n/2 . f (V ) . g(Y ) n/2 , Y ( Y ). Y g(Y ) , , O*(2n) .</p><p>. (Computer Science ) 10. FPT- 10 / 28</p></li><li><p> - </p><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 11 / 28</p></li><li><p> - </p><p> . V = L R |L| = |R| = n/2. Y R ( Y V ) g(Y ) n/2 , L Y . O*(2n/2).</p><p>. (Computer Science ) 10. FPT- 12 / 28</p></li><li><p> - </p><p> .</p><p> V = L R |L| = |R| = n/2. Y R ( Y V ) g(Y ) n/2 , L Y . O*(2n/2).</p><p>. (Computer Science ) 10. FPT- 12 / 28</p></li><li><p> - </p><p> . V = L R |L| = |R| = n/2.</p><p> Y R ( Y V ) g(Y ) n/2 , L Y . O*(2n/2).</p><p>. (Computer Science ) 10. FPT- 12 / 28</p></li><li><p> - </p><p> . V = L R |L| = |R| = n/2. Y R ( Y V ) g(Y ) n/2 , L Y .</p><p> O*(2n/2).</p><p>. (Computer Science ) 10. FPT- 12 / 28</p></li><li><p> - </p><p> . V = L R |L| = |R| = n/2. Y R ( Y V ) g(Y ) n/2 , L Y . O*(2n/2).</p><p>. (Computer Science ) 10. FPT- 12 / 28</p></li><li><p> - </p><p>1 2 3 4 5 6 7 8 9 10 11 12X</p><p>{1}</p><p>{2}</p><p>{3}</p><p>{1, 3}</p><p>+</p><p>+</p><p>. (Computer Science ) 10. FPT- 13 / 28</p></li><li><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 14 / 28</p></li><li><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 15 / 28</p></li><li><p> (subset-sum problem) n b1, . . . , bn , B .</p><p> 2n.</p><p>. (Computer Science ) 10. FPT- 16 / 28</p></li><li><p> (subset-sum problem) n b1, . . . , bn , B .</p><p> 2n.</p><p>. (Computer Science ) 10. FPT- 16 / 28</p></li><li><p> 2n/2 {b1, . . . , bn/2}. . S {bn/2+1, . . . , bn} B S .</p><p> O*(2n/2). . , 2n .</p><p>. (Computer Science ) 10. FPT- 17 / 28</p></li><li><p> 2n/2 {b1, . . . , bn/2}.</p><p> . S {bn/2+1, . . . , bn} B S .</p><p> O*(2n/2). . , 2n .</p><p>. (Computer Science ) 10. FPT- 17 / 28</p></li><li><p> 2n/2 {b1, . . . , bn/2}. .</p><p> S {bn/2+1, . . . , bn} B S .</p><p> O*(2n/2). . , 2n .</p><p>. (Computer Science ) 10. FPT- 17 / 28</p></li><li><p> 2n/2 {b1, . . . , bn/2}. . S {bn/2+1, . . . , bn} B S .</p><p> O*(2n/2). . , 2n .</p><p>. (Computer Science ) 10. FPT- 17 / 28</p></li><li><p> 2n/2 {b1, . . . , bn/2}. . S {bn/2+1, . . . , bn} B S .</p><p> O*(2n/2). . , 2n .</p><p>. (Computer Science ) 10. FPT- 17 / 28</p></li><li><p> 2n/2 {b1, . . . , bn/2}. . S {bn/2+1, . . . , bn} B S .</p><p> O*(2n/2).</p><p> . , 2n .</p><p>. (Computer Science ) 10. FPT- 17 / 28</p></li><li><p> 2n/2 {b1, . . . , bn/2}. . S {bn/2+1, . . . , bn} B S .</p><p> O*(2n/2). .</p><p> , 2n .</p><p>. (Computer Science ) 10. FPT- 17 / 28</p></li><li><p> 2n/2 {b1, . . . , bn/2}. . S {bn/2+1, . . . , bn} B S .</p><p> O*(2n/2). . , 2n .</p><p>. (Computer Science ) 10. FPT- 17 / 28</p></li><li><p> k- k-</p><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 18 / 28</p></li><li><p> k- k-</p><p> k- (table-k sum problem) k m S , , S .</p><p> mk . , 2- O(m logm). k- O(mk/2 logm) O(mk/2).</p><p>. (Computer Science ) 10. FPT- 19 / 28</p></li><li><p> k- k-</p><p> k- (table-k sum problem) k m S , , S .</p><p> mk . , 2- O(m logm). k- O(mk/2 logm) O(mk/2).</p><p>. (Computer Science ) 10. FPT- 19 / 28</p></li><li><p> k- k-</p><p> k- (table-k sum problem) k m S , , S .</p><p> mk .</p><p> , 2- O(m logm). k- O(mk/2 logm) O(mk/2).</p><p>. (Computer Science ) 10. FPT- 19 / 28</p></li><li><p> k- k-</p><p> k- (table-k sum problem) k m S , , S .</p><p> mk . , 2- O(m logm).</p><p> k- O(mk/2 logm) O(mk/2).</p><p>. (Computer Science ) 10. FPT- 19 / 28</p></li><li><p> k- k-</p><p> k- (table-k sum problem) k m S , , S .</p><p> mk . , 2- O(m logm). k- O(mk/2 logm) O(mk/2).</p><p>. (Computer Science ) 10. FPT- 19 / 28</p></li><li><p> k- k-</p><p> 3-</p><p> k- (k-sum problem) m S , k , S .</p><p> , 3- O(m2). , , 3-, , .</p><p>. (Computer Science ) 10. FPT- 20 / 28</p></li><li><p> k- k-</p><p> 3-</p><p> k- (k-sum problem) m S , k , S .</p><p> , 3- O(m2). , , 3-, , .</p><p>. (Computer Science ) 10. FPT- 20 / 28</p></li><li><p> k- k-</p><p> 3-</p><p> k- (k-sum problem) m S , k , S .</p><p> , 3- O(m2).</p><p> , , 3-, , .</p><p>. (Computer Science ) 10. FPT- 20 / 28</p></li><li><p> k- k-</p><p> 3-</p><p> k- (k-sum problem) m S , k , S .</p><p> , 3- O(m2). , , 3-, , .</p><p>. (Computer Science ) 10. FPT- 20 / 28</p></li><li><p> k- k-</p><p> m , - . y = ax + b y = f (x) = x3 Sx2 x3 Sx2 ax b = 0., (a1, f (a1)), . . . , (am, f (am)) (ax , f (ax)), (ay , f (ay )), (az , f (az)) , ax + ay + az = S .</p><p>. (Computer Science ) 10. FPT- 21 / 28</p></li><li><p> k- k-</p><p> m , - .</p><p> y = ax + b y = f (x) = x3 Sx2 x3 Sx2 ax b = 0., (a1, f (a1)), . . . , (am, f (am)) (ax , f (ax)), (ay , f (ay )), (az , f (az)) , ax + ay + az = S .</p><p>. (Computer Science ) 10. FPT- 21 / 28</p></li><li><p> k- k-</p><p> m , - . y = ax + b y = f (x) = x3 Sx2 x3 Sx2 ax b = 0.</p><p>, (a1, f (a1)), . . . , (am, f (am)) (ax , f (ax)), (ay , f (ay )), (az , f (az)) , ax + ay + az = S .</p><p>. (Computer Science ) 10. FPT- 21 / 28</p></li><li><p> k- k-</p><p> m , - . y = ax + b y = f (x) = x3 Sx2 x3 Sx2 ax b = 0., (a1, f (a1)), . . . , (am, f (am)) (ax , f (ax)), (ay , f (ay )), (az , f (az)) , ax + ay + az = S .</p><p>. (Computer Science ) 10. FPT- 21 / 28</p></li><li><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 22 / 28</p></li><li><p> 2-</p><p>1 - </p><p>2 k- k-</p><p>3 2-</p><p>. (Computer Science ) 10. FPT- 23 / 28</p></li><li><p> 2-</p><p> t = (t1, . . . , tn) {0, 1}n N(t) 2-.</p><p>G (w) =</p><p>t{0,1}nwN(t) .</p><p>, , .</p><p>. (Computer Science ) 10. FPT- 24 / 28</p></li><li><p> 2-</p><p> t = (t1, . . . , tn) {0, 1}n N(t) 2-.</p><p>G (w) =</p><p>t{0,1}n</p><p>wN(t) .</p><p>, , .</p><p>. (Computer Science ) 10. FPT- 24 / 28</p></li><li><p> 2-</p><p> t = (t1, . . . , tn) {0, 1}n N(t) 2-.</p><p>G (w) =</p><p>t{0,1}nwN(t) .</p><p>, , .</p><p>. (Computer Science ) 10. FPT- 24 / 28</p></li><li><p> 2-</p><p> t = (t1, . . . , tn) {0, 1}n N(t) 2-.</p><p>G (w) =</p><p>t{0,1}nwN(t) .</p><p>, , .</p><p>. (Computer Science ) 10. FPT- 24 / 28</p></li><li><p> 2-</p><p> A,B,C n/3. t = (a, b, c), a, b, c {0, 1}n/3,</p><p>N(t) = NC (a, b) + NB(a, c) + NA(b, c) ,</p><p> NC (a, b) , C a, b ( ). NwC ,N</p><p>wB ,N</p><p>wA 2</p><p>n/3 2n/3 :</p><p>NwC (a, b) = wNC (a,b), NwB (b, c) = w</p><p>NB(b,c), NwC (a, b) = wNC (a,b) .</p><p>. (Computer Science ) 10. FPT- 25 / 28</p></li><li><p> 2-</p><p> A,B,C n/3.</p><p> t = (a, b, c), a, b, c {0, 1}n/3,</p><p>N(t) = NC (a, b) + NB(a, c) + NA(b, c) ,</p><p> NC (a, b) , C a, b ( ). NwC ,N</p><p>wB ,N</p><p>wA 2</p><p>n/3 2n/3 :</p><p>NwC (a, b) = wNC (a,b), NwB (b, c) = w</p><p>NB(b,c), NwC (a, b) = wNC (a,b) .</p><p>. (Computer Science ) 10. FPT- 25 / 28</p></li><li><p> 2-</p><p> A,B,C n/3. t = (a, b, c), a, b, c {0, 1}n/3,</p><p>N(t) = NC (a, b) + NB(a, c) + NA(b, c) ,</p><p> NC (a, b) , C a, b ( ).</p><p> NwC ,NwB ,N</p><p>wA 2</p><p>n/3 2n/3 :</p><p>NwC (a, b) = wNC (a,b), NwB (b, c) = w</p><p>NB(b,c), NwC (a, b) = wNC (a,b) .</p><p>. (Computer Science ) 10. FPT- 25 / 28</p></li><li><p> 2-</p><p> A,B,C n/3. t = (a, b, c), a, b, c {0, 1}n/3,</p><p>N(t) = NC (a, b) + NB(a, c) + NA(b, c) ,</p><p> NC (a, b) , C a, b ( ). NwC ,N</p><p>wB ,N</p><p>wA 2</p><p>n/3 2n/3 :</p><p>NwC (a, b) = wNC (a,b), NwB (b, c) = w</p><p>NB(b,c), NwC (a, b) = wNC (a,b) .</p><p>. (Computer Science ) 10. FPT- 25 / 28</p></li><li><p> 2-</p><p>G (w) =a,b,c</p><p>wNC (a,b)+NB(a,c)+NA(b,c) =</p><p>=a,b,c</p><p>wNC (a,b)wNB(a,c)wNA(b,c) =</p><p>=a,c</p><p>wNB(a,c)b</p><p>wNC (a,b)wNA(b,c) =</p><p>=a,c</p><p>NwB (a, c)(NwC N</p><p>wA )(a, c) .</p><p>. (Computer Science ) 10. FPT- 26 / 28</p></li><li><p> 2-</p><p>G (w) =a,b,c</p><p>wNC (a,b)+NB(a,c)+NA(b,c) =</p><p>=a,b,c</p><p>wNC (a,b)wNB(a,c)wNA(b,c) =</p><p>=a,c</p><p>wNB(a,c)b</p><p>wNC (a,b)wNA(b,c) =</p><p>=a,c</p><p>NwB (a, c)(NwC N</p><p>wA )(a, c) .</p><p>. (Computer Science ) 10. FPT- 26 / 28</p></li><li><p> 2-</p><p>G (w) =a,b,c</p><p>wNC (a,b)+NB(a,c)+NA(b,c) =</p><p>=a,b,c</p><p>wNC (a,b)wNB(a,c)wNA(b,c) =</p><p>=a,c</p><p>wNB(a,c)b</p><p>wNC (a,b)wNA(b,c) =</p><p>=a,c</p><p>NwB (a, c)(NwC N</p><p>wA )(a, c) .</p><p>. (Computer Science ) 10. FPT- 26 / 28</p></li><li><p> 2-</p><p>G (w) =a,b,c</p><p>wNC (a,b)+NB(a,c)+NA(b,c) =</p><p>=a,b,c</p><p>wNC (a,b)wNB(a,c)wNA(b,c) =</p><p>=a,c</p><p>wNB(a,c)b</p><p>wNC (a,b)wNA(b,c) =</p><p>=a,c</p><p>NwB (a, c)(NwC N</p><p>wA )(a, c) .</p><p>. (Computer Science ) 10. FPT- 26 / 28</p></li><li><p> 2-</p><p>, O*2n/3 O(22n/3) ( 2.38 ). , (time-space tradeoff).</p><p>. (Computer Science ) 10. FPT- 27 / 28</p></li><li><p> 2-</p><p>, O*2n/3 O(22n/3) ( 2.38 ).</p><p> , (time-space tradeoff).</p><p>. (Computer Science ) 10. FPT- 27 / 28</p></li><li><p> 2-</p><p>, O*2n/3 O(22n/3) ( 2.38 ). , (time-space tradeoff).</p><p>. (Computer Science ) 10. FPT- 27 / 28</p></li><li><p> 2-</p><p> !</p><p>. (Computer Science ) 10. FPT- 28 / 28</p><p> - </p><p> k- k-</p><p> 2-</p></li></ul>

Recommended

View more >