Phần tích thiết kế giải thuật (phần 11)

Chia sẻ: Nguyen Kien | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

111
lượt xem 22
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu này sẽ cung cấp cho các bạn sẽ đi từng bước trong kĩ thuật duyệt đồ thị theo chiều sâu DFS, thông qua đó các bạn có thể hình dung được cách cài đặt nó trên máy tính thông quan cơ chế queue, rất đơn giản và nhẹ nhàng

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phần tích thiết kế giải thuật (phần 11)

Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 21 Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 22 11
Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 23 Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 24 12
Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 25 Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 26 13
Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 27 Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 28 14
Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 29 Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 30 15
Thuaät toaùn Depth-First Search Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 31 Thuaät toaùn Depth-First Search Meänh ñeà: Goïi G laø moät ñoà thò voâ höôùng, treân Me nh ng ñoù ta seõ thöïc hieän thao taùc DFS vôùi ñænh baét ñaàu laø s thì: 1. Pheùp duyeät seõ thaêm taát caû caùc ñænh cuøng ng thaønh phaàn lieân thoâng vôùi s. nh 2. Caùc caïnh coù nhaõn “ñaõ thaêm” seõ taïi ra moät nh caây toái ñaïi cuûa thaønh phaàn lieân thoâng chöùa nh s. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 32 16
Thuaät toaùn Depth-First Search Chöùng minh: Ch ng Khaúng ñònh 1. laø hieån nhieân vì DSF duyeät qua Kha ng taát caû caùc ñænh keà vôùi ñænh hieän haønh. (Coù theå nh chöùng minh hoaøn chænh hôn baèng phaûn ng ng chöùng). ng Khaúng ñònh 2. ñuùng do ta chæ ñaùnh daáu caùc Kha ng ng nh caïnh ñi ñeán moät ñænh môùi neân khoâng theå taïo nh ra chu trình. Nhö vaäy DFS taïo ra moät caây. Hôn nöõa, DFS thaêm taát caû caùc ñænh thuoäc thaønh phaàn lieân thoâng neân caây naøy laø caây toái nh ñaïi. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 33 Ñoä phöùc taïp thuaät toaùn Haõy nhôù raèng: Haõ ng DFS ñöôïc goïi ñuùng 1 laàn öùng vôùi moãi ñænh. DFS ng ng Moãi caïnh ñöôïc xem xeùt ñuùng 2 laàn, moãi laàn Moã nh ng töø moät ñænh keà vôùi noù Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 34 17
Ñoä phöùc taïp thuaät toaùn Vôùi nS ñænh vaø mS caïnh thuoäc thaønh phaàn lieân Vô nh nh thoâng chöùa s, moät pheùp DFS baét ñaàu taïi s seõ chay vôùi thôøi gian O(nS + mS ) neáu: Ñoà thò ñöôïc bieååu dieãn baèèng CTDL daïïng danh saùùch ñöô bie ba ng da ng sa ch keàà. ke Ñaët nhaõn cho moäät ñænh laøø “ñaõ thaêm” vaøø kieååm tra mo ñænh la va kie xem moäät ñænh “ñaõ thaêm” chöa toáán chi phí mo ñænh chö to phí O(degree). Baèèng caùùch ñaët nhaõn cho caùùc ñænh laøø “ñaõ thaêm”, ta ca ñænh la Ba ng ca ch coùù theåå xem xeùùt moäät caùùch heää thoâng caùùc caïïnh keàà vôùùi co the xe mo ca ch he ca ca nh ke vô ñænh hieään haøønh neân ta seõ khoâng xem xeùùt moäät caïïnh ñænh hie ha nh xe mo ca nh quaùù 1 laààn. qua la Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 35 Breadth-First Search Breadth (BFS ) 18
Khaùi nieäm Cuõng gioáng nhö DFS, Breadth-First Search Cuõ ng (BFS) duyeät qua toaøn boä caùc ñænh thuoäc moät thaønh phaân lieân thoâng cuûa ñoà thò vaø xaùc ñònh nh ñöôïc moät caây toái ñaïi cuûa noù vôùi moät soá thuoäc tính höõu ích: Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 37 Khaùi nieäm Ñænh xuaát phaùt s ôû möùc 0, vaø cuõng nhö trong Ñæ DFS, ñöôïc xem nhö moät ñieåm moác trong quaù trình tìm kieám. ÔÛ löôït thöù nhaát, cuoän chæ ñöôïc môû ra doïc theo chieàu daøi moät caïnh, vaø taát caû caùc ñænh keà vôùi nh ñieåm moác (caùch ñieåm moác ñuùng moät caïnh) ñeàu ch ng nh ñöôïc thaêm. Caùc ñænh naøy ñöôïc ñaët ôû möùc 1 (caùc caïnh töông Ca nh öùng cuõng vaäy) ng Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 38 19
Khaùi nieäm ÔÛ löôït thöù hai, taát caû caùc ñænh môùi caùch moác 2 ch caïnh seõ ñöôïc thaêm vaø ñöôïc ñaët ôû möùc 2 nh Qui trình naøy tieáp tuïc cho ñeán khi taát caû caùc ñænh Qui ñöôïc thaêm (ñöôïc gaùn vaøo moät möùc naøo ñoù). ). Nhaõn cuûa moïi ñænh v töông öùng vôùi ñöôøng ñi qua Nhaõ ng ng ít caïnh nhaát (ngaén nhaát) töø s ñeán v. nh Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 39 Breadth-First Search (BFS ) Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 40 20