***Mục đích:
- Các khái niệm liên quan đến bài toán và giải quyết bài toán
- Phân tích và đánh giá thuật thoán
- Các kỹ thuật thiết kế thuật toán
- Vận dụng giải quyết các bài toán cụ thể
***Nội dung:
- Giới thiệu
- Chứng minh tính đúng đắn
- Độ phức tạp
- Đệ quy
- Chia để trị
- Quy hoạch động
- Thuật toán tham lam
- Quay lui
- Thuật toán xác xuất
- Lớp các bài toán NP đầy đủ
- Thuật toán xấp xỉ
239 trang |
Chia sẻ: diunt88 | Lượt xem: 2998 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Bài giảng Thuật toán nâng cao, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
!"#$
%&'
($%&
) *+ ' ,
- , %% ,
.,/0($%&0 1
2
34 5
6! 789: ;<
= > 6>?!>"@AB 5C
$?@7B <
1 D ?/'/@
/$@B <E
F =?/
!>
!!B <G<
,
!"
!?@@/
" !7B GC
F
"?&
B 2EE
,AAH?>&
&"7@
" !7B2GG
I4>&)JK ?)L!>"@@B ;;
,AH>AM ?
>>A!
" !7B;N<
;
,>"4<
O!:&&
,>"4
! 1' &!= KP 'P ,
% 9!
E
<Q R/
" !7SQTQ!@SQUQI@7@7S
VQVQV'@7SW)@77<GGCQ
Q >@/@XY@7@Z" !@7SWL3
/@"SWQ[
SQ
\/@'
ASU/7@@@
"S<GG2Q
2Q 7!>"@AYSWQX
@"SU[RIS CCNQ
;Q X
7@7
/
" !7SZ"]@/.QZ S ^ UQ
T>]SZ//7L_@7"@S<G`2Q
EQ Z" !Z
"77
/!>
"!"@ASR
)
&@SI@@@7Sa'@7] @A
7S CC<Q
NQ @Z]!>@)
!!S."!@ SXQ
S
Z//7L_@7"@S<G`<Q
5Q " #R@@Q
N
Wb '# &
7
- , ' ,?&
/&/B
- ,&%c\@?\@
7]!B
,/P?@@
" !B
d#J
! 1' &'P KP
W ' ( + > e> >&f+ H '+ /0
0 1
' > *+ (> >'+ /0
T'#8 !%!""#$
% KP
%$(
g<C% C
> ( "
! (
`
!( ,h ,?
" !B
," !=/iAD
e&(>
/0#/j "' k!l(> > !=
'HP
T
'HP
!!=> e> >($%'HP
3(> >
A m&AmnCop ' AD
3(> >
AE m&A; mA2 m/A m@Am]nCo O
(> >c$
!!=(> >
) *&( ,' e
e " q ,&k!=j ",>
G
,
K 0+ ,,>
?>B' ?>B
,l"
?@BS
%
!"
'4
!/j "'
<C
, k=7r
He!
s
3
, h
*
!
,
+ + > *
3( > e &, H
s
<<
+ HK
,
+ c$
+ j
+ ,> k
+ $(
<
+ c$?<B
,> (>/0 H( !t/j
"' 6 u " !=!t/j "'
0 1
.+ /0
[:>A%>v/J!=/i D
Xj "' o <;2E
%$( o< 2;E
<2
+ c$? B
) e> >
[7
> Jw "#%>
g $
> (S
% 9 6 8 c'D + 9
Xiil7:>A%>
,O c$ x
.+ /0 /j "'o <E;2
4<o ↔ <;2E
4 o <;2E
42o< ;↔ 2E
4;o< 2 ; E
<;
+ j
,> (/g7
!=7r&4A
D
.+ /0
,O /g x
,>
y "@ ?≠ CB
nz
@/y "@
<E
+ ,> k
,> (lq( q {
| !b&4 8 S&4%> @7{l 8 > (
lAD }
.+ /0
,O ,> kx
4<oAnC
4 ovA"#< q(!AAr<
42o] ?A∈~L S B @
4
<N
+ $(
,> (7w /0 $( #!
+
= 4
.+ /0
, $( ex
<?B
&@
>n<
] ]! < /
>n>
@/]
@/
?B
&@
] ?nCB@?<B
@"7@
@??L<BB
@/]
@/
<5
q( ,?<B
O P q( ,
6
j 8 #
j
6
# l>j 8 #' +
[e rSj (Ss
T 6
+
j Sj Ss
<`
q( ,? B
> e> >q( j
6
j ( 8
h)
7
"% l>j 8 #
]?PB @
s
@"7@
s
@/]
] s ]! s s /
s
@/]
y "@ ?B/
s
@/y "@
<G
.+ /0 <
O O P/
QJ
q 9'<EvYQ 9
J> ( 8 % 1 O 1 "Hl
" 9
J!=
Hx
C
.+ /0 <
3(> >
9
A%> => 'vY @ 6 8
&HQ[
OS!b J"H 9
!f
vY @ 6 8 g $
> (Q
l>AH Ho> (!f<EvY
l>& o( 7w AAH"H"
S> (!f`vY
% j" vYr
"
l7w /0SJ P"J!f vY
==
<
.+ /0 <
3(> >I
7.@
7
9
vY1 !f != t #
%!
!:S 9
O " J"H
% S 9
"&pvY'g
!fS 8
!fvY != t #
==+++
.+ /0 <
3(> >PAw "
9
7:>A%> => @ 6 8 P/K
9
%>'vY @ 6 8 #
%"!f vYg 7
> ( 7{
l"l+
Wf vY @> e> >!%! D> *
l>AH Ho;"J!fvY
l>& o2Q N
3(> > u O M
9
A#!f
vY"H
=+++
2
.+ /0
, *
7r #
, *:W-
EN5
< 2;
N`
<5C<
<<2;
EN5
NGGN5`
;
.+ /0
, *Z
EN5
< 2;
EN5
<<2;
<5C<
N`
NGGN5`
E
.+ /0
, *L,>
[7 = $( ,x
`
;
C
<
<
`
<
E
<
;
<
<
C
C
5
C
N
C
E
EN5
<
2
;
N
.+ /0
%!7r > Y> *' =l 8
, *:W- ' , *Z P7w
/0 Y> *' Y>=
,L,>7w /0 Y> *' C> Y>=
[r > Y>> 0 ='7r j 7r K
!b7r #
[r > Y> *&k!'4!' "J"l" 7r j 7r K
!b7r #
5
.+ /0
, *
N2<`C`<
2G;``<5
<G5;;2E
;G2N<;<
;N` `2
< 2;EN5
NGGN5`
#
$o J
4 %$(
*
S u
J 8 > Y>
='
`
.+ /0
, *
1 D
[r j 7r K
7r #> (&k
' > (&k
"- g
%7r j 7r K
7r #
#!'
7r Cf
fo 9
> Y> *K
7r #O
j 7r &f;> Y> *K
7r #O h j 7rQ
%>0S
> Y> *K
7r #O h j 7r
&f;> Y> *K
7r #O h; j 7rSs
J *
7r #o
' &Q3
I '
V "
j
' > (K
7r
Se8 &I ' &V "
j
'
> (K
&
G
.+ /0
, *
1 D
I
V
&I &V
I&V
V&V
m
I&I
V&I
I&I m?
I&V m
V&IBm
V&V
& n?
I<Ch m
VB?&I<Ch m&VB
n
I&I<C m
I&V<Ch m
V&I<Ch m
V&V
n
I&I<C m?
I&V m
V&IB<Ch m
V&V
1 *
' &&fj
K
' &SJ7w /0;> Y> *
2C
.+ /0
, *
1 D
3(!7r > Y> *
' &&fj
K
' &g ;
Ar2
[r > Y> *7w /0&f ,l
" !CQEG '4≥ !
*
7r # "4S ,l
e ,4
qo >n
I&I
$n
V&V
n?
I m
VB?&I m
VB
Oo
& n
I&I<C m?
I&V m
V&IB<Ch m
V&V
n>L $B<Ch m$
2<
.+ /0
, *
1 D
CEN5< 2;
* 7r&4/D %$(
CE< ; NC
CE2; <5C
N5< `C;
N52; C 5`
NGGN5`
CE2;
* 7r&4/D %$(
C2 C
C; < C
E2 < <E
E; C C
<5C
2
.+ /0 2o+ A
.o!=7r #A' !=7r #
*!
V
onA
,e(
%nC&
n<
&'&
nA
&%
% % <
nA
&%
22
.+ /0 2o+ A
, D > *
3(!7r > Y>
fo7w /0%$(
#:o%h nC A nAh Ah %
A nAL< A
A2E nA2; A
A2; nA<5 A<5
A<5 nA<N A
A<N nA` A`
A` nA; A;
A; nA A
A nAA
2;
.+ /0 2o+ A
, D > *
*
Q
!b&+ D > *
< &f+ [
C &f+
2Q q>+ [ H
;Q
%$(o + AO
[ M
" & > e
M
" *'4A
:Jg A
2E
.+ /0 2o+ A
, D > *
1/&f/i D > *o@L<@L s@C
%@L< nC&
n<hh nC
&'&
nA
&%
% % L C
n
%@ n<&
nA
&%
&%
2N
.+ /0 2o+ A
, D > *
.+ /0on2En<CCC<<? B
5A2E<
EA<5<
2A`C
A;C
<A C
CA<
7r > Y> *@
25
.+ /0 2o+ A
, D > *o( +
1/ D > *K
o
3( 7w 9
$ + AQ3" 'D +
&+r
? HB&1/S " %$( r
OlQ
Jon>S> nAnAZ>
O
(vK
ZL<
ZL< n<Q
% ZL< &f[Q.,L< n A
ZL< nCQ
% ZL< &f[Q.,L< n
(
l>oL< n AZL<
.,o>L AZ>LB AZ>LmZ>L<
k o
=
=
==
=
2`
.+ /0 2o+ A
, D > *oO (> >r ex
+ A<E
<Q n<En<<<<
Q [ [ [ [
2Q [ [ [
;Q :J&fAS 9
OoA SA2SANSA5SA<;SA<E
.,S 9
7w /0N> Y> *
#S 9
O 1 + A<E &fo
A SA2SANSA< SA<E nA< A2
M
" u J7w /0E> Y> *
2G
.+ /0 2o+ A
) e> >47r
A nA%n<
A nAL< A%" 7r #r
A n?AB7 %n7'4"47r #r p H
K
' 7<
.+ /0on<E
/0 ,1 +
A2 ' E'4nA2Q
A2 nA AS>/0 ,+ A
A nAA
E n; S>/0 ,+ ;
; n? B
> Y> *+ ;S2> Y> *+ ES > Y> *+
A2Q.,E> Y> *+ A<E
;C
) *+ ' ,
X8
'+ HK
,
6! 789:
= > 6>
!
;
"
1!
789:
u
k , %$( !
l7
!=7r&4 8
$(
# ,7w /0
K
!+
= 4
;2
# $
8 !
1! w ?@7B
8 ,#,>/j "'' $
7%$(
I %
6! 789:?@@77>]B
6! k , %$(9'4
!/j "'
;;
L
O 8
L
1 >/0
,
> 6>
L
&((!
+ 9
:
L((!+ 9
:
Le( e
LX 8
()*"+,
;E
W=' !
PP' ,P
K
,
A ,
9 + ,
;N
%
PP ?>@/7B
+ H! /j "'> ( ( !i
T,P ?>7/7B
+ H! %$( K
,> ( ( !i
.+ /0
! D p H!( bA~<QQ
>@/7o≥ <
>7/7o!n!?A~<≤ ≤ B
;5
$
K
,
" ,> !" #$%&
'( ,
$ 8 ,
c
,"9%r
K
O ( !i ,P
;`
&
, ?
77@B
" !=*" !( &=# K
,
.+ /0
AC
AnAm
A
A ,l7w /0
6! 789:
9 + ,
.%"
;G
[w /0A ,1 9 + ,
.+ /0
!?A~<QQB
&@
≥ <
!nA~<
!nA~<
] ]! /
≤ ≤
] ?!A~B @
!nA~
@/]
!n!?A~<SA~ SsSA~B
@/]
@?!B
@/
EC
6! 9:!=> J?>
"@@77B
6! k /j "' ( !iPP
%$( ,7{ ( !i ,P
6! 9:> J?
"@@77B
6! k ,9:!=> J' ,
/g
&4
6! 789:
) *+ K
,
) *+ 78 ( fK
!b&4Aw"% K
,
E<
) L PP
F L ,P
Z L ,
Z9:%'4/j "' ( !i)
Z7{
%$( ( !iF
/g7
!=7r&4Aw " j
)Z F
E
&4e&(
D PP ' ,P
9 + ,&k #!A ,
"#$
% K
,7
PPl ( !i
A ,r
> (&
! ,P
6! k!b&4Aw "S ,g A
,4Aw"%A ,7
Aw "
E2
'(
W=7r $: H9" e
&(
I J8
I Ph{
I "q>
E;
)(
Xi" J8 Z
)C
R<
)<
s
)L<
R
)
s
)L<
R
)
F:
%
) )C
)L<R )Sn QQ
) F
)ZF
M
"o
%
LPP)
&
!A ,
J#
L!b*" &
!A ,%>
@
LA ,r
&
! ,P
L/i" J8Z
9
EE
)(
.+ /0
T
&%A' ,
De6
' &QT
c D
&%A' Q
)nAn
Sn&
FnAn&Sn
An
Sn&S!>
O D
!>nA
An
Sn&S!>n
An
An&Sn&S!>n
n!>
An&Sn
S!>n
EN
)(
I PZ
)C
] ?B @
S)C
R<
S)<
@"7@
S)C
R
S )
@/]
F:
%
) )C
O D
ZX )< F
ZX ) F
)ZF
M
"o
%
LPP)
&
!A ,
J#
LO 1lD
L(
P
&
! ,P
L" PZ
9
E5
)(
.+ /0
! D p HK
' &'4
≠ &
>@/7o
≠ &
>7/7o!n!?
S&B
I Z
≠ &
] ?
&B @
&
!n
&S!n
@"7@
&
!n&
&S !n&
@/]
&S!n
&
!!n!?
S&B
'
&S!n&&
!!n!?
S&B
.,>@/7Z>7/7
E`
)(
W=" '"q>"9
<Q %O /gSO ( !i ,P
Q O /g 7
!=7r&4 j
% u + H<9 u " )*+
,
-
9:!=> Jl 6! &f$
> q#!#$./0,
9:> JJ 6! #!
,'1
EG
* %+
D M
W=#!#$./0, R"
!=2
3 ( !io
9
&:J'"q>
Q $ "q>?6
"P9B
&H&%'"q>R"
9
2Q
p'"q>
?6"P7
B
&H&%'"q>R
> (&
! ,P
I "q>Z
) R
y "@ ?B/
SR
!n
R
@/y "@
SR F
AD l&H&%'"q>S M
"i
6! l ,9:!=> J
NC
* %+
.+ /0
! D p H!( bA~<QQ
>@/7o≥ <
>7/7o!n!?A~<≤ ≤ B
!?A~<QQB
&@
!nA~<
] ]! /
] ?!A~B @
!nA~
@/]
@/]
@?!B
@/
!?A~<QQB
&@
n<S!nA~
y "@ ? B/
nm<
] ?!A~B @
!nA~
@/]
@/y "@
@?!B
@/
N<
* %+
.+ /0
)o≥ <
Fo!n!?A~<≤ ≤ B
!?A~<QQB
&@
n<S!nA~
!n!?A~Sn<QQB
y "@ ? B/
S!n!?A~Sn<QQB
nm<
] ?!A~B @
!nA~
@/]
!n!?A~Sn<QQB
@/y "@
nS!n!?A~Sn<QQB
@?!B
@/
-./"0123
Rn!n!?A~Sn<QQB
-453
L %n<S!nA~< R9
L %S7
8
*'"q>SR't9
L %nS!n!?A~Sn<QQB
+ " ,P
N
,
1 6! '"q>/g7
!=7r&4"q> j
S u JAD !/g?@!
]B
D M
T!o→8" !/g%O ( !io
<Q"(!
Q%P9 ?>BCS%?>BnC P
7
,AY
&