<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

TR¯àNG Đ¾I HàC DUY TÂN KHOA CƠNG NGHà THƠNG TIN

Khoa: Cơng nghá thơng tin BÁc đào t¿o: Đ¿i hác – Cao đẳng

Đà Nẵng, tháng 01 năm 2021

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

<small>Nguyễn Thị Anh Đào Trang 1 </small>

Khái niệm: Nếu 1 lái giải cÿa bài toán P đ°ợc thāc hián bằng lái giải cÿa 1 hay nhiều cÿa bài tốn P’nhỏ h¡n có d¿ng giống nh° P thì đó là một lái giải đá quy. Giải thuÁt t°¡ng āng vßi lái giải đá quy gái là giải thuÁt đá quy.

<b>Cấu trúc của giải thuật đệ quy </b>

Một giải thuÁt đá quy bao giá cũng gồm 2 phần

• Phần neo: Xác đßnh điểm kết thúc cÿa một giải thuÁt đá quy. Tr°áng hợp này còn đ°ợc gái là tr°áng hợp suy biến. Nếu một giải thuÁt đá quy khơng có tr°áng hợp suy biến thì sẽ d¿n đến lặp vô h¿n và sinh lỗi khi thi hành. • Phần đá quy: Phân tích và xây dāng tr°áng hợp chung cÿa bài tốn (có nghĩa

là đ°a bài tốn về bài tốn cùng lo¿i nh°ng vßi dÿ liáu nhỏ h¡n).

<b>Xây dÿng giải thuật đệ quy </b>

Khi cài đặt thuÁt toán đá quy ta tin hnh nhng bòc sau:

ã Bòc 1: Xỏc đßnh mục đích, đầu vào và đầu ra để từ đó xác đßnh tên tiêu đề hàm (tên hàm v tham s hỡnh thc ca nú)

ã Bòc 2: Xác đßnh tr°áng hợp suy biến (neo)

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

ã Bòc 3: Phõn tớch v xõy dng tr°áng hợp chung cÿa bài toán (phần đá quy). Có nghĩa là đ°a bài tốn về bài tốn cùng lo¿i nh°ng vßi dÿ liáu nhỏ h¡n. Từ 3 b°ßc trên, áp dụng nguyên tắc viết ngôn ngÿ ta xây dāng đ°ợc hàm đá qui (thông th°áng sử dụng toán tử điều kián (if&else) để viết hàm đá quy.

Ví dụ 1: Tính x <small>y</small>vßi x<small>y</small>đ°ợc đßnh ngha nh sau:

<small>10</small>

ã Bòc 1: Xỏc ònh tham số đầu vào là x và y, tham số đầu ra là . Ta ln nhÁn x<small>y</small>

đ°ợc giá trß x<small>y </small>duy nhất, do đó ta sử dụng hàm cú kiu tr v. ã Bòc 2: Phn neo: y=0 thỡ tng x<small>0</small> = 1

ã Bòc 3: Phần đá quy: là tr°áng hợp thāc hián l¿i bài tốn vßi giá trß nhỏ h¡n y = y - 1. Tāc là āng vßi tr°áng hợp thāc hián l¿i lái gái cũng đều có chung tham số đầu vào là y nh°ng vßi giá trß nhỏ h¡n y = y – 1 và đều có khuynh hòng n ã Bòc 1: Xỏc inh tham số đầu vào là n, tham số đầu ra là số chÿ số cÿa n. Sử

dụng hàm có kiểu trả về vì bài tốn này trả về một giá trß duy nhất là số chÿ số

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

<small>Nguyễn Thị Anh Đào Trang 3 </small>

int dem(long n) {

if(n==0) return 0;

else return (1+ dem(n/10));

Ví dụ Xuất đảo ng°ợc một số nguyên d°¡ng ra màn hình3:

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

3) Viết giải thuÁt đá quy cho bài tốn tìm số Fibonaci F(n)=F(n-1)+ F(n-2) 4) Viết giải thuÁt đá quy cho Bài toán tháp Hà Nội chuyển n đĩa từ cột A sang cột C vßi cột B làm trung gian.

− Hiáu cÿa 2 tÁp hợp: hiáu cÿa 2 tÁp hợp A B là một tÁp hợp chāa các phần \ tử thuộc A mà không thuộc B.

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

<small>Nguyễn Thị Anh Đào Trang 5 </small>

− Hợp cÿa hai tÁp hợp: hợp cÿa 2 tÁp A B là một tÁp hợp chāa các phần tử ø hoặc thuộc A hoặc thuộc B.

− Giao cÿa hai tÁp hợp: giao cÿa 2 tÁp A ÷ B là một tÁp hợp chāa các phần tử vừa thuộc A vừa thuộc B.

− Tích Đề các cÿa hai tÁp A, B là tÁp A - B = {(a,b) a A & b ỵ ỵ B}

<b>Biu din tập hợp trên máy tính: dùng mảng. </b>

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

2) Viết ch°¡ng trình kiểm tra 2 tÁp A, B có bằng nhau khơng Gợi ý: Sử dụng mảng, sắp xếp tr°ßc khi tính

3) Viết ch°¡ng trình tính hợp, giao, hiáu và tích Descartes cÿa 2 tÁp A, B. Gợi ý: Sử dụng mảng, sắp xếp tr°ßc khi tính

4) Giải quyết bài 4 vßi cấu trúc danh sách liên kết (đ¡n, đơi)

5) Viết ch°¡ng trình tính hợp, giao, hiáu và tích Descartes cÿa 3 tÁp A, B, C. Gợi ý: Sử dụng nguyên lý bù trừ

6) Viết ch°¡ng trình kiểm tra 1 phần tử x có trong tÁp hợp A khơng?

7) Viết ch°¡ng trình thêm phần tử x vào tÁp hợp A

8) Tìm phần tử bé nhất, lßn nhất trong tÁp hợp

<b>III. </b> Hệ thức truy hồi A. Lý thuyết

Định nghĩa hệ thức truy hồi: Há thāc truy hồi đối vßi dãy số {a } là cơng thāc <small>n</small>

biểu dißn a qua một hay nhiều số h¿ng đi tr°ßc cÿa dãy, cụ thể là a<small>n 1</small>, a<small>2</small>, &, a<small>n-1 </small>

vßi mái n  n<small>0</small>nguyên d°¡ng. Dãy số đ°ợc gái là lái giải hay nghiám cÿa há thāc truy hồi nếu các số h¿ng cÿa nó thỏa mãn há thāc truy hồi.

<b>Giải hệ thức truy hồi: </b>

− Bằng ph°¡ng pháp lặp. − Bằng ph°¡ng trình đặc tr°ng.

Giải hệ thức truy hồi trên máy tính: dùng giải thuÁt đá quy. Ví dụ 1: Viết ch°¡ng trình cài đặt bài toán lãi kép

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

<small>Nguyễn Thị Anh Đào Trang 7 </small>

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

1) Một ng°ái gởi ngân hàng một số tiền ban đầu P<small>0</small>=10.000 USD, lãi suất ngân hàng là 7%, hỏi sau n năm ng°ái đó có đ°ợc số tiền trong tài khoản là bao nhiêu? (n nhÁp từ bàn phím).

2) Cho các dãy số thỏa mãn há thāc truy hồi sau đây, hãy viết ch°¡ng trình A(n) để tính giá trß cÿa há thāc (n nhÁp từ bàn phím):

a. LÁp há thāc truy hồi cho dân số thế gißi n năm sau năm 2004. b. Giải há thāc truy hồi cho dân số thế gißi n năm sau năm 2004. c. Dân số thế gißi năm 2020 là bao nhiêu ?

d. Viết hàm A(n) để tính kết quả.

4) Cho dãy số {a<small>n</small>} thoả mãn há thāc truy hồi: a<small>n</small>= 5a - 6a<small>n-1n-2</small>; a =0 và a =1. <small>01</small>

a. Giải há thāc truy hồi trên. b. Viết hàm A(n) để tính a<small>n</small>.

5) Cho dãy số {a<small>n</small>} thoả mãn há thāc truy hồi: a<small>n</small>= 6a - 9a<small>n-1n-2</small>; a =1 và a =3. <small>01</small>

a. Giải há thāc truy hồi trên b. Viết hàm A(n) để tính a<small>n</small>.

6) Xây dāng há thāc truy hồi và cài đặt thuÁt tóan đá quy cho các yêu cầu sau:

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

<small>Nguyễn Thị Anh Đào Trang 9 </small>

a. Tìm số xâu nhß phân độ dài bằng 3 khơng có ba số 1 liền nhau.

b. Giả sử số vi trùng trong một quần thể sẽ tăng gấp 3 lần sau mỗi giá. LÁp há thāc truy hồi tính số vi trùng sau n giá

c. Giả sử rằng mỗi cặp thỏ trên đảo khi đ°ợc 1 tháng tuổi đẻ đ°ợc 2 cặp thỏ con và từ 2 tháng tuổi mỗi tháng đẻ đ°ợc 6 cặp thỏ con. Giả sử rằng trong thái gian thí nghiám khơng có con nào bß chết hoặc rái khỏi đảo.Tìm há thāc truy hồi cho số cặp thỏ trên đảo sau n tháng kể từ khi thả 1 cặp thỏ mßi sinh lên đảo

d. Có bao nhiêu xâu nhß phân có độ dài n và khơng chāa 2 bít 0 liên tiếp

<b>IV. </b> Bài toán liệt kê A. Lý thuyết

<b>Phương pháp sinh </b>

Ph°¡ng pháp sinh có thể áp dụng để giải bài toán liát kê tổ hợp đặt ra nếu nh° 2 điều kián sau đ°ợc thāc hián:

− Có thể xác đßnh đ°ợc một thā tā trên tÁp các cấu hình tổ hợp cần liát kê. Từ đó có thể xác đßnh đ°ợc cấu hình đầu tiên và cấu hình cuối cùng trong thā tā đã xác đßnh.

− Xây dāng đ°ợc tht tốn từ cấu hình ch°a phải là cuối cùng đang có, đ°a ra cấu hình kế tiếp nó.

Ta sẽ gái tht tốn nói trong điều kián thā 2 là thuÁt toán sinh kế tiếp. Rõ ràng là thā tā trong điều kián thā 1 cần đ°ợc lāa chán sao cho có thể xây dāng đ°ợc tht tốn sinh kế tiếp. Giả thiết rằng 2 điều kián nêu ra đã đ°ợc thāc hián, khi đó, tht tốn sinh để giải bài tốn liát kê đ°ợc mơ tả nh° sau:

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

Có nhiều tht tốn đã đ°ợc nghiên cāu để có thể t¿o đ°ợc các cấu hình tổ hợp liền kề ngay sau một cấu hình đã có. Một trong nhÿng thā tā hay đ°ợc dùng đó là thā tā từ điển, trong bài hác này chúng ta sẽ tìm hiểu về ph°¡ng pháp sinh cấu hình tổ hợp theo thā tā này.

Cho = s1 s2 ... sp và đ ị = t1 t2 ... tq là các dãy số hoặc ký tā. Ta nói rằng đ nhỏ h¡n ị (theo kiểu từ điển) , ký hiáu ñ < ò, nếu hoặc

(i) p < q và si = ti vßi mái i = 1, 2,..., p

Ví dụ Liệt kê các dãy nhị phân đß dài n: . Cho n ỵ N, hóy liỏt kờ theo th t t điển tất cả các dãy nhß phân độ dài n, tāc là các dãy b1b2b3 &bn trong đó bi {0,1} ỵ

i = 1, 2, &, n. Sẽ có tất cả 2 dãy nhß phân nh° thế, dãy đầu tiên là 00&0, và dãy <small>n</small>

cuối cùng là 11&1.

Giả sử dãy b<small>1</small>b<small>2</small>&b<small>n</small>là dãy đang có, nhÁn xét rằng nếu dãy này tồn số 1 thì chính là dãy cuối cùng cần tìm, q trình liát kê kết thúc, cịn nếu ch°a phải thì sẽ cộng thêm 1 (theo modun 2 có nhß) vào dãy đang có để nhÁn đ°ợc dãy kế tiếp. Từ đó ta có qui tắc nh° sau:

o Tìm i đầu tiên (theo thā tā i = n, n – 1, &,1) mà b<small>i</small> = 0.

o Gán l¿i b<small>i</small> = 1 và b <small>j</small>= 0 vßi tất cả j > i. Dãy mßi thu đ°ợc sẽ là dãy cần tìm. o Tht tốn:

o Đầu vào: n

o Đầu ra: Danh sách tất cả dãy nhß phân độ dài n theo thā tā từ điển tăng dần. o Các b°ßc:

1) Khởi t¿o dãy xuất phát: Gán b = 0 vßi mái i = 1, 2, .., n<small>i</small>

2) Đ°a ra cấu hình đang có.

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

<small>Nguyễn Thị Anh Đào Trang 11 </small>

5) Quay l¿i b°ßc 2.

<b>Thuật tốn quay lui </b>

Ý t°ởng chính cÿa tht tốn này là xây dāng dần các thành phần cÿa cấu hình bằng cách thử tất cả các khả năng. Giả thiết cấu hình cần đ°ợc mô tả bằng một bộ gồm n thành phần x1, x2, ..., xn. Giả sử đã xác đßnh đ°ợc i 1 thành phần x1, x2, − ... , xi-1. Ta xác đßnh thành phần thā i bằng cách duyát tất cả khả năng có thể đề cử cho nó (đánh số các khả năng từ 1 đến ni). Vßi mỗi khả năng j, kiểm tra xem khả năng j có chấp nhÁn đ°ợc khơng. Có thể xảy ra 2 tr°áng hợp:

− Nếu ch p nhấ Án j thì xác đßnh xi theo j, sau đó nếu i = n, thì ta đ°ợc mộ ất c u hình, cịn trái l i ta ti¿ ến hành xác đßnh xi+1.

− Nếu th tất cả khả năng mà không khả năng nào đ°ợử c ch p nh n thì quay l i ấ Á ¿ b°ßc tr°ßc để xác đßnh l¿i xi 1. −

Điều quan tráng cÿa thuÁt toán là phải ghi nhß, t¿i mỗi b°ßc đã đi qua, nhÿng khả năng đã thử để tránh trùng lặp. Rõ ràng nhÿng thông tin này cần đ°ợc l°u trÿ theo c¡ cấu ngăn xếp (stack vào sau ra tr°ßc). Vì thế thÿ tục đá qui rất phù hợp vßi - tht tốn này. B°ßc xác đßnh xi có thể dißn tả qua thÿ tục

Phần quan tráng nhất trong thÿ tục trên là viác đ°a ra đ°ợc một danh sách các khả năng đề cử và viác xác đßnh giá trß cÿa biểu thāc logic <chấp nhận j>. Thơng th°áng giá trß này ngồi viác phụ thuộc j còn phụ thuộc vào khả năng đ°ợc chán ở các b°ßc tr°ßc. Vì thế cần ghi nhß tr¿ng thái mßi cÿa q trình tìm kiếm sau khi

<i><xác định xi theo j> và trả l¿i tr¿ng thái cũ sau lái gái Try(i+1) </i>. Các tr¿ng thái này đ°ợc ghi nhÁn nhá một số biến toàn cục (global), gái là biến tr¿ng thái.

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

Sau khi xây dāng thÿ tục đá qui Try , ch°¡ng trình chính giải bài tốn liát kê có d¿ng :

{

Init; Try(1); }

trong đó Init là thÿ tục khởi t¿o các giá trß ban đầu (nhÁp các giá trß tham số cÿa bài toán, khởi gán các biến tr¿ng thái, biến đếm ...).

Ví dụ: Liệt kê các dãy nhị phân có đß dài n

Ta biểu dißn dãy nhß phân d°ßi d¿ng x1, x2,.. xn, trong ú xi {0,1}. Th tc ỵ Try(i) xác đßnh xi {0,1}. Các giá trß này đ°ợc mc nhiờn chp nhn m khụng cn ỵ phi tho mãn điều kián gì (vì thế bài tốn khơng cần biến tr¿ng thái).

//Ham liet ke cac day nhi phan do dai n void Nhiphan( int i)

3. Cho số nguyên d°¡ng n, liát kê tất cả các hốn vß cÿa n số tā nhiên đầu tiên 4. Cho dãy a , a<small>12</small>,&,a<small>n</small> các phần tử trong dãy khác nhau từng đôi một. Liát kê tất

các các hốn vß cÿa các giá trß trong dãy.

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

<small>Nguyễn Thị Anh Đào Trang 13 </small>

5. *Cho ph°¡ng trình x<small>1</small> + x<small>2</small> +&+x<small>n</small>= C vßi C là hằng nguyên không âm. Hãy liát kê tất các các bộ nghiám (x<small>1</small>, x<small>2</small>,&,x<small>n</small>) vßi x<small>i</small> ngun khơng âm.

6. Cho n là số quân hÁu trên 1 bàn cá vua kích th°ßc n x n. Hãy viết ch°¡ng trình liát kê tất các cách xếp các quân hÁu trên bàn cá sao cho chúng không ăn đ°ợc l¿n nhau.

7. Bài toán quân Mã: cho bàn cá vua kích th°ßc n x n. Hãy chỉ ra hành trình cÿa một quân Mã xuất phát từ ô đang đāng, đi qua tất cả các ơ cịn l¿i trên bàn cá,

Cho đồ thß G = (V, E) (vơ h°ßng hoặc có h°ßng), vßi V = {v<small>1</small>, v ,..., v<small>2n</small>}. Ma trÁn liền kề cÿa G āng vßi thā tā các đỉnh v<small>1</small>, v ,..., v <small>2n</small>là ma trÁn

A = (a ) 1 i,j n <small>ij</small>  

trong đó a là số c¿nh hoặc cung nối từ v tßi v<small>ijij</small>. Đặc điểm cÿa ma trÁn kề:

o Ma trÁn liền kề là ma trÁn đối xāng đối vßi đồ thß vơ h°ßng o Đối vßi đồ thß vơ h°ßng tổng hàng i = tổng cột i = deg(i) o Đối vßi đồ thß có h°ßng

▪ Tổng hàng i = deg (i) = số cung xuất phát từ đỉnh i<small>+</small>

▪ Tổng cột i = deg (i) = số cung vào đỉnh i<small></small>

-Trong nhiều āng dụng cÿa lý thuyết đồ thß thì mỗi c¿nh e = (u, v) đ°ợc gán vßi một con số c(e) hay c(u, v) gái là trọng số cÿa c¿nh e. Đồ thß trong tr°áng hợp này gái là đồ thị có trọng số. Trong tr°áng hợp ma trÁn có tráng số, thay vì ma trÁn kề thì để biểu dißn đồ thß ta sử dụng ma trÁn tráng số: C = c[i, j], i, j = 1, 2, &, n. Vßi c[i, j] = c(i, j) nu (i, j) ỵ E

Và c[i, j] =  nếu (i, j) ÿ E ( có thể thay bằng +, - , 0) 

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

Ví dụ:

<b>Duyệt đồ thị: 2 phương pháp Duyệt theo chiều sâu </b>

Ý t°ởng cÿa thu t tốn có th trìÁ ể nh bày nh° sau. Ta sẽ ắt đầ b u tìm ki m t m t ế ừ ộ đỉnh v<small>0 </small>nào đó cÿa đồ ß. Sau đó chán u là đỉ th nh tùy ý kề vßi v và l<small>0</small> ặp l¿i q trình đối vßi u. Tổng quát hóa, giả s ta đang xét đỉử nh v. Nếu nh° trong số các đỉnh kề vßi v tìm đ°ợc đỉnh w là ch°a đ°ợc xét thì ta sẽ xét đỉnh này (nó trở thành đã xét) và bắt đầ ừu t nó ta s ti p t c quá trình tìm ki m. Cịn nẽ ế ụ ế ếu nh° khơng cịn đỉnh nào kề vßi v là ch°a xét thì ta sẽ nói rằng đỉnh này đã dut xong, và quay trở l¿i tiếp tục tìm ki m tế ừ đỉnh mà tr°ßc đó ta đến đ°ợc đỉnh v (n u v = v thì k t thúc tìm ế <small>0 </small> ế kiếm). Độ phāc t¿p cÿa tht tốn là O(n+m).

<b>Thủ t</b>ục đệ<b> qui mơ t thu t toán DFS</b>ả ậ :

Rõ ràng l nh g i DFS(v) sá á ẽ cho phép đến thăm tấ ả các đỉt c nh thu c cùng thành ộ phần liên thơng vßi đỉnh v, bởi vì sau khi thăm đỉnh là lánh gái đến th tÿ ục DFS đối vßi t t cấ ả các đỉnh k v i nó. M t khác, do mề ß ặ ỗi khi thăm đỉnh v xong, biến Chuaxet[v] đ°ợc đặt l¿i giá trß false nên mỗi đỉnh sẽ đ°ợc thăm đúng 1 lần. ThuÁt toán lần l°ợ ẽ ết s ti n hành tìm ki m tế ừ các đỉnh ch°a đ°ợc thăm, vì vÁy, nó s xét ẽ qua t t c ấ ả các đỉnh cÿa đồ thß (khơng nh t thi t ph i là liên thông) ấ ế ả

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

<small>Nguyễn Thị Anh Đào Trang 15 </small>

Ví dụ: Xét đồ ß cho trong hình sau. Các đỉ th nh cÿa nó đ°ợc đánh số ¿ l i theo th ā tā chúng đ°ợc thăm theo thÿ tục tìm kiếm theo chiều sâu mô tả ở trên. Gi thi t ả ế rằng các đỉnh trong danh sách kề cÿa đỉnh v (Ke(v)) đ°ợc sắp xếp theo th tā ā tăng dần cÿa chỉ số.

Hình minh háa: Chỉ số mßi (trong ngoặc) cÿa các đỉnh đ°ợc đánh l¿i theo thā tā chúng đ°ợc thăm trong tht tốn tìm kiếm theo chiều sâu.

<b>Duyệt theo chiều rßng </b>

Trong thu t tốn tìm ki m theo chiÁ ế ều sâu, đỉnh đ°ợc thăm càng muộn s càng ẽ sßm trở thành đỉnh đã dut xong. Bởi vì các đỉnh đ°ợc thăm sẽ ần l°ợt đ°a vào l ngăn xếp (Stack), nên đỉnh đ°ợc thăm sau cùng sẽ đ°ợc hồn thành tr°ßc tiên. Tìm kiếm theo chiều rộng trên đồ th , nß ếu nói m t cách ngộ ắn gán, đ°ợc xây dāng dāa trên c¡ sở thay thế ngăn xếp (Stack) bởi hàng đợi (Queue). V i s c i biß ā ả ến nh° vÁy, đỉnh đ°ợc thăm càng sßm sẽ sßm trở thành đỉnh duyát xong (tāc là sßm rái khỏi hàng đợi). Một đỉnh sẽ trở thành đã duyát xong ngay sau khi ta xét xong t t c các ấ ả đỉnh kề (ch°a đ°ợc thăm) vßi nó. Thÿ t c có th mơ t ụ ể ả nh° sau:

</div><span class="text_page_counter">Trang 17</span><div class="page_container" data-page="17">

// kh i t o các giá tr cở ạ ị ủa các bi n toàn c c. ế ụ For v V Chuaxet[v]= false; ỵ

For v V ỵ

If Chuaxet[v] BFS(v); }

T°¡ng tā nh° DFS() có thể thấy rằng lánh gái BFS() sẽ cho phép đến thăm tất cả các đỉnh thuộc cùng thành phần liên thơng vßi đỉnh v, và mỗi đỉnh cÿa đồ thß sẽ đ°ợc thăm đúng mộ ần. Đột l ph c t p tính tốn c a thu t tốn là O(n+m). ā ¿ ÿ Á

Hình minh h a: Ch s m i (trong ngo c) cá ỉ ố ß ặ ÿa các đỉnh đ°ợc đánh l¿i theo th t ā ā chúng đ°ợc thăm trong tht tốn tìm ki m theo chi u r ng. ế ề ộ

Āng dụng cÿa 2 thu t tốn tìm kiÁ ếm trên đồ ß th : • Tìm đ°áng đi (chu trình) trên thò. ã Liỏt kờ tt c cỏc ỏng i cú trong thò ã Kiểm tra tính liên thơng.

</div><span class="text_page_counter">Trang 18</span><div class="page_container" data-page="18">

<small>Nguyễn Thị Anh Đào Trang 17 </small>

<b>Tìm đưßng đi ngắn nhất trên đồ thị Bài toán </b>

Cho đồ thß G = (V, E) là đồ thß đ¡n liên thơng có tráng số khơng âm, tìm đ°áng đi có tổng tráng số nh nht t nh s n f ỵ V.

<b>Thut tốn Dijkstra </b>

Đầu vào: Đồ thß vơ h°ßng G = (V, E) vßi n đỉnh, s V l nh khi u, ỵ

<b>a[u,v] l trỏng s ca cnh e(u, v), u, v ỵ V </b>

Giả thiết: a[u, v] 0 , u, v V ỵ

u ra: di ỏng i từ s đến f. Truoc[v], v V, ghi nhÁn ỏng ỵ i l cỏc

<b>Tỡm cõy khung nh nhất trên đồ thị Thuật tốn Prim </b>

Đối vßi nhÿng đồ thß dày (số c¿nh m n(n  − 1)/2) thuÁt toán Kruskal làm viác kém hiáu quả. Trong tr°áng hợp đó, tht tốn Prim đ°ợc trình bày sau đây tỏ ra hiáu quả h¡n. ThuÁt tốn Prim cịn đ°ợc gái là ph°¡ng pháp lân cÁn gần nhất. Đầu vào: Đồ thß G = (V, E) đ¡n, liên thơng, có tráng số a(u, v), u, v V, vỵ <small>*</small>l nh khi u.

Đầu ra: Cây khung T = (V , E<small>TT</small>) là cây khung nhỏ nhất trong đồ thß.

</div>