TR NG Đ I H C QU C GIA HÀ N IƯỜ Ạ Ọ Ố Ộ
Đ I H C KHOA H C T NHIÊNẠ Ọ Ọ Ự
KHOA : TOÁN – C – TIN H CƠ Ọ
---------------  ---------------
TI U LU N GI A KÌỂ Ậ Ữ
Môn h c : Thi t k và đánh giá thu t toánọ ế ế ậ
Đ Tàiề : Ph ng pháp quay luiươ
Giáo viên h ngướ
d n :ẫ Nguy n Th H ng Minhễ ị ồ
Sinh viên th c hiên :ự Lê Th Ng c Ánhị ọ
Nguy n H ng Ch ngễ ồ ươ
Lê Th Hi nị ế
Tr n Th Thu H ng (4/9)ầ ị ằ
L p :ớK54A2 Toán Tin
Hà N i : 4 / 2012ộ
L I NÓI Đ UỜ Ầ
Trong quá trình nghiên c u gi i quy t các v n đ – bài toán, ng i ta đã đ a raứ ả ế ấ ề ườ ư
nh ng nh n xét nh sau:ữ ậ ư
Có nhi u bài toán cho đ n nay v n ch a tìm ra m t cách gi i theo ki u thu tề ế ẫ ư ộ ả ể ậ
toán và cũng không bi t là có t n t i thu t toán hay không.ế ồ ạ ậ
Có nhi u bài toán đã có thu t toán đ gi i nh ng không ch p nh n đ c vì th iề ậ ể ả ư ấ ậ ượ ờ
gian gi i theo thu t toán đó quá l n ho c các đi u ki n cho thu t toán khó đápả ậ ớ ặ ề ệ ậ
ng.ứ
Có nh ng bài toán đ c gi i theo nh ng cách gi i vi ph m thu t toán nh ngữ ượ ả ữ ả ạ ậ ư
v n ch p nh n đ c.ẫ ấ ậ ượ
T nh ng nh n đ nh trên, ng i ta th y r ng c n ph i có nh ng đ i m i cho kháiừ ữ ậ ị ườ ấ ằ ầ ả ữ ổ ớ
ni m thu t toán. Ng i ta đã m r ng hai tiêu chu n c a thu t toán: tính xác đ nh và tínhệ ậ ườ ở ộ ẩ ủ ậ ị
đúng đ n. Vi c m r ng tính xác đ nh đ i v i thu t toán đã đ c th hi n qua các gi iắ ệ ở ộ ị ố ớ ậ ượ ể ệ ả
thu t đ quy và ng u nhiên. Tính đúng c a thu t toán bây gi không còn b t bu c đ iậ ệ ẫ ủ ậ ờ ắ ộ ố
v i m t s cách gi i bài toán, nh t là các cách gi i g n đúng. Trong th c ti n có nhi uớ ộ ố ả ấ ả ầ ự ễ ề
tr ng h p ng i ta ch p nh n các cách gi i th ng cho k t qu t t (nh ng không ph iườ ợ ườ ấ ậ ả ườ ế ả ố ư ả
lúc nào cũng t t) nh ng ít ph c t p và hi u qu . Ch ng h n n u gi i m t bài toán b ngố ư ứ ạ ệ ả ẳ ạ ế ả ộ ằ
thu t toán t i u đòi h i máy tính th c hiên nhi u năm thì chúng ta có th s n lòng ch pậ ố ư ỏ ự ề ể ẵ ấ
nh n m t gi i pháp g n t i u mà ch c n máy tính ch y trong vài ngày ho c vài gi .ậ ộ ả ầ ố ư ỉ ầ ạ ặ ờ
Các cách gi i ch p nh n đ c nh ng không hoàn toàn đáp ng đ y đ các tiêuả ấ ậ ượ ư ứ ầ ủ
chu n c a thu t toán th ng đ c g i là các thu t gi i. Khái ni m m r ng này c aẩ ủ ậ ườ ượ ọ ậ ả ệ ở ộ ủ
thu t toán đã m c a cho chúng ta trong vi c tìm ki m ph ng pháp đ gi i quy t cácậ ở ử ệ ế ươ ể ả ế
bài toán đ c đ t ra.ượ ặ
Vét c n, quay lui ,nhánh c n .. là m t s tên g i tuy không đ ng nghĩa nh ng cùngạ ậ ộ ố ọ ồ ư
ch m t ph ng pháp r t đ n gi n trong tin h c : ỉ ộ ươ ấ ơ ả ọ Tìm nghi m c a m t bài toán b ngệ ủ ộ ằ
cách xem xét t t c các ph ng án có thấ ả ươ ể. Đ i v i con ng i ph ng pháp này th ngố ớ ườ ươ ườ
là không kh thi vì s ph ng án c n ki m tra quá l n. Tuy nhiên đ i v i máy tính, nhả ố ươ ầ ể ớ ố ớ ờ
t c đ x lí nhanh, máy tính có th gi i r t nhi u bài toán b ng ph ng pháp th sai.ố ộ ử ể ả ấ ề ằ ươ ử
Bài ti u lu n sau đây , s cho chúng ta tìm hi u rõ h n v ể ậ ẽ ể ơ ề “ Thu t toán quayậ
lui“ Vì ki n th c c a chúng em còn nhi u h n ch nên trong quá trình làm ti u lu n cònế ứ ủ ề ạ ế ể ậ
có sai sót. Mong cô và các b n , góp ý. Đ bài ti u lu n c a chúng em hoàn ch nh h n .ạ ể ể ậ ủ ỉ ơ
Chúng em xin c m n !ả ơ
M C L CỤ Ụ
I . T ng quan vổ ề
ph ngươ pháp quay lui
1 . D u hi u nh n bi tấ ệ ậ ế
2 . Ý t ng ưở
3 . Mô hình
4 . L c đượ ồ
5 . Ch ng minh tính đúngứ
6 . Nh n xétậ
7 . So sánh v i “ Vét c n , Nhánh c n“ớ ạ ậ
II . Phân tích thi t kế ế
m tộs bài toán c b nố ơ ả
1. Li t kê các dãy nh phân có đ dài nệ ị ộ
2. Phân tích số
3. Li t kê các ch nh h p không l p k ph n tệ ỉ ợ ặ ầ ử
4. Ng i bán hàngườ
5. Bài toán Balo
6. Bài toán x p H uế ậ
7. Chu trình Hamilton
III. M t s l i m cộ ố ỗ ắ
ph i ảkhi dùng ph ng pháp quay luiươ
1 . L i hay m c ph iỗ ắ ả
2 . Chú ý !
IV. T ng k tổ ế
1 . K t lu nế ậ
2 . Ph l cụ ụ
I . T ng quan v ph ngổ ề ươ pháp quay lui
1.D u hi u nh n bi t bài toán có th s d ng ph ng phápấ ệ ậ ế ể ử ụ ươ
M t bài toán li t kê t h p luôn c n ph i đ m b o hai nguyên t c, đó là: khôngộ ệ ổ ợ ầ ả ả ả ắ
đ c b sót m t c u hình và không đ c trùng l p m t c u hình. Có th nói r ngượ ỏ ộ ấ ượ ặ ộ ấ ể ằ
ph ng pháp li t kê là cách cu i cùng đ có th gi i đ c m t s bài toán t h p hi nươ ệ ố ể ể ả ượ ộ ố ổ ợ ệ
nay. M t trong nh ng ph ng pháp li t kê có tính ph d ng cao đó là ph ngpháp quayộ ữ ươ ệ ổ ụ ươ
lui.
M t s bài toàn li t kê đ n gi n :ộ ố ệ ơ ả
•Li t kê các n c Asean ( Đ ÁN : Vi t Nam , Lào , Thài Lan … )ệ ướ ệ
•Li t kê các s nh phân 3 bit ( Đ ÁN : 000 , 001 , 010 , 100 , …..)ệ ố ị
•Li t kê các s t nhiên chia h t cho 5 ( Đ ÁN : 5,10,15,20,25…..)ệ ố ự ế
•Vv …..
2 . Ý t ng c a ph ng phápưở ủ ươ
“ Quay đ u là b “ầ ờ
Nét đ c tr ng c a ph ng pháp lui các b c h ng t i l i gi i cu i cùng c a bàiặ ư ủ ươ ướ ướ ớ ờ ả ố ủ
toán hoàn toàn đ c làm th .ượ ử
T i m i b c , n u có m t l a ch n đ c ch p nh n thì ghi nh n l i l a ch nạ ỗ ướ ế ộ ự ọ ượ ấ ậ ậ ạ ự ọ
này và ti n hành các b c th ti p theo. Còn ng c l i không có l a ch n nào thích h pế ướ ử ế ượ ạ ự ọ ợ
thì làm l i b c tr c, xóa b s ghi nh n và quay v chu trình th các l a ch n còn l iạ ướ ướ ỏ ự ậ ề ử ự ọ ạ
.
Hành đ ng này đ c g i là quay lui, thu t toán th hi n ph ng pháp này g i làộ ượ ọ ậ ể ệ ươ ọ
quay lui.
Đi m quan tr ng c a thu t toán là ph i nghi nh m i b c đi qua đ tránh trùngể ọ ủ ậ ả ớ ỗ ướ ể
l p khi quay lui . D th y là các thông tin này c n đ c l u tr vào m t ngăn x p , nênặ ễ ấ ầ ượ ư ữ ộ ế
thu t toán th hi n ý thi t k m t cách đ quy.ậ ể ệ ế ế ộ ệ
3. Mô hình
L i gi i c a bài toán th ng bi u di n m t vec t g m n ph n t = ( ..)ờ ả ủ ườ ể ễ ộ ơ ồ ầ ử
Ph i th a mãn các đi u ki n nào đó. Đ ch ra l i gi i ả ỏ ề ệ ể ỉ ờ ả x, ta ph i xây d ng d n các thànhả ự ầ
ph n l i gi i .ầ ờ ả
T i b c i :ạ ướ
-Đã xây d ng xong các thành ph n ,…..ự ầ
-Xây d ng thành ph n b ng cách l n l t th c các kh năng mà có thự ầ ằ ầ ượ ử ả ả ể
ch n.ọ
•N u m t kh năng j nào đó ph h p cho thì ta xác đ nh theo kh năng jế ộ ả ủ ợ ị ả
.Th ng ph i có thêm thao tác ghi nh n tr ng thái m i c a bài toán đườ ả ậ ạ ớ ủ ể
h tr cho b c quay lui. N u i = n thì ta có đ c m t l i gi i , ng cỗ ợ ướ ế ượ ộ ờ ả ượ
l i thì ti n hành b c i+1 đ xác đ nh .ạ ế ướ ể ị
•N u không có m t kh năng nào ch p nh n đ c cho thì ta lùi l iế ộ ả ấ ậ ượ ạ
b c tr c ( b c i -1 ) đ xác đ nh l i thành ph n ướ ướ ướ ể ị ạ ầ
Đ đ n gi n , ta gi đ nh các kh năng l a ch n cho các t i m i b c là nhể ơ ả ả ị ả ự ọ ạ ỗ ướ ư
nhau , dó đó ta ph i có thêm m t thao tác ki m tra kh năng j nào là ch p nh n đ c choả ộ ể ả ấ ậ ượ
.
Hình 1.1 : Mô hình hóa ý t ngưở
4 . L c đ ph ng phápượ ồ ươ
Mô hình c a ph ng pháp quay lui có th vi t b ng th t c sau, v i n là s b củ ươ ể ế ằ ủ ụ ớ ố ướ
c n ph i th c hi n , k là s kh năng mà có th l a ch n.ầ ả ự ệ ố ả ể ự ọ
5 . Ch ng minh tính đúng c a ph ng phápứ ủ ươ
Chúng ta s ch ng minh tính đúng c a ph ng pháp b ng b t bi n vòng l pẽ ứ ủ ươ ằ ấ ế ặ
B t bi n vòng l p : D = {xấ ế ặ 1 , x2 , … , xn } – T p các c u hình.ậ ầ
Ta có 3 đi u b t bi n v vòng l p này:ề ấ ế ề ặ
1. Kh i t o :ở ạ j=1 có 1 kh năng ch p nh n đ c nghi m c a ả ấ ậ ượ ệ ủ
Bài toán luôn có nghi m. ệ
2. Duy trì : T i b c I thu t toán tìm m t giá tr cho , ghi nh n tr ngạ ướ ậ ộ ị ậ ạ
tr ng thái r i g i đ quy , đê sinh thành ph n . Khi sinh đ n thànhạ ồ ọ ệ ầ ủ
ph n c a x thì d ng l i c p nh t ph ng án t i u . N u m i khầ ủ ừ ạ ậ ậ ươ ố ư ế ọ ả
năng c a . đ u đã xét qua thì vòng for c a try(i+1) th c hi n xong. Sauủ ề ủ ự ệ
đó ch ng trình s quay v đ g i đ quy c a try (i). Tr ng thái cũươ ẽ ề ẻ ọ ể ủ ạ