Ch

ng 1: M

U

TS. Tr n Cao
N m 2010

1


T
•

BÀI TOÁN

N CH

NG TRÌNH

Mô hình hóa bài toán
– Xác đ nh bài toán c n gi i quy t:
•
•

ph i làm gì?
làm nh th nào?

– Hình th c hóa bài toán: phát bi u l i bài
toán th c t thành m t bài toán hình th c

– M t cách mô hình hóa là:
• M i n c nh m t đi m;
• Hai n c có chung biên gi i ta
s v m t đ ng n i hai đi m
t ng ng.

•

B n đ th gi i và m i quan h
láng gi ng gi a các n c đã
đ c bi u di n b ng m t đ th
(graph):
– m i đ nh là m t n c,
– hai n c có biên gi i chung s
đ c n i v i nhau b i m t cung.

Bài toán tô màu cho b n đ th
gi i tr thành:
•Tìm cách tô màu cho t t c
các đ nh đ th sao cho hai
đ nh có c nh n i nhau thì
ph i đ c tô b ng hai màu
khác nhau
•S màu đ c s d ng là ít
nh t.

4


Ví d 2: èn giao thông

các l i đi:

– Hai l i không th đi đ ng th i
s đ c v 1 cung n i

•

Bài toán tr thành: Tô màu lên
các đ nh c a đ th

– Các l i đi cho phép cùng đi
đ ng th i s có cùng m t màu
– Hai đ nh có c nh n i nhau s
không đ c tô cùng màu.
– S nhóm là ít nh t: s màu
đ c dùng là ít nh t.

6


Nh n xét
• Hai bài toán th c t : “tô màu b n đ th
gi i” và “đèn giao thông” xem ra r t khác
bi t nhau nh ng sau khi mô hình hóa,
chúng th c ch t ch là m t, đó là bài toán
“tô màu đ th ”.
• Nhi u bài toán cùng mô hình toán
– Gi i mô hình toán å gi i nhi u bài toán hay
gi i m t l p các bài toán


– "th t t c các kh n ng" hay
"vét c n" t t c các tr ng
h p có th có,
– ta ch có th "vét c n" trong
tr ng h p đ th có s đ nh
nh

•

HEURISTIC cho bài toán tô
màu đ th , th ng g i là gi i
thu t "háu n" (GREEDY) là:
– Ch n m t đ nh ch a tô màu
và tô nó b ng m t màu m i C
nào đó.

– Duy t danh sách các đ nh
ch a tô màu.
i v i m t đ nh
ch a tô màu, xác đ nh xem nó
có k v i m t đ nh nào đ c
tô b ng màu C đó không. N u
không có, tô nó b ng màu C
đó.

•

Ý t ng c a Heuristic này là
h t s c đ n gi n: dùng m t
màu đ tô cho nhi u đ nh nh t


DA

DB

DC

EA

EB

EC

ED

10


Greedy có cho l i gi i t i u?
• Ta có th tr l i mô hình c a
bài toán và dùng tính ch t
c a đ th đ ki m tra k t
qu . Nh n xét r ng:
– M t đ th có k đ nh và m i
c p đ nh b t k đ u đ c n i
nhau thì ph i dùng k màu đ
tô.
– M t đ th ch a k đ nh và m i
c p đ nh b t k đ u đ c n i
nhau thì ph i dùng ít nh t k

• Hình th c hoá m t gi i thu t trong thu t ng c a mô
hình đó.

– Kh i đ u là vi t nh ng m nh đ t ng quát
– tinh ch d n thành nh ng chu i m nh đ c th h n
– Cu i cùng là các ch th thích h p trong m t ngôn ng l p trình.

• Ví d : Heuristic GREEDY, gi s đ th là G, heuristic s
xác đ nh m t t p h p Newclr các đ nh c a G đ c tô
cùng m t màu, mà ta g i là màu m i C trên.
ti n
hành tô màu hoàn t t cho đ th G thì Heuristic này ph i
đ c g i l p l i cho đ n khi toàn th các đ nh đ u đ c
tô màu.

13


Th t c GREEDY v i ngôn ng gi
PASCAL
PROCEDURE GREEDY ( var G: GRAPH ; var Newclr: SET );
begin
{1} Newclr := ∅;
{2} for (m i đ nh v ch a tô màu c a G) do
{3}
if (v không đ c n i v i m t đ nh nào trong Newclr) then begin
{4}
đánh d u v đã đ c tô màu;
{5}
thêm v vào Newclr;

{4}
đánh d u v đã đ c tô màu;
{5}
thêm v vào Newclr;
end;
end;
end;

15


Ki u d li u tr u t

ng

• GRAPH và SET ta coi nh t p h p

– Có nhi u cách đ bi u di n t p h p trong
ngôn ng l p trình: xem các t p h p nh là
m t danh sách (LIST) các s nguyên bi u
di n ch s c a các đ nh và k t thúc b ng m t
giá tr đ c bi t NULL.

16


PROCEDURE GREEDY ( var G: GRAPH ; var Newclr: LIST );
var found:boolean;
v,w :integer;
begin

m t m t ng l p trình nào khác là tùy thu c vào thói
quen c a ng i s d ng, vào s quen thu c v i ngôn
ng l p trình.
18


N u ng i dùng quen thu c v i ngôn ng C có th vi t
th t c v i ngôn ng gi t a C nh sau :
void GREEDY ( GRAPH& G, SET& Newclr ){
/*1*/
Newclr = ∅;
/*2*/
for (m i đ nh v ch a tô màu c a G)
/*3*/
if (v không đ c n i v i m t đ nh nào trong Newclr){
/*4*/
đánh d u v đã đ c tô màu;
/*5*/
thêm v vào Newclr;
}
}

19


Th t c tinh ch đ

c vi t t a C nh sau:

void GREEDY ( GRAPH& G, SET& Newclr )

void GREEDY ( GRAPH& G, LIST& Newclr ){
Newclr= ∅;
int v= đ nh đ u tiên ch a đ c tô màu trong G;
while (vnull) {
int found=0;
int w=đ nh đ u tiên trong newclr;
while( wnull) && (!found)
If (có c nh n i gi a v và w) found=1;
else w= đ nh k ti p trong newclr;
if (!found) {
ánh d u v đã đ c tô màu;
Thêm v vào Newclr;
}
v= đ nh ch a tô màu k ti p trong G;
}
}
21


Tóm t t các b c ti p c n v i m t
bài toán
1. Mô hình hoá bài toán b ng m t mô hình toán h c thích
h p.
2. Tìm gi i thu t trên mô hình này.
Gi i thu t có th mô t m t cách không hình th c, t c là nó ch
nêu ph ng h ng gi i ho c các b c gi i m t cách t ng
quát.

3. Hình th c hoá gi i thu t b ng cách vi t m t th t c
b ng ngôn ng gi , r i chi ti t hoá d n ("m n hoá") , k t


ng hóa d li u

– M t ki u d li u tr u t ng
(ADT): m t mô hình toán
h c cùng v i m t t p h p
các phép toán (operator)
tr u t ng đ c đ nh
ngh a trên mô hình đó.
– Ví d t p h p s nguyên
cùng v i các phép toán
h p, giao, hi u là m t ki u
d li u tr u t ng.
– ADT là s t ng quát hoá
c a các ki u d li u
nguyên thu .

23


ADT - t ng quát hoá các ki u d li u
nguyên thu
•

Danh sách (LIST) các s nguyên và các phép toán trên danh sách
– T o m t danh sách r ng.
– L y ph n t đ u tiên trong danh sách và tr v giá tr null n u danh sách r ng.
– L y ph n t k ti p trong danh sách và tr v giá tr null n u không còn ph n t
k ti p.
– Thêm m t s nguyên vào danh sách.

•

Ki u d li u là m t t p h p
các giá tr và m t t p h p các
phép toán trên các giá tr đó.
– ki u d li u s c p: int, char
– ki u d li u có c u trúc; array,
struct.

•

C u trúc d

li u:

– Các ki u d li u có c u trúc
c b n (cung c p b i NNLT)
– các c u trúc ph c h p (đ c
t o ra t các ki u d li u c
b n)

•

M t ki u d li u tr u t ng
là m t mô hình toán h c cùng
v i m t t p h p các phép toán
trên nó.

LI U VÀ
NG