Báo cáo bài tập lớn thuật toán floyd wrashall

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.18 MB, 20 trang )

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

ĐẠ<b>I H C QU C GIA TPHCM </b>ỌỐ

<b>TRƯỜNG </b>ĐẠ<b>I H C BÁCH KHOA </b>Ọ 

<b>KHOA CƠ KHÍ </b>

<b>NHĨM NGÀNH: K THU T H</b>ỸẬ<b>Ệ THỐNG CƠNG NGHI P, </b>Ệ

<b>LOGISTICS VÀ QU N LÝ CHU I CUNG </b>ẢỖ<b>ỨNG</b>

<i><b>Mơn học:</b></i><b>ĐẠI S TUY N TÍNH </b>ỐẾ

<b>BÁO CÁO BÀI T P L N </b>ẬỚ

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

<b>Danh sách thành viên </b>

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

<b>MỤC L C </b>Ụ

Danh sách thành viên………...Trang 2 Lời m ở đầu ………..Trang 4

I. GIỚI THI U CHUNG: Ệ

Sơ lược về thu t toán Folyd Warshall, Lậ ịch s ử …………...Trang 5 Tác dụng , Ưu điểm, Nhược điểm ………Trang 6 II. Ý TƯỞNG VÀ CÁCH GI I THUẬT TOÁN: Ả

Ý tưởng, cách giải ……….Trang 7 Giải thuật toán trong matlab ……….Trang 8

III. ỨNG DỤNG:

IV. CÁC THUẬT TỐN KHÁC:

Thuật tốn Dijkstra ………...Trang 12 Thuật tốn Bellman – Ford ………...…Trang 15 Thuật toán Johnson………Trang 17 V. TÀI LI U THAM KHỆ ẢO: ………...Trang 19 VI. TỔNG KẾT:………...Trang 19 VII. NHẬN XÉT CỦA GIÁO VIÊN: ………..Trang 19

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

<b>Lời mở đầu </b>

<b> Với sự </b>ra đờ ủi c a Internet, tất c ả các trường h c hiọ ện nay đều đã áp dụng các kiến thức, kĩ năng và hiểu biế ềt v công nghệ thông tin trong các môn học nhằm nâng cao hi u qu d y và hệ ả ạ ọc.

Trong khoa h c máy tính và trong tốn h c, thuọ ọ ật tốn tìm đường đi ngắn nhất trong đồ thị là một bài toán thường được vận dụng trong các ứng dụng tin học. Trong các ng d ng th c tứ ụ ự ế, bài tốn tìm đường đi ngắn nh t giấ ữa hai đỉnh của một đồ thị có một ý nghĩa to lớn. Ví dụ, bài tốn chọn một hành trình tiết kiệm nhất ( v tiêu chu n kho ng cách, th i gian ho c chi phí) trên một mề ẩ ả ờ ặ ạng lưới giao thơng đường bộ, đường thủy,…Hiện nay có rất nhiều các phương pháp để giải các bài tốn như vậy. Thế nhưng thơng thường, các thuật tốn được xây dựng dựa trên cơ sở lý thuyết đồ thị là hiệu quả cao nhất. Sau đây chúng ta sẽ xét đến một số thuật toán như vậy.

Mong th y và các b n theo dõi, góp ý ầ ạ để chủ đề ủa chúng em đượ c c hoàn thiện hơn.

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

<i><b>I. GIỚI THI U CHUNG: </b></i>Ệ

<b> SƠ LƯỢC VỀ THUẬT TOÁN FLOYD-WARSHALL: </b>

Khi nhắc đến thuật toán để tìm đường đi ngắn nhất trong đồ thị, người ta sẽ thường nghĩ tới những thuật toán dễ tiếp cận và có thể chạy trong giới hạn cho

-tốn trên đều chỉ có thể tìm được đường đi ngắn nhất từ một đỉnh nguồn nhất định đến các đỉnh khác và do đó, trong một số trường hợp cụ thể cần chỉ ra đường đi ngắn nhất của mọi cặp đỉnh trong đồ thị, các thuật toán này sẽ hoạt động chưa hiệu quả khi phải chạy lặp đi lặp lại khá nhiều thao tác.

Floyd-Warshall chính là cơng cụ có thể giúp ta giải quyết vấn đề này chỉ trong một lần chạy duy nhất. Hơn thế nữa, cách tiếp cận và cài đặt của nó cũng khá đơn giản và quen thuộc.

Thuật toán Folyd Wardshall được Robert Folyd đưa ra và được công nhận vào năm 1962. Nó cơ bản giống với các thuật toán được đưa ra bởi Bernard Roy vào năm 1959 cũng như Stephen Wardshall năm 1962.

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

<b> Floyd-Warshall được sử dụng để tính tốn đường đi ngắn nhất giữa mọi cặp điểm trong đồ thị có hướng. </b>

đường đi ngắn nhất giữa các cặp cạnh, ta tiếp tục chạy thuật toán một lần nữa, và nếu đường đi được xem là đường đi ngắn nhất tiếp tục cập nhật ngắn hơn thì có nghĩa rằng tồn tại một đường đi âm trong đồ thị.

<b> ƯU ĐIỂM SO VỚI CÁC THUẬT TOÁN KHÁC: </b>

Tìm được đường đi ngắn nhất giữa tất cả các điểm trong đồ thị với trọng số âm hoặc dương, trong đồ thị có hướng hoặc vơ hướng.

Chỉ với một lần chạy thuật toán sẽ cho ta kết quả. Phát hiện được chu trình âm trong đồ thị.

<b> NHƯỢC ĐIỂM: </b>

Trong đồ thị không được có vịng (cycle) nào có tổng các cạnh là âm, nếu có vịng như vậy ta khơng thể tìm được đường đi ngắn nhất (mỗi lần đi qua vòng này độ dài quãng đường lại giảm, nên ta có thể đi vơ hạn lần)

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

<i><b>II. Ý TƯỞNG VÀ CÁCH GIẢI THUẬT TOÁN: </b></i>

<b>1. Ý tưởng: </b>

Từ bài toán đã cho, chuyển các số liệu về ma trận trọng số D. Sau bước lặp thứ k, D[i,j] chứa độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh j (có thể đi qua đỉnh khác rồi đến j), các đỉnh nó đi qua có chỉ số khơng vượt q k.

<b>2. Cách giải: </b>

Bước 1: Sử dụng ma trận A để lưu độ dài đường đi ngắn nhất giữa mọi cặp đỉnh.

Bước 2: Ta đặt A[i, j] = C[i, j] (có nghĩa A ban đầu chứa độ dài đường đi trực tiếp các đỉnh x đến y thuộc đồ thị mà không đi qua đỉnh nào cả.) Bước 3: Sau đó, ta thực hiện n lần lặp. Sau lần lặp thứ k, ma trận A sẽ chứa

độ dài các đường đi ngắn nhất chỉ đi qua các đỉnh thuộc {1, 2, …, k} Bước 4: Kí hiệu Ak là ma trận A sau lần lặp thứ k, khi đó Ak[i, j] được tính

theo cơng thức sau: A [i, j] = min(A [i, j], A [i, k] + A [k, j] ) <small>kk-1k-1k-1</small>

Bước 5: Do đó, sau n lần lặp ta nhận được ma trận A chứa độ dài các đường đi ngắn nhất.

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

<b>3. Giải thu t toán trong matlab: </b>ậ

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

<b>4. Ví dụ: </b>

<i>Hình nh mơ t thu t toán </i>ả ả ậ

<i>Floyd – Warshall trong đồ thịvô hướng </i>

Và đây là kết qu cả ủa đoạn code cho thu t toán trên: ậ

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

10 Dưới đây là một ví dụ khác về thuật tốn Floyd-Warshall trong đồ thị có hướng:

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

<i><b>III. NG D NG: </b></i>ỨỤ

Việc nghiên c u thuứ ật toán Floyd để áp dụng vào trong th c t là r t quan trọng ự ế ấ với nhi u ti n lề ệ ợi cho con ngườ ả ề ậi c v v t ch t, cấ ủa c i l n th i gian. Giúp ích rả ẫ ờ ất nhiều cho con người trong việc nâng cao hiệu quả làm việc và làm tăng năng suất lao động, tăng thu nhập cho doanh nghiệp.

tối ưu hóa đường đi ở các thành phố lớn.

Tối ưu hóa mặt bằng trong doanh nghiệp hay các tổ chức, cắt giảm thời gian di chuyển giữa các đơn vị, giữa các tr m, t ạ ừ đó nâng cao năng suấ ủt c a cả mạng lưới. Tìm được con đường vận chuyển nhanh nhất giữa các vùng lân cận hoặc giữa các quốc gia v i nhau,l a chớ ự ọn để đưa ra phương án cực ti u chi phí v n chuy n hàng ể ậ ể hóa, d ch v . ị ụ

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

Thuật toán Dijkstra là m t trong nhộ ững thuật toán cơ bản dùng để tìm đường đi ngắn nh t t mấ ừ ột điểm tới một điểm nào đó, và mở ộng ra là tìm đường đi ngắn r nhất từ 1 điểm tới mọi điểm còn lại của đồ thị, với điều ki n các tr ng s cệ ọ ố ủa đồ thị đó khơng âm.

<i><b>b) Các bước giải thuật tốn: </b></i>

Bước 1: Ta xây d ng mự ột m ng 1D chả ứa đường đi ngắn nh t giấ ữa đỉnh đang xét tới t t cấ ả các đỉnh còn l i, giá trạ ị ngầm định bằng +INF.

Bước 2: Chọn một điểm b t kấ ỳ chưa đư c duyợ ệt và có đường đi ngắn nh t t ấ ừ điểm gốc t i nó là nhớ ỏ nhất.

Bước 3: T ừ điểm đó, loang đường đi ra tất cả các đỉnh kề cận, và cập nhật lại đường đi ngắn nhất tới các đỉnh đó nếu đường đi mớ ối ưu hơn.i t

Bước 4: Nếu còn điểm chưa được duy t (hoệ ặc chưa tìm được điểm đích, tùy yêu cầu đề bài), ta trở lại bước 1.

Ta xét đồ thị vô hướng sau (số màu đỏ là đường đi ngắn nhất xuất phát từ đỉnh 1 tới đỉnh được xét):

Đầu tiên, ta xét đỉnh 1 (vì đường đi ngắn nhất từ 1 tới 1 hiển nhiên có độ dài 0). Sau q trình c p nh t, ta có các giá tr ậ ậ ị đường đi ngắn nh t m i: ấ ớ

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

Tiếp theo, ta duyệt đỉnh 5 (đường đi ngắn nhấ ừt t 1 tới 5 có độ dài 1). Sau c p nhậ ật, ta thu được các giá tr m ị ới:

Tiếp theo, ta duyệt đỉnh 4 (đường đi ngắn nhấ ừt t 1 tới 4 có độ dài 3). Sau c p nhậ ật, ta thu được các giá tr m ị ới:

Cứ tiếp tục như vậy cho tới khi duyệt hết đỉnh, ta sẽ thu được các giá trị hoàn chỉnh:

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

14 Sở dĩ phương pháp này đúng bởi, ta đã ngầm định đặt ra điều kiện trước: các trọng s c a các c nh ph i là các s không âm. ố ủ ạ ả ố Do đó, việc duy t liên t c t ệ ụ ừ các đỉnh có độ dài đường đi ngắn nhất là cực tiểu sẽ ln được đảm bảo tính chính xác: ta khơng th ể xuất phát t b t k nh nào khác qua m t giá tr trung ừ ấ ỳ đỉ ộ ị gian mà thu được đường đi nhỏ nhất từ đỉnh gốc tới đỉnh cực tiểu ta đang xét thậm chí cịn nh ỏ hơn nữa được.

Tuy nhiên, với trường h p tr ng s âm, l p lu n này b bác bợ ọ ố ậ ậ ị ỏ. Xét đồ thị sau:

Bằng mắt thường, ta có thể thấ ằng: đường đi ngắy r n nhất từ đỉnh 1 tới đỉnh 4 sẽ là đoạn đường 1->3->4.

Tuy nhiên, áp dụng tư duy thuật tốn Dijkstra, ta có:

<small></small> Khở ại t o: s_path[1] = 0, s_path[2] = INF, s_path[3] = INF, s_path[4] = INF. <small></small> Xuất phát t nh 1. C p nh t: s_path[2] = 2, s_path[3] = 6. ừ đỉ ậ ậ

<small></small> Xuất phát t nh 2. C p nh t: s_path[4] = 5. ừ đỉ ậ ậ

<small></small> Xuất phát t đỉnh 4. Do đây là đỉnh đích nên ng ng thu t toán, k t lu n ans ừ ừ ậ ế ậ = 5.

Rõ ràng, do phương pháp khơng tính đến trường hợp độ dài đường đi nhỏ nhất có thể giảm, nên nhánh xu t phát t nh 3 bị ại bỏ, dẫn đến kết quả sai ấ ừ đỉ lo

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

<b>2. Thuật toán Bellman-Ford: </b>

<i><b>a. Giới thiệu: </b></i>

Thuật toán Bellman Ford là một trong những thuật tốn dùng để tìm đường đi ngắn -nhất (chỉ áp dụng cho đồ thị có hướng) từ một điểm tới một điểm nào đó, và mở rộng ra là tìm đường đi ngắn nhất từ 1 điểm tới mọi điểm còn lại của đồ thị, với điều kiện đồ thị khơng được phép có chu trình âm.

<i><b>b. Các bước giải thuật toán: </b></i>

Bước 1: Chọn một đỉnh gốc. Ta xây dựng một mảng chứa đường đi ngắn nhất giữa đỉnh đang xét tới tất cả các đỉnh còn lại, giá trị ngầm định bằng +INF. Bước 2: Xét chiều dài đường đi từ đỉnh đang xét đến các đỉnh lân cận, cập nhật đường đi.

Bước 3: Từ mỗi điểm lân cận với điểm gốc, xét chiều dài đường đi đến các đỉnh khác lân cận chưa được duyệt, cập nhật lại chiều dài từ đỉnh gốc đến đó là tổng chiều dài từ đỉnh gốc đến đỉnh kề trước và chiều dài từ đỉnh kề trước đến đỉnh đang xét nếu chiều dài đường đi tính được ngắn hơn lần duyệt trước.

Bước 4: Tiếp tục duyệt cho đến khi khơng cịn đường đi tối ưu từ đỉnh gốc đến các đỉnh còn lại hoặc cho đến khi số lần duyệt bằng số đỉnh trừ đi 2.

Ta xét ví dụ với đồ thị có hướng sau (giả định các đường đi là một chiều, chỉ đi từ đỉnh có số thứ tự thấp hơn tới đỉnh có số thứ tự cao hơn, số có màu đỏ cạnh mỗi đỉnh là độ dài đường đi ngắn nhất từ gốc tới đỉnh đó, và đỉnh gốc là đỉnh 1):

Thực hiện lần duyệt đầu tiên, ta cập nhật được đường đi ngắn nhất thông qua các cạnh (1, 2); (1, 3); (1, 4):

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

Tới lần duyệt thứ 4, ta thấy khơng cịn cạnh nào có thể tối ưu hóa bất kỳ đường đi ngắn nhất nào nữa. Tới đây, ta hồn tồn có thể dừng duyệt (vì chắc chắn việc khơng cịn cạnh có thể tối ưu cũng đồng nghĩa với việc khơng có chu trình âm trong đồ thị).

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

<b>3. Thuật toán Johnson: </b>

<i><b>a) Giới thi u: </b></i>ệ

Thuật toán này tương tự thuật tốn Floyd-Warshall nhưng cho đồ thị có trọng số b t k và khơng có chu trình âm. ấ ỳ

Ý tưởng bài tốn: Từ đồ thị đã cho, tìm cách chuyển nó thành đồ thị có trọng số không âm r i dùng thu t toán Dijkstra áp d ng cho tồ ậ ụ ừng đỉnh.

Hình (a) là đồ thị có hướng mà ta muốn tìm đường đi ngắn nhất. Hình (b) là đồ thị thu được sau khi ta thêm S và các cung (có màu đỏ) có

hướng t S từ ới các đỉnh khác với trọng s 0. ố

Hình (c) là cây đường đi ngắn nhất gốc tại S sau khi áp dụng thuật toán Bellman-Ford. Các s trong ơ vng chính là kho ng cách t S tố ả ừ ới đỉnh tương ứng. Kí hiệu tại mỗi đỉnh v là h(v). Với h(v) là kết quả đi từ S tới v tính b ng thu t toán trên. ằ ậ

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

18 Hình (d) là đồ thị mới thu được sau khi hiệu chỉnh trọng số của đồ thị cũ

theo công thức: w'(u, v) = w (u, v) + h(u) - h(v). (Trong đó: w'(u, v) là trọng số mới ứng với đường đi từ u t i v; w (u, v) là tr ng s ớ ọ ố cũ; h(u) có ý nghĩa như h(v) ứng với đỉnh u, v).

<i><b>b) Các bước giải thuật toán: </b></i>

Bước 1: Đặt một đỉnh ph ụ S có đường đi đế ấ ản t t c các đỉnh trong đồ thị đều bằng 0.

Bước 2: Áp ụ d ng thu t toán Dijkstra cho tậ ừng đỉnh để tìm đường đi ngắn nhất.

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