Báo cáo cuối kỳ môn phân tích thiết kế và giải thuật chủ đề thuật toán quy hoạch động

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.96 MB, 12 trang )

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

<b>BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HCM</b>

<b>KHOA CÔNG NGHỆ THÔNG TIN</b>

<b>BÁO CÁO CUỐI KỲ MƠN PHÂN TÍCH THIẾTKẾ VÀ GIẢI THUẬT</b>

<b>CHỦ ĐỀ THUẬT TOÁN QUY HOẠCH ĐỘNG </b>

<b>Giảng viên hướng dẫn: GV Văn Thế Thành</b>

<b>Sinh viên thực hiện: Lê Phan Gia MinhLớp học phần: COMP140101MSSV: 45.01.104.143</b>

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

<b>1. Trình bày thuật tốn.</b>

Khởi tạo lấy điểm 1 làm điểm xuất phát

C1: từ điểm 1 ta có đường đi đến điểm 2 và điểm 4 => ở điểm 2 và điểm 4 lần lượt ta có (3,1), (10,1) với 3 và 10 là khoảng cách giữa 2 điểm lần lượt là 2 và 4 so với điểm 1. Và do khoảng cách từ 1 -> 2 ngắn hơn từ 1 -> 4 nên tại đây ta chốt ở điểm 2.

C2: từ điểm 2 có 2 đường đi đến là 3 và 4 và do đã có khoảng cách từ 1 ->2 ở C1 nên ta sẽ cộng dồn vào khoảng cách ở tại điểm 3, 4 lần lượt là (4, 2), (6, 2). Khoảng cách từ 2->3 ngắn hơn nên ta sẽ chốt tại 3 với (4, 2)

C3: tương tự như C1, C2 ta có 4 (11, 4) và kết thúc. Yêu cầu tìm đường đi ngắn nhất từ 1->3 nên ta có: =>lấy đường đi 1 -> 2 -> 3

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

C2=1 public int[,] maTran = new int[100, 100];

public void dijkstra(int dinhDau, int dinhCuoi)

C10= n(n+1)/2 if (maTran[v, k] != 0 && thuocT[k] == true && (length[k] == voCuc || length[k] > length[v] + maTran[v, k]))

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

Khi ta có 1 đồ thị như hình, ta có quy về 1 ma trận với số đỉnh và giá trị khoảng cách của từng cạnh như ví dụ ở Input và tìm đường đi ngắn nhất giữa các đỉnh bất kì

- Gán vơ cực = -1 (vơ cực khi khơng có đường đi giữa 2 điểm) - Khởi tạo mảng 2 chiều cho ma trận [100,100]

- Tạo hàm đọc tạo ma trận [i,j] của đồ thị

<small>public void docMaTran( [,] _maTran, _soDinh)intint</small>

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

<small> (maTran[v, k] != 0 && thuocT[k] == iftrue && (length[k] == voCuc || length[k] > length[v] + maTran[v, k]))</small>

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

Hướng dẫn chạy chương trình:

Sau khi giải nén thầy chọn mục Grap_Theory.sln và chạy bằng MS Visual Studio

Sau đó sẽ được như hình:

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

Sau khi bấm start:

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

Ngồi ra cịn có các tính năng “xóa đỉnh”, “xóa cạnh”, “Set/Đổi trọng số”(thay đổi

“Đỉnh cuối”, “Trọng số” sau đó double click vào “Set/Đổi trọng số” )

(Do đây là phần code em đã làm bên môn lý thuyết đồ thị ở học kỳ trước nên cịn một số tính năng em chưa kịp remove em mong thầy thông cảm giúp em ạ) Kết quả các test case:

Test case1:

Test case 2:

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

Test case 3:

Test case 4:

Test case 5:

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

Test case 6:

Test case 7:

Test case 8:

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

Test case 9: