CH
ƯƠ
NG IX: Đ TH Ị
Ồ
ị
ể
ễ ậ
ế
1. Đ nh nghĩa 2. Các khái ni mệ 3. Bi u di n đ th trong máy tính ồ ị 4. Các thu t toán tìm ki m trên đ th ồ ị ng đi ng n nh t 5. Bài toán tìm đ ấ ắ ườ 6. Bài toán cây khung 7. Tính liên thông c a đ th ồ ị ủ
1. Đ nh nghĩa
ị
La môt câu truc r i rac G=< V, E> ́ ờ
V la tâp cac đinh ( vertices)
̀ ̣ ́ ̣
E la tâp cac canh ( Edges) - tâp cac căp
̀ ̣ ́ ̉
(u,v) ma u,v la hai đinh thuôc V.
̀ ̣ ́ ̣ ̣ ́ ̣
̀ ̀ ̉ ̣
1. Đ nh nghĩa
ị
ự
D a vao đăc tinh cua tâp E: G la đ n đô thi nêu gi
hai đinh u va v bât
̀ ơ
ữ
̀ ̣ ́ ̉ ̣
ki co nhiêu nhât môt canh
̀ ̣ ́ ̉ ̀ ́
hai đinh u va v bât
ữ
̀ ́ ̀ ́ ̣ ̣
ki co thê co nhiêu h n môt canh
G la đa đô thi nêu gi ơ
̀ ̀ ̣ ́ ̉ ̀ ́
̀ ́ ̉ ́ ̀ ̣ ̣
1. Đ nh nghĩa
ị
G-undirected graph nêu (u,v)=(v,u). G-directed graph nêu (u,v)<>(v,u), goi la
́
cac cung.
́ ̣ ̀
́
1. Đ nh nghĩa
ị
Hình A
Hình B
Hình C
Hình D
ng ng
̀ ̀ ̣
̀ ̀ ̣
Hinh A: Đ n đô thi, vô h ơ Hinh B: Đ n đô thi, co h ơ Hinh C: Đa đô thi, vô h Hinh D: Đa đô thi, co h
ng ng
ướ ́ ướ ướ ́ ướ
̀ ̀ ̣
̀ ̀ ̣
2. Các khái ni mệ
a) Canh liên thuôc, đinh kê, bâc
̣ ̣ ̉ ̀ ̣
va e la liên thuôc v i u va v
Nêu e=(u,v) thi u,v kê nhau (adjacent) ớ
́ ̀ ̀
Nêu e la môt cung thi ta noi u nôi t
́ ớ
̀ ̀ ̣ ̀
i v va u. Cung e đi ra khoi đinh u
́ ừ
́ ̀ ̣ ̀ ́ ̀
̉ ̉
v nôi t ( đinh đâu) va đi vao đinh v ( đinh cuôi). Bâc (degree) cua v ( deg(v)) la sô canh
̉ ̀ ̀ ̀ ̉ ̉ ́
liên thuôc v i v.
ớ
̣ ̉ ̀ ́ ̣
̣
2. Các khái ni mệ
Ví dụ
2
3
2
3
4
1
1
4
4
5
5
6
6
2. Các khái ni mệ
̀ ̀
ườ Môt đ
̣ ườ
1…vp) mà canh v
i-1vi
̣
̣ ̣
̣ ̉ ́ ́ ̉ ́ ̉
b) Đ ng đi va chu trinh ng đi P=( v thuôc E v i moi i 1<=i<=p). ớ P goi la đ n gian nêu tât ca cac đinh ̀ ơ ng đi đêu phân biêt.
trên đ
ườ
̀ ̣
2. Các khái ni mệ
Môt đ
ng đi con cua P la môt đoan
ườ
̣ ̉ ̀ ̣ ̣
P goi la đ n gian nêu tât ca cac đinh
liên tuc doc theo P. ̀ ơ
̣ ̣
đêu la phân biêt.
̣ ̉ ́ ́ ̉ ́ ̉
P goi la chu trinh (circuit) n u v
ế
̀ ̀ ̣
1=vp
Môt đô thi vô h
̣ ̀ ̀
̣ ̀ ̣ ̣ ̀
ng goi la liên thông ướ (connected) nêu v i moi căp đinh (u,v) ớ c v. đêu co u đên đ
ượ
́ ̣ ̣ ̉
̀ ́ ́
3. Bi u di n đ th trong máy tính ồ ị
ể
ễ
a) Ma tr n kậ Đanh sô th t 1 đên n ề ́ ứ ự ̣ ừ ́ ́ ̉ ̉ ̀
̉ ̃ ̀ ̣ ̀ ̣ ̣ ́
̣ ̀ ̣ ̀
́ ̀ ̣ ̣
́ cac đinh cua đô thi t biêu diên đô thi băng môt ma trân vuông câp n goi la ma trân kê: a[i,j]=1 nêu i, j la canh thuôc E. a[i,j]=0 nêu i, j la canh không thuôc E. ́ ̀ ̣ ̣
Cac tinh chât cua ma trân kê:
Đôi v i đô thhi vô h
ng thi ma trân kê
́ ớ
́ ́ ́ ̉ ̣ ̀
ướ la đôi x ng (a[i,j]=a[j,i]).
́ ứ
̀ ̣ ̀ ̣ ̀
Tông cac sô trên hang i băng tông cac
̀
sô trên côt i =deg(i)
̉ ́ ́ ̀ ̀ ̉ ́
́ ̣
Vi dú
1
1
2
2
5
5
A =
A =
0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 0 0
0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0
4
3
4
3
̣
Vi dú
̣
Graphs - Data Structures
• Vertices
• Map to consecutive integers • Store vertices in an array
• Edges
• Adjacency Matrix • Booleans -
TRUE - edge exists FALSE - no edge
• O(|V|2) space
2. Các khái ni mệ
Nhân xet:
̣ ́
2 dân đên lang phi
ướ
̃ ̀ ̣
́ ̀ ̃ ́ ̃ ́
̉ ́ ̉ ̀ ̉ ́ ̣
̃ ớ
ớ
̣ ̉ ̀ ́ ́ ̉ ́ ̉ ̀
̀ ớ
̃ ́ ̣ ̀
Tr c quan, dê cai đăt ự Kich th c luôn la N Kiêm tra cac đinh kê cua u, cac canh liên thuôc cua u cân xet tât ca cac đinh v ma i lang phi bô nh khi u la a[u,v]<>0 dân t đinh cô lâp hoăc đinh treo ( chi kê v i 1 đinh).
̉ ̣ ̣ ̉ ̉
̉
3. Bi u di n đ th trong máy tính ồ ị
ễ
ể
́ ̣
̣ ́ ̉ ́ ̣ ̉ ̀ ̣
b) Danh sach canh (edge list) Liêt kê tât ca cac canh cua đô thi trong cua danh
ử
môt danh sach, môi phân t sach la môt căp (u,v)
̣ ́ ̃ ̀ ̉
Danh sach đ
c l u trong bô nh băng
ớ
́ ̀ ̣ ̣
ượ ư mang hoăc danh sach moc nôi.
́ ̣ ̀
̉ ̣ ́ ́ ́
1
2
5
4
3
3. Bi u di n đ th trong máy tính ồ ị
ể
ễ
b) Danh sach canh (edge list)
1 2 3 4 5 6
(1, 2)
(1, 3)
(1, 5)
(2, 3)
(3, 4)
(4, 5)
(1, 2)
(1, 3)
(1, 5)
(2, 3)
(3, 4)
(4, 5)
́ ̣
3. Bi u di n đ th trong máy tính ồ ị
ễ
ể
ng h p đô thi th a, tiêt kiêm
̣ ư
ườ
̣ ́
ơ
̀ ́ ̣
Nhân xet Trong tr ợ Viêc duyêt cac canh dê dang h n. Nh
̣ ̣ ́ ̣ ̃ ̀
ượ ̀ ớ
̉ ́ ̉ ́ ̉
ứ
̀ ̉ ̣ ́ ̉ ́ ̣ ̀
ng
ườ
ờ
̣ ́ ̉ ́ ̣ ́
c điêm: khi duyêt v i tât ca cac đinh ̣ ớ kê v i v thi phai duyêt tât ca cac canh va chon tât ca cac canh co ch a v rât tôn th i gian, nhât la trong tr h p ma trân day.
ợ
́ ́ ́ ̀
̣ ̀
3. Bi u di n đ th trong máy tính ồ ị
ể
ễ
́ ̀
c) Danh sach kê (adjacency list) V i môi đinh ta cho t
ng ng môt danh sach cac đinh
ươ
ứ
ớ kê v i v. ̀ ớ
̃ ̉ ̣ ́ ́ ̉
1
2
5
4
3
1 2 3 4 5 6 7 8 9 10 11 12
2
3
5
1
3
1
2
4
3
5
1
4
1 2 3 4 5
Ồ
NG IX: Đ TH CH Ị 3. Bi u di n đ th trong máy tính ồ ị
ƯƠ ể
ễ
c) Danh sach kê (adjacency list)
List 1:
2
3
5
́ ̀
Graphs - Data Structures
• Edges
List 2:
1
3
• Adjacency Lists
• For each vertex
• List of vertices “attached” to it
List 3:
1
2
4
• For each edge • 2 entries • One in the list for each end
• O(|E|) space
List 4:
3
5
\ Better for sparse graphs
Undirected representation
List 5:
1
4
Nhân xet.
Duyêt tât ca cac đinh kê cua môt đinh la
̣ ́
hêt s c dê dang.
́ ứ
̣ ́ ̉ ́ ̉ ̀ ̉ ̣ ̉ ̀
Kho kiêm tra (u,v) co phai la canh hay
̃ ̀
không.
́ ̉ ́ ̉ ̀ ̣
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
Bai toan.
̀ ́ ̀ ̣ ̀ ̣ ́ ̉
́ ̉ ́ ̉ ́ ̣ ̉ ́ ́
Cho đô thi G =
cac đinh co thê đên đ c t ượ ừ nao đo v i yêu câu la không đ lai bât ki môt đinh nao. ̣ ́ ̀ ̣ ̉ ̀
ự ̀ ̉ ́ ̣ ́ ̣ ̣ ́
Cân phai xây d ng cac thuât toan duyêt môt cach co hê thông cac đinh va goi cac thuât toan đo la thuât toan tim kiêm trên đô thi.
́ ̣ ́ ́ ̉ ̀ ̣ ́ ̣ ́ ́ ̀
̣ ́ ̀ ́ ̀ ̣
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
a) Tìm ki m theo chi u sâu (Depth first
ề
S.
c t ượ ừ
̀ ớ
̣ ̉ ̃ ́
ế search) Moi đinh x kê v i S se đên đ V i môi đinh x kê v i S nh ng đinh y kê v i x ữ
̀ ớ
ớ
cung đên đ
̀ ớ S.
c t ượ ừ
̃ ̉ ̉
̃ ́
Xet thu tuc đê quy DFS(u): duyêt t
̣ ừ
́ ̉ ̣ ̣ ̉
ư
̀ ́ ̉ ̀ ́ ̣ ́ ̀
đinh u băng cach thăm đinh u va tiêp tuc qua trinh duyêt DFS(v) trong đo v la đinh ch a thăm kê v i u…
̀ ớ
̣ ́ ̀ ̉
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
2nd
5th
Ví dụ
2
4
2
4
6
6
6th
7
1
1
7
8
8
1st
3
3
5
5
3rd
4th
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
́ ̉ ́ ̉ ̀ ̉ ̉ ́
ng t
́ ươ
ự ớ
̀ ̉ ́ ̀ ̣ ̃ ̣
ỡ
̀ ̣ ̉ ́
Khi tât ca cac đinh kê cua đinh cuôi cung cua qua trinh đê quy trên đa duyêt v i đinh sat thi quay lai xet t cuôi,… tiêp tuc cho đên khi tr lai đinh u.
́ ́ ̣ ́ ̣ ̉
̣ ̣ ̉ ̀ ̣ ̣ ́
c thăm.
̀ ̣ ́ ́ ̉
́ ̉ ̀
̉ ́ ̣ ̣
̀ ̀ ́ ́ ̉ ̃
Chon môt đinh ch a thăm va lăp lai qua ư trinh đê quy nh trên cho đên khi tât ca ư cac đinh đêu đa đ ̃ ượ Đê tranh viêc ch a thăm hoăc thăm ư nhiêu h n 1 lân ta đanh dâu đinh đa ơ thăm đê b c duyêt đê quy tiêp la không ̉ ướ thăm lai đinh đo n a.
́ ữ
̣ ̣ ́ ̀
̣ ̉
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
ư ́ ̉ ̣
̣ ườ ướ ̣ ̣ ̀ ̣
ớ ư ̉ ̀ ́ ́ ̣ ̉
u t ướ ư ườ ừ ớ ̀ ̀ ́
̣ ̣ ̉ ̀
s t ớ ́ ́
L u lai đ ng đi xuât phat t s, trong thu tuc ́ ừ c khi goi đê quy DFS(v) v i v la môt DFS(u) tr đinh kê v i u ma ch a đanh dâu, ta l u lai đinh ̀ ớ c v trong đ i v băng cach liên tr ng đi t c v trên đăt Trace[v]=u (l u lai đinh liên tr ướ ư ng đi i v). Khi kêt thuc ta co đ đ ng đi t ́ ườ ừ ườ t S đên f la: ừ f –p[1] = Trace(f)- p[2]= Trace[p[1]]-------s
́ ̀
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
a) Tìm ki m theo chi u sâu (Depth first
ề
ế search) ́ : Nhân xet
Thu tuc DFS se đ
c goi <= n ( n la sô
̃ ượ
̣
đinh)
̉ ̣ ̣ ̀ ́
Co thê co nhiêu đ
ng đi t
ườ
ừ
̉
́ ̉ ́ ̀ ́
S đên f nh ng thuât toan DFS luôn tra vê môt đ
điên nho nhât.
ng đi co th t
t
́ ứ ự ừ
ư ườ
̣ ́ ̃ ̀ ̣
̉ ̉ ́
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
́ ̀ ̀ ́ ̀
đinh u t
ừ
̣ ́ ̣ ̀
Qua trinh tim kiêm theo chiêu sâu cho môt cây gôc s v i quan hê cha con la: ớ i thăm đinh v ( DFS(u) Nêu t ớ goi DFS(v)) thi u la nut cha cua nut v.
́ ̉ ̉
̣ ̀ ̀ ́ ̉ ́
Sau khi hoan tât thăm cây ta co môt r ng
̣ ừ
cây.
̀ ́ ́
ớ ̃ ượ
̀ ́ ̉ ́ ́ ̃ ̉ ́
́ ̣ ́ ̣ ̉ ̀ ́
Cân thiêt phai đanh dâu v i môi đinh cac c thăm va sô sô hiêu xac đinh đinh đa đ hiêu xac đinh tât ca cac đinh kê cua no đêu đa đ
̃ ượ
̣ ́ ̣ ́ ̉ ́ ̉ ̀ ̉ ́
Trong cai đăt ta s dung Stack đê ghi th ứ
c thăm. ử
̀
t
x li cac đinh.
ự ử
̀ ̣ ̣ ̉
́ ́ ̉
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
a) Tìm ki m theo chi u sâu (Depth
ề
ế first search) Graphs - Depth-First
Graph data structure
Adjacency Matrix ADT
struct t_graph { int n_nodes; graph_node *nodes; int *visited; AdjMatrix am; }
static int search_index = 0;
void search( graph g ) {
Mark all nodes “not visited”
int k;
for(k=0;kn_nodes;k++) g->visited[k] = 0;
search_index = 0;
for(k=0;kn_nodes;k++) {
Visit all the nodes attached to node 0, then ..
if ( !g->visited[k] ) visit( g, k ); }
}
Graphs - Depth-First
Adjacency List version of visit
void visit( graph g, int k ) {
AdjListNode al_node; g->visited[k] = ++search_index; al_node = ListHead( g->adj_list[k] ); while( n != NULL ) {
j = ANodeIndex( ListItem( al_node ) ); if ( !g->visited[j] ) visit( g, j ); al_node = ListNext( al_node ); }
}
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
̀ ́ ̀ ̣
b) Tim kiêm theo chiêu rông ( Breadth
First)
ơ
c ̣ ướ
̉ ̀ ̀ ̃
̃ ̣ ́ ̉ ́ ̉ ̀
c duyêt tr
ướ
̀ ̉ ̣ ̉ ̀ ́ ̀ ́ ̉ ̀
Đinh nao gân s h n se duyêt tr Sau khi đa duyêt xong tât ca cac đinh liên kê cua môt đinh nao đo thi cac đinh liên kê cua đinh nao đ c se ượ duyêt tr
c.
̣ ướ
̀ ̉ ̉ ̀ ̣ ̃
ứ
́ ̀ ̃ ́ ̉
ư
́ ̉ ̀ ́ ̣
̣ ̉ ́ ̀ ̀ ̣ ̣ ́
Qua trinh trên se châm d t khi không thê đên thăm đinh nao n a, khi đo lai xet v i ́ ớ ữ môt đinh bât ki ch a thăm va lăp lai qua trinh trên cho đên khi tât ca cac đinh đêu đa đ
c thăm.
̃ ượ
̀ ́ ́ ̉ ́ ̉ ̀
ƯƠ
CH Ồ 4. Các thu t toán tìm ki m trên đ th ồ ị
NG IX: Đ TH Ị ế
ậ
S
b) Tim kiêm theo chiêu rông ( Breadth First) ̀ ́ ̀ ̣
Graph - Breadth-first Traversal
…
x1
x2
xp
• Breadth-first requires a FIFO queue
static queue q; void search( graph g ) {
…
u1
u2
uq
Phai duyet sau xp
q = ConsQueue( g->n_nodes );
for(k=0;kn_nodes;k++) g->visited[k] = 0;
search_index = 0;
for(k=0;kn_nodes;k++) {
if ( !g->visited[k] ) visit( g, k );
}
void visit( graph g, int k ) {
al_node al_node; int j; AddIntToQueue( q, k ); while( !Empty( q ) ) { k = QueueHead( q ); g->visited[k] = ++search_index; ......
2nd
4th
2
4
2
4
6
6
6th
1
7
1
7
8
8
1st
3
5
3
5
3rd
5th
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
Nhân xet
Co thê co nhiêu đ
ừ
ớ
̣ ́
i f s t ng đi it canh
ng đi t ườ
́ ̉ ́ ̀
ườ nh ng BFS luôn cho đ ư nhât.́
́ ̣
đinh u t
ớ
́ ̀ ̀ ́ ̣ ́
̣ ̉ ̉
̀ ̀ ̀ ́ ̉ ́ ́
Trong cai đăt thuân l
Qua trinh tim kiêm cho môt cây gôc s. i thăm đinh Quan hê cha-con: t ừ v thi thi u la nut cha cua v. Khi kêt thuc duyêt tao thanh môt r ng cây. ̣ ừ ̣ ợ
̣ ̣ ̀
i nhât la dung hang c thăm nh ng ̃ ượ
ư
̉ ư
̀ ̣ ́ ̀ ̀ ̀
đ i đê l u cac đinh đa đ ch a xem xet cac đinh kê cua no.
ợ ư
́ ̉
́ ́ ̉ ̀ ̉ ́
4. Các thu t toán tìm ki m trên đ th ồ ị
ế
ậ
́ ́ ̣ ̣ ̣ ́
c) Đanh gia đô ph c tap thuât toan ứ Cach biêu diên đô thi co anh h ớ
ưở ng l n đên th i ờ ́ ̉ ̃ ̀ ̣ ́ ̉ ́
̣
gian th c hiên. ự Trong tr ng h p biêu diên băng danh sach kê ườ ợ ̉ ̃ ̀ ́ ̀
ca hai thuât toan đêu co : ̉ ̣ ́ ̀ ́
O(n+m)=O(max(n,m))
ng ng la sô đinh va sô canh cua đô ươ ứ ̀ ́ ̉ ̀ ́ ̣ ̉ ̀
( n, m t thi)̣
ƯƠ
CH Ồ 4. Các thu t toán tìm ki m trên đ th ồ ị
NG IX: Đ TH Ị ế
ậ
Nêu biêu diên băng ma trân kê thi đô ph c tap se
ứ ́ ̉ ̃ ̀ ̣ ̀ ̀ ̣ ̣ ̃
O(n+n2)=O(n2) la ̀
́ ̉ ̃ ́ ̣ ̀ ̣ ̣
ữ ̀ ớ ̉ ̉ ̀ ̉ ̣ ̀
ng h p biêu
Nêu biêu diên theo danh sach canh thi viêc duyêt nh ng đinh kê v i đinh u thi phai duyêt qua toan bô danh sach canh, O(n.m). Nh vây, đô ph c tap trong tr ư
ườ
ợ
̣ ́ ̣
ứ diên băng danh sach kê la tôt nhât
̣ ̣ ̣ ̉
̃ ̀ ́ ̀ ̀ ́ ́
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
́ ̃ ̣ ̀ ̣ ̣ ́ ̀ ́ ̀ ̀ ̣ ̣
Ta gan môi canh đô thi môt sô nao đo thi đô thi goi la co trong sô. Sô gan đo goi la trong sô cua canh. ng biêu diên đ th này băng ma trân trong sô
̀ ́ ̣ ́ ́ ́ ́ ̣ ̀ ̣ ́ ̉ ̣
Th T
ồ ị ườ ̉ ̃ ̀ ̣ ̣ ́
T[i,j]= trong sô cua canh (i,j). T[i,i]=0 v i moi i
ớ
̣ ́ ̉ ̣
T[ij]= môt sô nao đo đê đanh dâu la không co canh (i,j), vi
̣
du la +∞ chăng han.
̣ ́ ̀ ́ ̉ ́ ́ ̀ ́ ̣ ́
̣ ̀ ̉ ̣
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
Bai toan:
ng đi ngăn nhât t
Cho môt đinh xuât phat s, va ́ ừ
ườ
̀ ́ ̣ ̉ ́ ́ ̀
đinh kêt thuc f, tim đ s đên f.
̉ ́ ́ ̀ ́
Nêu không co đ
ng đi t
s đên f thi thông
́ ườ
ừ
́
bao.
́ ́ ̀
́
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
̣ ́
ng đi ngăn nhât ̀ ườ ̃ ̉ ́ ̣ ̃ ́ ́
a) Thuât toan E. Dijkstra Môi đinh v gan môt nhan d[v] la đ
́
t s đên v. ừ B c kh i tao ở ướ ̣
d[s]=0 va d[v]= +∞ v i moi v <>s Nhãn co hai trang thai:
ớ ̀ ̣
́ ̣ ́
thay đôi: con co thê tôi u h n ơ c tôi u. xac đinh: đa đat đ ́ ư
́ ư ̉ ̀ ́ ̉
Co thê dung cach đanh dâu: free[v]= true hay
̣ ượ ́ ̣ ̃
́ ̉ ̀ ́ ́ ́
false t ng ng la thay đôi hay xac đinh. ươ ứ ̀ ̉ ́ ̣
ƯƠ
NG IX: Đ TH Ị
CH 5. Bài toán tìm đ
Ồ ng đi ng n nh t ấ ắ ườ
Dijkstra’s Algorithm - Operation
• Initialise d and p
• For each vertex, j, in V
• dj = ¥ • p
Initial estimates are all ¥ No connections
j = nil
• Source distance, ds = 0
• Set S to empty • While V-S is not empty
Add s first!
• Sort V-S based on d • Add u, the closest vertex in V-S, to S • Relax all the vertices still in V-S connected to u
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
Dijkstra’s Algorithm - Operation
• Initial Graph
Source
Red arrows show pre-decessors
̣ ́
a) Thuât toan E. Dijkstra B c lăp ướ
Trong sô cac đinh thay đôi chon đinh u ma
̣
d[u]= nho nhât va xac đinh u;
́ ́ ̉ ̉ ̣ ̉ ̀
S a nhan tât ca cac đinh thay đôi v va s a
̀ ữ
ữ
̉ ́ ̀ ́ ̣
theo công th c:ứ
̉ ́ ̉ ́ ̉ ̉
d[v] = min ( d[v], d[u]+c[v,u])
B c lăp se kêt thuc khi f đ
c gan nhan
ướ
ượ
xac đinh.
̣ ̃ ́ ́ ́ ̃
Nêu cac nhan thay đôi đêu co d[v] =+∞ thi
́ ̣
kêt luân không co đ
ng đi t
s đên f.
́ ườ
ừ
́ ́ ̃ ̉ ̀ ́ ̀
́ ̣ ́
Dijkstra’s Algorithm - Operation
Source is now in S
Sort vertices and choose closest
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
̣ ́
a) Thuât toan E. Dijkstra B c lăp ướ
̣
Dijkstra’s Algorithm - Operation
Change u’s pre-decessor also
Source is now in S
Relax y because a shorter path via x exists
Dijkstra’s Algorithm - Operation
S is now { s, x }
Sort vertices and choose closest
ƯƠ
NG IX: Đ TH Ị
CH 5. Bài toán tìm đ
Ồ ng đi ng n nh t ấ ắ ườ
̣ ́
a) Thuât toan E. Dijkstra B c lăp ướ
̣
Dijkstra’s Algorithm - Operation
S is now { s, x, y }
Sort vertices and choose closest, u
Dijkstra’s Algorithm - Operation
S is now { s, x, y, u }
Finally add v
B c lăp se kêt thuc khi f đ
c gan nhan
ướ
ượ
xac đinh.
̣ ̃ ́ ́ ́ ̃
Nêu cac nhan thay đôi đêu co d[v] =+∞ thi
́ ̣
kêt luân không co đ
ng đi t
s đên f.
́ ườ
ừ
́ ́ ̃ ̉ ̀ ́ ̀
́ ̣ ́
Dijkstra’s Algorithm - Operation
S is now { s, x, y, u }
Pre-decessors show shortest paths sub-graph
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
̣ ́
a) Thuât toan E. Dijkstra B c k t h p
ướ
ế ợ ́ ư
Lây vêt l u trong qua trinh s a nhan cho ữ c hoăc thông
ng đi ngăn nhât tim đ
ườ
́ ́ ̀ ̃
đ bao không tôn tai đ
ượ ng đi (d[f]= +∞).
̣ ườ
́ ́ ̀ ̣
́ ̀
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
̣ ́
a) Thuât toan E. Dijkstra Đ ph c t p thu t toán
ộ
ứ ạ
c lăp.
ướ
̀ ́ ̣
́ ̉ ́ ̣ ̣ ̉ ̣
ậ Dung không qua (n-1) b Co thê xac đinh môt đinh không thuôc D c k dung không qua n-1 phep so
̣ ướ
tai b sanh́
Kêt luân đô ph c tap thuât toan la O(n
2)
ứ
̀ ́ ́
́ ̣ ̣ ̣ ̣ ́ ̀
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
̣ ́
b) Thuât toan Floyd
́ ướ
́ ớ
̀ ̣ ́ ̣ ̉
́ ừ
ớ
̀ ̣ ̃ ̀ ́ ̉ ̀ ̉
ng , co trong sô v i n đinh Cho đô thi co h va m canh. Hay tim tât ca d(u,v) la khoang u đên v v i moi căp đinh cach ngăn nhât t (u,v).
́ ́ ́ ̣ ̣ ̉
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
ừ ̣ ̣ ́ ́ ̣ ́ ̀
T ma trân trong sô TS tinh lai cac ts(u,v) thanh ớ
đô dai ngăn nhât t u t ́ ừ ̣ ̀ ́
c xet theo th t t i v. V i moi đinh k cua đô thi đ ̣ ượ ứ ự ừ ̣ ̉ ̉ ̀ ́
C c tiêu hoa ts(u,v) theo công th c:
i n, xet moi căp u,v. ́ ̣ ̣
ứ ớ 1 t ớ ự ̉ ́
Ts(u,v)= min {ts (u,v), ts(u,k) +ts (k,v)}
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
Gia thiêt ta đa xây d ng ts
k-1 (u,v) khi đo ́
ự ̉ ́ ̃
c xac đinh: ượ ́ ̣
i v chi đi qua cac đinh ng đi ngăn nh t u t ườ ấ ớ ́ ́ ̉ ́ ̉
̣ ̣ ̀
tsk (u,v) đ Nêu đ trung gian thuôc tâp 1,2,…,k ma: Không đi qua đinh k ( chi đi qua cac đinh trung ̉ ̉ ́ ̉
̣ ̣
gian thuôc tâp 1,2,…k-1) thi: (u,v) = tsk-1 (u,v) tsk
Co đi qua đinh k thi đ
̀ ườ u đên k va t
ừ
́ ̉ ́ ̃ ́
ng đi đo se nôi hai k đên v ma hai ng đi t ̀ ừ ng đi sau chi ch a cac đinh thuôc tâp
ứ
ườ ườ
́ ́ ̀
đ đ 1,2,…k-1:
Tsk(u,v)=Tsk-1(u,k) + Tsk-1 (k,v)
̉ ́ ̉ ̣ ̣
5. Bài toán tìm đ
ườ
ng đi ng n nh t ấ ắ
̣
́ ́ ̉ ̀
D a trên nguyên li tôi u; nêu đinh k năm trên ́ ư i đên j thi cac đoan đ ừ
ng t ́ ừ ườ ́ ́ ̀ ́ ̣
Viêc cai đăt thuât toan Floyd rât dê dang ( 03 vong
đ i t ng đi ngăn nhât t k t i k va t i j la ngăn nhât. Nhân xet ́ ự ườ ớ ̀ ừ ớ ̀ ́ ́
̣ ̀ ̣ ̣ ́ ́ ̃ ̀ ̀
Do cach biêu diên băng ma trân kê nên khi n đu l n
For lông nhau). ̀
̉ ớ ́ ̉ ̃ ̀ ̣ ̀
Đô ph c tap thuât toan la O(n
3).
thi se găp kho khăn vê không gian nh . ớ ̀ ̃ ̣ ́ ̀
ứ ̣ ̣ ̣ ́ ̀
6. Bài toán cây khung
Đinh nghia
ướ
̣ ̃
̀ ̣ ̀ ̀ ̣
́ ̀ ̣ ̉
ng liên thông
ướ
ớ
́ ̣ ̀ ̉
Cho đô thi G=
́ ̣ ́ ̀ ̣
́ ̉ ́ ̀
G
T1
T2
T3
ƯƠ
NG IX: Đ TH Ị
Ồ
CH 6. Bài toán cây khung
a) Thuât toan h p nhât
ợ
̣ ́ ́
̃ ̉ ̀ ̣ ̀ ̣
́ ́ ̣ ́ ́ ̀
Môi đinh đô thi coi la môt cây. Nêu co canh nôi hai cây khac nhau thi bô sung canh đo vao cây cho đên khi c. đu n-1 canh la đ
̀ ượ
̉ ̣ ́ ̀ ́
̉ ̣
b) Thuât toan ap dung DFS va DBS
̣ ́ ́ ̣ ̀
̉ ̣ ́ ̀ ̣ ̃ ̉
́ ̣ ̀ ̀ ́ ́ ́
Ca hai thuât toan đêu duyêt môi đinh đung môt lân va nêu ta ghi dâu vêt đi qua cac canh nao thi bô sung cac c cây khung. canh đi qua đo la co đ
́ ượ
́ ̣ ̀ ̀ ̉ ́
̣ ́ ̀
1
1
3
3
2
2
5
4
6
7
6
7
5
4
9
8
9
8
10
11
10
11
6. Bài toán cây khung
̣ ́
̣ ́ ̉ ̣ ̀ ̉ ̣ ́ ́ ̉ ́ ̣
c) Thuât toan J.Kruskal Trong sô cua môt cây la tông trong sô tât ca cac trong ́. Cây khung co trong sô nho
́ ́ ̣ ̉ ́ ̣ ́ ̉
́ ̣ ̀ ̉
ở ̣ ̃ ̀ ̉
. Kh i tao n cây ,môi cây la 1 đinh. . Xet tât ca cac canh t ừ ́ ́ ̉ ́ ̣ ̣ ́ ̉ ́ ́
́ ́ ̣ ́ ̀ ̀ ̣
sô cac canh cua cây đo ́ . nhât goi la cây khung nho nhât B c 1 ướ trong sô nho nhât đên B c 2 ướ l n nhât. Nêu thêm canh đo vao ma không tao ớ thanh chu trinh thi thêm canh đo vao cây. ̀ ̀ ̀ ̣ ́ ̀
B c 3. Lăp lai b ướ ̣ ướ ̣ ́ ̉ ̣
ớ ̣ ́ ̣ ̣ ̀ ̀ ̃ ́
̀ ́ ̀ ̀ ̣
c 2 cho đên khi đu n-1 canh hoăc khi kêt nap thêm canh m i vao đêu dân đên la luôn co chu trinh, đô thi không liên thông, không tôn tai cây khung. ̀ ̣
Nhân xet
Khi cai đăt cân săp xêp danh sach canh theo th t
̣ ́
ứ ự ̀ ̣ ̀ ́ ́ ́ ̣
không giam cua trong sô. ̉ ̉ ̣ ́
́ ̣ ̣ ̀ ̉ ̀
̀ ̀ ̣ ̉ ́ ́
́ ̉ ̀ ̀ ̣ ̀ ̣ ̀ ̃ ̣
Muôn thêm môt canh (u,v) vao cây đê không thanh chu trinh thi canh (u,v) phai nôi hai cây khac nhau ( nêu ca u va v đêu thuôc cung môt cây thi se tao thanh chu trinh). Nh vây ban đâu co n cây sau môi b
̀ ̀ ̣ ̀ ́ ̃
ư c h p nhât hai cây thanh môt cây. ướ ́ ̀ ̣
ợ ứ ̣ ̣ ̣ ̣ ̀ ̣ ́ ́ ́
Đô ph c tap phu thuôc vao thuât toan săp xêp danh sach canh, vi du s dung Heapsort co đô ph c tap la O(mlgn).
̣ ử ứ ́ ̣ ́ ̣ ́ ̣ ̣ ̀
6. Bài toán cây khung
̣ ́
́ ̣ ̀ ̣ ̀ ̣ ̉ ̣
d) Thuât toan R. Prim Xet môt cây T trong đô thi G va môt đinh v, goi i T la trong sô nho ́ ừ
̉ ́ ́ ̀ ̣ ́ ̉
v t ớ ớ ́ ́ ́ ̣ ́
d[v] = min{ ts[u,v] v i moi u thuôc T} khoang cach ngăn nhât t nhât trong sô cac canh nôi v v i T: ớ ̣ ̣
ở ̣ ̉ ̀ ̣ ̉
Kh i tao T chi gôm môt đinh. Chon đinh gân T nhât va kêt nap đinh đo B c 1. ướ B c 2. ướ ̣ ̉ ̀ ́ ̀ ́ ̣ ̉ ́
va canh co khoang cach ngăn nhât vao T. ̀ ̣ ́ ̉ ́ ́ ́ ̀
Lăp lai b B c 3. ướ ̣ ướ ̣ ́ ̣ ̀
̃ ́ ̉ ̉ ̣ ̀ ́ ̉ ̀ ̣ ́
ườ ̉ ́ ́ ̀ ̀ ̀
c 2 cho đên khi hoăc cây T la cây đa co đu n đinh hoăc la cac đinh con lai co khoang cach đên T đêu la vô cung. Tr ng h p nay xây ra khi đô thi không liên thông. ợ ̀ ̉ ̀ ̣
Nhân xet ứ
̣ ́
̣ ̣ ̣ ́ ̀
́ ợ ́ ̉ ̣ ́ ̣
Đô ph c tap thuât toan R Prim la O(n 2) Co thê kêt h p thuât toan R. Prim v i viêc s ử ớ dung câu truc Heap, khi đo đô ph c tap la ứ O( (m+n)lgn)
Khi đô thi day thi nên dung thuât toan R. Prim
̣ ́ ́ ́ ̣ ̣ ̀
̀ ̣ ̀ ̀ ̀ ̣ ́
7. Tính liên thông c a đ th ồ ị
ủ
Đ nh nghĩa
ị
̀ ̣ ̣ ̀ ́ ̀ ̣
ữ ườ ̉ ́ ̀ ̉ ́ ̀ ̣
̀ ợ ̀ ́ ̃ ̉
ừ ̀ ̀ ̣ ́ ̀ ̣
Đô thi G=
G1
G2
G3
7. Tính liên thông c a đ th ồ ị
ủ
Đinh nghia ̣ ̃
̉ ớ ̣ ̀ ̣ ̀ ̉ ̀ ̣ ̀ ̣
Môt đô thi đây đu v i n đinh la môt đô thi vô ng ma gi a hai đinh bât ki cua no đêu co ướ ̀ ữ ̉ ́ ̀ ̉ ́ ̀ ́
̣ ́
ườ ự ̀ ̣ ̀ ̣
ượ ́ ̣ ̉ ̀ ́
ữ ữ ̣ ́ ̀ ̉ ̀ ́
h
canh nôi.
i ta xây d ng đô thi G’=
Nhân xet:
̣ ́
Môt đô thi đây đu la liên thông. Môt đ n đô thi vô h
̣ ̀ ̣ ̀ ̉ ̀
ng la liên thông nêu va ướ ơ ̣ ̀ ̣ ̀ ́ ̀
Môt đ n đô thi vô h
chi nêu bao đong cua no la đô thi đây đu ̉ ́ ́ ̉ ́ ̀ ̀ ̣ ̀ ̉
̣ ơ ướ ̀ ̣ ́ ̀ ̀
́ ̀ ̉ ́ ́ ̉ ́ ́
ng co k thanh phân liên thông nêu va chi nêu bao đong cua no co k thanh phân đây đu. ̀ ̀ ̀ ̉
Thuât toan Warshall (1959) ớ
̣ ́
ướ ̀ ̣ ̣ ̉ ́
ớ ́ ́ ̉ ́ ̣ ̉
́ ́ ̀ ̣ ̣ ́ ̀ ̣ ́
ng G, v i moi đinh k xet theo V i đô thi vô h ớ th t 1 đên n, v i tât ca cac căp đinh (u,v) t ứ ự ừ nêu co tôn tai canh nôi (u,k) va canh nôi (k,v) nôi thêm canh (u,v) nêu ch a co. thi ta t ư ự ̀ ́ ̣ ́ ́
NG X: CÁC K THU T
Ậ
Ỹ
CH THI T K THU T TOÁN
ƯƠ Ế
Ậ
Ế
ươ ươ
1. Ph ng pháp duy t ệ 2. Ph ng pháp ăn tham 3. Chia đ tr và đ quy ể ị ệ 4. Quy ho ch đ ng ạ
ộ
Ậ Ế
ươ
CH CÁC K THU T THI T K THU T TOÁN Ế 1. Ph NG X: ƯƠ Ậ Ỹ ng pháp duy t ệ
a) Duy t tuy n tính
ế
́ ̉ ̣ ́ ́ ̀
́ ̣ ̣ ́ ́ ̣ ́ ́ ̉ ́
ệ ng chinh cua duyêt tuyên tinh la T t ư ưở “vet can” môt cach co hê thông tât ca cac kha năng co thê xây ra.
̉ ́ ̉ ̉
Duyêt toan bô
Ph
ng phap rât c ban, th
ng dung
ươ
ơ
ườ
̣ ̀ ̣
trong cuôc sông hang ngay.
́ ́ ̉ ̀
Cho phep tim ra môt nghiêm hoăc tât ca
̣ ́ ̀ ̀
cac nghiêm ( nêu co).
́ ̀ ̣ ̣ ̣ ́ ̉
Vi du thuât toan tim kiêm tuân t
̀ ự
́ ̣ ́ ́
ta đa s ̃ ử sô hang th nhât
t t
ứ
̀ ượ ừ
́ ̣ ̣ ́ ̀ ́
dung duyêt lân l cho đên sô hang sau cung.
̣ ̣ ́ ̣ ́
́ ́ ̣ ̀
ng pháp m t l ươ
i ắ ướ ng trinh y=f(x) liên tuc trong đoan ươ ̀ ̣ ̣
̀ ̀
̣ ̀ ̣ ̀
iả : Chia đoan [a,b] thanh n đoan băng nhau c epx đu nho đê f(x)=0 v i moi x ma |x- ướ ớ ́ ́ ̉ ̉ ̉ ̣ ̀
́ ̣ ́ ̣ ̀
đo x =(x
b) Ph Vi d́ ụ: cho ph [a,b], cân tim x trong đoan [a,b] sao cho f(x)=0. Cách gi co kich th x0| < epx Nêu trong đoan [x t ừ
i)*f(xi+1) < 0, ng trinh. ươ
i,xi+1] co nghiêm thi f(x i + xi+1 )/2 se la nghiêm cua ph
́ ̃ ̀ ̣ ̉ ̀
c) Duy t phi tuy n ế ̀ ừ
ệ ư ưở
́ ̣ ̀ ́ ̉
ng chinh la t ng b ự ́ ̉ ̉ ̉ ́ ́ ́ ̀
c môt tim cac kha năng T t ướ co thê đê xây d ng theo kiêu kiên thiêt cac thanh phân cua nghiêm theo cach “ th sai”. ử ̀ ̉ ̣ ́
Tam con hâu
́ ̣
̀ ́ ́ ̣
Bai toan tam con hâu Cân đăt tam con hâu trên ban c Quôc tê sao cho c ( không co qua 1
ờ ̀ ̣ ́ ̣ ̀ ́ ́
ượ ́ ̉ ́ ́
chung không thê ăn nhau đ con hâu trên môi dong, môi côt, môi đ ng cheo). ̃ ườ ̣ ̃ ̀ ̃ ̣ ́
Tam con hâu
́ ̣
Cac con hâu đ ứ
t ́ ̣ ́ ́
c đanh sô th t ở ứ ̣ ̀ ̀ ̣ 1 đên 8. ́ ứ ự ừ i hang th i va côt th c ứ
Cân xac đinh cac gia tri cua c
ượ Con hâu i đ ng (1<=ci<=8).
1,c2,…,c8 t
̀ ́ ̣ ́ ́ ̣ ̉ ̣
̀ ́ ̀ ừ i) va (j,c tâp j)
Cac gia tri co thê tao thanh nghiêm thanh phân
{1,2,..,8} sao cho: ci<>cj va cac ô ( i, c không năm trên cung môt đ ng cheo. ̣ ườ ̀ ̀ ́
́ ́ ̣ ́ ̉ ̣ ̀ ̣ ̀ ̀
tao thanh tâp kha năng ( vi du tâp {1,2,..8}) ̣ ̀ ̣ ̉ ́ ̣ ̣
Tam con hâu
Đây la môt bai toan cô điên co t
́ ̣
́ ừ ̀ ̣ ̀ ́ ̉ ̉ ́ ̃ ̀
́ ̀ ́ ̣ ́ ̉ ́ ̣
̉ ̣ ́ ́ ́ ̣ ̀ ́
thê ki 18 ma cac nha toan hoc rât quan tâm ca hai khia canh: chi ra môt cach xêp cac con hâu va co bao nhiêu cach xêp hâu khac nhau. ́ ́ ̣ ́
Tam con Hâu
Gia s đa chon đ
́ ̣
1,c2,…,ci-1
c c ̉ ử ượ ̃ ̣
ừ ̀ ̣ ̉ ̀ ́ ̣ ́ ̉
̣ ̣ ́ ̉ ̣ ̣
ướ ̃ ̣ ́ ̣ ̀
T điêu kiên cua bai toan ta chon cac kha năng cho ci. Pham vi chon cac kha năng phu thuôc c đo.Nghiêm thanh vao c̀ 1,c2,…,ci-1 đa chon tr phân cân “th - sai” đê m rông, lăp lai qua trinh ̉ ở đo cho đên khi xây d ng xong nghiêm.
ư ̉ ̀ ̀ ̣ ̣ ̣ ́ ̀
ự ́ ́ ̣
Tam con hâu
́ ̣
Nêu không chon đ
c kha năng cho c ượ ́ ̣ ̉
ớ ư ́ ́ ̉ ́ ̉ ̃
i ( đa th ̃ ử hêt v i tât ca cac kha năng nh ng vân không i-1 thanh công thi phai “ quay lui” xây d ng lai c băng cach “th -sai v i cac kha năng con lai. ớ
ự ̀ ̀ ̉ ̣
̀ ́ ́ ̉ ̀ ̣
i-1 đa th hêt ma
́ ́ ̉ ́ ̉ ̉ ́ ̀
i-2 ...
Qua trinh trên đ
không chon đ c c ử Nêu tât ca cac kha năng cua c ượ ự ̣ ̀ ̉ ̣
ượ ́ ̀ ̣ ̣ ́ ̣
̉ ̣ ̀ ̀ ̣ ̀ ́
̃ ử i thi phai xây d ng lai c c lăp lai cho đên khi hoăc xây d ng đu n nghiêm thanh phân hoăc bai toan trên th c tê không co nghiêm. ự ự ́ ́ ̣
c1 c2 c3 c4 c5 c6 c7 c8
Tam con hâu
x
x
x
x
x
x
x
x
́ ̣
Nhân xet Th c chât la ta đa chia bai toan thanh cac bai toan ự
̣ ́
́ ̀ ̃ ̀ ́ ̀ ́ ̀ ́
thanh phân va mô ta d i dang đê quy. ̉ ướ ̀ ̀ ̀ ̣ ̣
ự ̀ ̉ ́ ́ ́ ̣ ̀
Do s bung nô cac phep toan (dang cây) nên tuy ng phai tim cach phat hiên c ma không cân th sai đê
̀ ̣ ̀ ́ ̉ ̀ ́ ́ ̣
ườ ́ ướ ử ́ ̀ ́ ̉ ̀ ̀ ̉
điêu kiên bai toan th cac điêu co thê biêt tr giam b t s bung nô phep toan. ớ ự ̉ ̀ ̃ ́ ́
Nhân xet
Vi du,
̣ ́
̣ ở ́ ̃ ̀ ́ ̉ ̀ ́ ̉
ở ̉ ̣ ̣ ̃ ̀ ̀
̣ ở ́ ̉ ̣ ́ ̣ ̀ ̣ ́ ̃ ́
̣ ̀ ̀ ́ ̣ ́
̉ ự ̀ ̀ ̉ ́ ̉ ́ ̣
môi hang co thê xem đêu co 8 kha năng môi hang, không cân đê đăt hâu. Tuy nhiên cac côt ma tai đo đa co con thiêt phai đăt hâu hâu trên hang nao đo tr c đo. Do vây, khi xet ́ ướ hang i thi chi co (8-i+1) kha năng co thê l a chon đê th –sai ma thôi. ̉ ử ̀
Nhân xet
̣ ́
́ ̀ ̉ ̀ ̀ ̣ ̣ ̉ ̀
́ ̀ ́ ́ ̉ ̣ ̀ ̣ ́
̉ ̣ ̀ ́ ̉ ̉ ̀ ̉ ̉
Nêu yêu câu chi cân tim ra môt nghiêm cua bai toan thi không nhât thiêt phai “ duyêt toan bô” cac kha năng. Viêc lam đo chi xây ra khi đoi hoi phai đ a ra tât ca cac nghiêm hoăc khi đê khăng đinh bai toan không co nghiêm
ư ́ ̉ ́ ̣ ̣ ̉ ̉ ̣
̀ ́ ́ ̣
Ậ Ế
ươ
Th
NG X: CH ƯƠ CÁC K THU T THI T K THU T TOÁN Ế Ậ Ỹ ng pháp tham ăn 2. Ph
ườ ̀ ̉ ̉ ́ ̀ ́
̉ ượ ̃ ́ ́ ́ ̀ ́
ng dung đê giai cac bai toan tôi u theo c d ữ ướ ng phap ́ ư c ma do kich th ươ ́ ớ ̣ ̉ ́ ̀ ́
̣ ̀
nghia tôt nhât co thê đ liêu qua l n không giai quyêt băng ph duyêt toan bô đ c. ̣ ượ Đô ph c t p cua nhiêu bai toan tôi u noi ạ ́ ư ứ ̣ ̉ ̀ ̀ ́ ́
chung la ham mu. ̀ ̀ ̃
́ ư ̀ ư ̀ ̉ ́
Yêu câu tôi u đôi khi không phai la u tiên băt buôc ma yêu câu chi cân co nghiêm gân tôi u châp nhân đ
́ ư ̣ ̀ ̀ ̉ ̀ ́ ̣ ̀
c. ượ ́ ̣
Ăn tham
́ ̣ ̀ ̣ ̣ ̉ ̣ ̀ ́ ̀
Vi du, cân chon B tâp con cua tâp A ma cac phân tâp B thoa man môt sô tinh chât nao đo. Tâp c goi la nghiêm châp nhân
̣ ̉ ̃ ̣ ́ ́ ́ ̀ ́ ̣
ượ ư ̣ ̣ ̀ ̣ ́ ̣
t ử con B nh vây đ đ c. ượ
ớ ́ ́ ̣ ́ ̣ ̀ ̣ ̀ ̣
Găn v i cac nghiêm châp nhân la môt ham muc tiêu. Nghiêm tôi u la nghiêm châp nhân co gia tri ham muc tiêu tôt nhât.
́ ư ̣ ̀ ̣ ́ ̣ ́ ́ ̣
̀ ̣ ́ ́
Ăn tham
ự ở ̣ ̀ ́ ́ ̣ ̀ ̣
c, chon môt phân t ̀ ử ợ ̃ ướ ̣ ̃ ̣ ̣ ̣ ́
́ ̉ ̣ ̉ ́ ̣ ̀ ̣ ̀ ̣ ̀
L a chon d a trên tiêu chi cho tr
Xây d ng tâp B băng kiên thiêt, kh i tao B la môt “h p li tâp rông. Tai môi b nhât” cua tâp A đê kêt nap vao tâp B va loai phân đo ra khoi tâp A. t ử ự
́ ̉ ̣
ướ ự ̣ ́ ̣
c. Viêc m ở m i vao ̀ ử ớ ̣ ̃ ́ ́ ̣ ̀
rông B se kêt thuc khi thêm môt phân t B thi no không con thoa man tiêu chi n a. ́ ữ ̀ ́ ̀ ̉ ̃
Ăn tham
Co hai vân đê giai quyêt:
́ ́ ̀ ̉ ́
1. Xây d ng cach chon theo kiêu ăn tham. 2. Xây d ng câu truc tôi u
́ ̣ ̃
ự ự ́ ư ́ ́
Ậ Ế
ươ
NG X: CH ƯƠ CÁC K THU T THI T K THU T TOÁN Ế Ậ Ỹ ng pháp tham ăn 2. Ph
̀ ́ ́ ̣
ử ̀ ̣ ̣ ̀ ̣
̀ ̀ ̣ ̃ ̉ ̉ ̣ ̣
̣ ̣ ̉ ́ ̣
i va kêt thuc la f
́ ̀ ̀ ́ ́ ̀ ̀ ̉ ̃
ờ ̣ ̣ ̉
̀ ̉ ́ ̣
Bai toan x li công viêc ử Cho CV={1,2,…N}. la tâp N công viêc cân s dung tai nguyên, ma tai môi th i điêm chi phuc vu cho ờ môt công viêc. Gia thiêt, công viêc i co th i gian băt đâu s i <= fi. Th i gian th c hiên công viêc la n a khoang th i ờ ự gian [si, fi) va gia thiêt hoăc s
j>=fj.
́ ờ i va thoa man s ̀ ữ i=>fj hoăc ṣ
Yêu câu la chon công viêc đ a vao s dung sao
ử ư ̀ ̀ ̣ ̣ ̀ ̣
Không mât tinh tông quat ta gia thiêt f
cho cang nhiêu công viêc cang tôt. ̀ ̀ ̣ ̀ ́
1<=f2<=…
́ ́ ̉ ́ ̉ ́
<=fn
2. Ph
ng pháp tham ăn
ươ
̀ ́ ̣
Tai môi th i điêm đang xet, chon cai tôt. Vi f
Bai toan x li công viêc (i) Xây d ng l a chon theo kiêu ăn tham. ́ ử ự ự ̣ ̃
ờ ̣ ̃ ̉ ́ ̣ ́ ́ ̀ 1 la ̀
̉ ́ ̣ ̣ ́ ́ ́
Viêc l a chon bây gi
ư ̣ ̀ ̣
ướ ng t c tiên. ự nh bai ư ̣ ự ̣ ̃ ̀
́ ́ ́ ̣ ́
nho nhât ( viêc môt kêt thuc s m nhât) nên ta ớ chon CV1 đ a vao th c hiên tr ự cung t ươ ờ toan xuât phat nh ng chi l a chon trong sô (n-1) ̉ ự ư công viêc con lai. ̣ ̀ ̣
Ăn tham
(ii) Xây d ng câu truc tôi u.
Nghiêm tôi u cua bai toan ch a nghiêm tôi u
́ ư ự ́ ́
́ ư ́ ư ứ ̣ ̉ ̀ ́ ̣
Thuât toan:
cua bai toan con. ̉ ̀ ́
̣ ́
́ ̀ ́ ́
́ ̀
B c 1. CV:=[1]; B c 2. j:=1; i:=1; B c 3 Nêu i> N đ a ra CV va kêt thuc; ư B c 4. i:=i+1; B c 5. Nêu si >= fj thi { CV:= CV+[i]; j:=i} B c 6. Quay lai b ̣ ướ
c 3. ướ ướ ướ ướ ướ ướ
Ậ Ế
ươ
NG X: CH ƯƠ CÁC K THU T THI T K THU T TOÁN Ế Ậ Ỹ ng pháp tham ăn 2. Ph
0
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
si
fi
1
4
1*
x
x
x
3
5
2
0
6
3
5
7
4*
x
x
3
8
5
5
9
6
6
10
7
8
11
8*
x
x
x
8
12
9
2
12
10
12
14
x
x
11 *
Bai toan x li công viêc ́ ử ̀ ́ ̣
2. Ph
ng pháp tham ăn
ươ
Nh n xét ậ
̣ ̉ ̀ ́ ́
̣ ̀ ̣ ̃
Nghiêm cua bai toan noi chung không cho nghiêm tôi u toan cuc. Tuy nhiên cung không it tr ́ ườ Môt sô tr
́ ư ́ ̣
́ ư ng h p no cho nghiêm tôi u. ợ ́ ườ ng h p ng ợ ự ̣ ̀ ́
ớ ̣ ́ ̃ ́
̣ ̣ ̀ ́ ́ ́
i ta tim cach xây d ng ườ l a chon ăn tham khac nhau. V i môi cach cho ự môt nghiêm tôi u gân đung. Trong sô cac nghiêm tim đ ́ ư c đo chon nghiêm tôt nhât. ượ ̣ ̀ ́ ̣ ̣ ́ ́
3. Chia đ tr và đ quy ể ị
ệ
Gi
i thi u ớ ệ
c Chia-Đê- Tri môt cach ́ ượ ́ ̉ ̉ ̉ ̣ ̣ ́
Co thê hiêu chiên l đai thê nh sau: ư ̣ ̉
ứ ̀ ́ ́ ́ ̣ ́
Chia: Chia bai toan xuât phat, ph c tap, co c Input l n thanh cac bai toan con c Input nho h n. nh ng co kich th ướ
ớ ́ ̀ ́ ̀ ́
kich th t ng t ươ ướ ự ̉ ơ ư ́ ́
Chia-Đê- Tri
̉ ̣
̣ ̉ ́ ̀ ́ ̀ ̣ ́
ướ ̣ ̣ ́ ̀
́ ̣ ̀ ̉ ̉ ̣ ̃
c l ươ ờ ̀ ̣ ̉
́ ̣ ̣ ́ ̀
́ ợ ́ ̉ ̣ ̀ ́
Tri: Giai cac bai toan con băng đê quy. Cac c lăp lai cho đên khi bai c Chia- Tri đ b ̣ ượ i giai hiên nhiên hoăc de toan con hoăc la co l ́ ờ i giai. dang nhân đ Kêt h p nghiêm (combaine): Nghiêm cac bai ợ toan con đ c kêt h p đê cho nghiêm bai toan ượ con l n h n va cuôi cung cho nghiêm cua bai ơ ớ toan xuât phat.
̀ ́ ̀ ̣ ̉ ̀
́ ́ ́
3. Chia đ tr và đ quy ể ị
ệ
Nhân xet
ử
̣ ́
̣ ̣ ̣
S dung công cu đê quy: rât chăt che, dê cai đăt Th
ng đoi hoi khôi l
ng tinh toan rât l n.
́ ượ
ườ
́ ớ
́ ̣ ̃ ̃ ̀ ̣
Qua trinh th c hiên Chia- Đê tri diên ra theo hai
ự
̀ ̉ ́ ́
b
c:ướ
́ ̀ ̣ ̉ ̣ ̃
Chia-Đê- Tri
̉ ̣
trên xuông”( Top- ừ ̉ ̣ ̀ ́
ờ ̉ ́ ̣ ̣ ̣
B c kêt h p nghiêm thi đi t d ướ ́ ̣ ̀
ự ̀ ̣ ́ ́
̣ ướ ợ ớ ́ ̀ ́ ̣ ̀ ́
̣ ́ ̀ ́
c l u tr nên cac b ơ ượ ư ướ ữ ́ ̀
B c chia đê tri la đi “ t ướ i goi đê quy. Down) đê xac đinh l i lên ừ ướ ợ c nay th c hiên cac tinh ( Bottom-up), tai b toan va kêt h p nghiêm cho bai toan l n h n. Do nghiêm cac bai toan con không đ c sau, khi cân s ử dung thi phai tinh lai. ̣ ̀ ̉ ́ ̣
Ậ Ế
NG X: CH ƯƠ CÁC K THU T THI T K THU T TOÁN Ế Ậ Ỹ 4. Quy ho ch đ ng ộ ạ
ị
ng dung đê a) Đ nh nghĩa Ph ươ ườ ́ ̣ ̣ ̀ ̉
ng phap quy hoach đông th giai cac bai toan tôi u co ban chât đê quy ́ ư ̉ ́ ̀ ́ ́ ̉ ́ ̣
́ ̉ ̉ ̀ ́
̀ ư ữ ̀ ̃ ̉ ́ ̉ ́ ̀ ́ ̣
́ ̉ ́ ̣ ̉ ́ ̀ ́ ̀ ̀
̣ ̣ ̀ ̀ ̉ ̉ ̣ ̀ ̉ ̀
Trong QHĐ khi không biêt phai giai bai toan con nao ta se giai tât ca cac bai toan con va l u tr lai tât ca cac nghiêm cua cac bai toan con nay va khi găp lai thi không cân phai giai lai ma chi cân s ử dung cac nghiêm đa đ ̃ ượ ư
c l u tr . ữ ̣ ́ ̣
Quy hoach đông
Bai toan co thoa man cac yêu câu:
̣ ̣
̀ ́ ́ ̃ ̃ ́ ̀
1. Bai toan phai phân ra thanh nhiêu bai toan i giai cac bai toan con đo
̀ ́ ̉ ̃ ̀ ̀ ̀ ́
́ ợ ờ ̉ ́ ̀ ́ ́
con ma s kêt h p l ̀ ự phai cho l ờ ̉ ̉ ̉ ̀
i giai cua bai toan l n. 2. QHĐ cân co bô nh đê l u tr nên phai xem ̉ ư ớ ̀ ́ ̣ ̉
3. Qua trinh t
́ ớ ữ ta co đu tai nguyên hay không. ́ ̉ ̀
ừ ́ ̀ ̀ ́ ̀ ̉ ̀
toan xuât phat phai qua h u han b bai toan c s tim ra l i giai bai ờ c. ướ ơ ở ữ ́ ́ ́ ̉ ̣
4. Quy ho ch đ ng ạ
ộ
ữ
́ ợ
ơ
ứ
́ ớ
b) Thu t ngậ ứ ̣ ́ ̀ ́ ̉ ́
̣ ̉ ̀ ̣ ̀
̀ ̉
đo giai cac bai toan l n h n goi la c s cua
i giai hiên nhiên ́ ờ ơ
̀ ơ ở
́ ớ
̣ ́ ̀ ́ ̉ ́ ̉ ̉
̉ ư
ữ
́ ̉ ́ ̀ ̣ ̉
́ ớ
ơ
̀ ̣ ́ ̀ ́
Công th c kêt h p nghiêm cac bai toan con đê co nghiêm cua bai toan l n h n goi la công th c truy hôi cua QHĐ. Tâp cac bai toan nho nhât co l đê t ̉ ừ QHĐ. Không gian dung đê l u tr nghiêm cac bai toan con dung đê tinh nghiêm bai toan l n h n goi la bang ph
ng an cua QHĐ.
ươ
̀ ̀ ́ ̣ ̀ ̣ ̀
̉ ́ ̉
4. Quy ho ch đ ng ạ
ộ
̣ ́
ơ ở ̣ ̉ ́ ̀ ́ ̀
ứ ́ ̣ ̉ ́
c) Thuât toan QHĐ B c 1: ướ cac vi tri t B c 2: ướ ng ng trong bang ph ứ ng an. ươ ự ̀ ̀ ̀ ̣
ươ ́ ̀ ́ ̉ ́ ̉
̃ ư ́ ớ ́ ̣ ̀ ́ ̉ ̀ ̣
ơ ng ng trong bang ph ́ ươ ứ ̉ ́ ́ ̣ ́
ng an đ ượ ̀ ́ ́ ̉ ́ ́
L u nghiêm cua cac bai toan c s vao ư ́ ươ Dung công th c truy hôi, d a vao nghiêm cac bai toan con đa l u trong bang ph ng an đê tinh nghiêm bai toan l n h n va l u kêt qua vao vi ̀ ư ng an. Tiêp tuc qua tri t ươ c tinh trinh đo cho đên khi bang ph ươ xong hoan toàn. ̀
D a vao bang ph ng an, truy vêt đê tim
B c 3: ướ
ự ươ ̀ ̉ ́ ́ ̉ ̀
ra nghiêm tôi u. ́ ư ̣
Vi dú
̣
̣ ́ ́ ̣
̃ ̣ ̀ ́
d) Môt sô vi du Day con đ n điêu tăng dai nhât ơ Cho A la day sô nguyên a
1,a2,….an. Môt day con cua gi ử ữ
̀ ̃ ́ ̣ ̃ ̉
n.
̀ ̣ ́ ̣ ̣ ́ ̀
.ứ ự ́ ượ ̣ ́ ̃ ̀
A la môt cach chon trong A môt sô phân t nguyên th t Nhân xet . Sô l Yêu câu. Tim day con đ n điêu tăng cua A co đô dai ng day con la 2 ơ ̀ ̀ ̃ ̣ ̉ ́ ̣ ̀
́
l n nhât. ớ Kêt luân:
̣ Đô dai xâu con dai nhât la 7 va
bao gôm cac phân t
th ̀ ử ứ
́ ̣ ̀ ̀ ́ ̀ ̀
2,3,4,7,8,9,10 nghia la day con 2,3,4,5,6,7,8
̀ ́
̃ ̀ ̃
Vi dú
̣
Ta se giai bai toan nay băng QHĐ. - Bô sung vao day 02 phân t
̃ ̉ ̀ ́ ̀ ̀
la a[0]= -∞ va ̀ ử ̉ ̀ ̃ ̀ ̀
- Khi đo day con dai nhât chăc chăn băt đâu t
a[n+1]=+ ∞
̀ ừ ́ ̃ ̀ ́ ́ ́ ́
- V i moi I 0<=i<=n+1 ta tinh đô dai L[i] - đô dai
a[0] va kêt thuc tai a[n+1] ̀ ́ ́ ̣
ớ ̣ ́ ̣ ̀ ̣ ̀
day con dai nhât băt đâu t a[i]. ̀ ừ ̃ ̀ ́ ́
Vi dú
̣
(i) C s QHĐ. ơ ở Ro rang L[n+1]=1
̃ ̀
Vi dú
(ii) Bang ph
̣
ng an. Gôm n+2 phân t ươ ̀ ử ̉ ́ ̀
́ ́ ̉ ́ ̣ ̀ ̀ ̉ ́ ̉ ́ ̣ ́
̀ ử ̀ ́ ̣ ̀ ́ ̀ ̉
đê l u ̉ ư cac kêt qua tinh đô dai dai nhât cua tât ca cac vi tri, đâu tiên ghi gia tri 1 vao phân t cuôi cung cua mang L. ̉
ứ ̀
iii) Công th c truy hôi Gia s i băt đâu t n giam môi lân 1 cho đên khi ̀ ừ ̉ ử ́ ̉ ̃ ̀ ́
Day con dai nhât t
i=0. Cân tinh L[i] khi đa biêt L[i+1],..,L[n+1]. ̀ ́ ̃ ́
́ ừ ượ ̃ ̀ ̣ ́ ̀ ̣ ̀
́ ́ ̀ ̀ ̣ ́ ̃
c thanh lâp băng vi tri a[i] đ cach ghep thêm a[i] vao đâu môt trong sô day con dai nhât băt đâu t vi tri a[j] đ ng sau a[i]. ứ ̀ ừ ̀ ́ ́ ̣ ́
Vi dú
Day nao se đ
̣
̃ ượ ̃ ̀ ̣ ̃ ̀ ̀ ̉ ́
c chon? Ro rang la chi ghep a[i] a[j] ma a[j] >a[i] va phai ̀ ừ ̀ ̃ ́ ̀ ̀ ̉
L[i] đ
vao day con băt đâu t chon day con dai nhât. ̣ ̃ ̀ ́
c tinh: Xet tât ca chi sô j trong khoang t ượ ́ ́ ́ ̉ ̉ ́ ̉
́ ̀ ̣ ̉ ́ ́
̀ ́
ừ i+1 đên n+1 ma a[j] >a[i] , chon ra chi sô jmax co L[jmax] dai nhât Đăt L[i] = L[jmax] +1 ̣
QHĐ
(iV) Truy vêt ́ -Môi lân khi gan L[i] = L[jmax] +1ta đăt T[i] =jmax a[i] co
̃ ̀ ́ ̣
̀ ừ ̉ ̉ ̀ ̃ ̀ ́ ́ ́
đê chi răng day con dai nhât băt đâu t phân t th 2 la a[jmax]. ̀ ử ứ ̀
ươ ́ ̉ ́ ̀ ̉
ng an L va bang đâu T[0] – la phân t ̀ ừ ̀ ử ́ ̃ ̃ ́ ̀ ̀
- Sau khi tinh xong bang ph ghi vêt T, day se băt đâu t c chon. tiên đ ượ T[T[0]] la phân t
̣
th 2,…. ̀ ử ứ ̀
Vi dú
I
0
1
2
3
4
6
7
8
9
10
11
5
A[i]
̣
- ∞
5
2
3
4
10
5
6
7
8
+∞
9
