Bài giảng Toán rời rạc: Một số bài toán tối ưu trên đồ thị - ThS. Hoàng Thị Thanh Hà

Bài giảng Toán rời rạc - Một số bài toán tối ưu trên đồ thị được biên soạn gồm các nội dung chính sau: Một số bài toán trên đồ thị; Thuật toán dijkstra; Thuật toán floyd tìm khoảng cách của các cặp đỉnh. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Một số bài toán tối ưu trên đồ thị - ThS. Hoàng Thị Thanh Hà Nội dung 1. MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ Toán rời rạc (5): 2. THUẬT TOÁN DIJKSTRA MỘT SỐ BÀI TOÁN TỐI ƯU 3. THUẬT TOÁN FLOYD TÌM KHOẢNG TRÊN ĐỒ THỊ CÁCH CỦA CÁC CẶP ĐỈNH Ts. Hoàng Thị Thanh Hà Khoa Thống kê –Tin học Trường Đại học Kinh tế30 October 2012 1 30 October 2012 2 MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ Mở đầu: Có thể coi sơ đồ của đường đi từ A đến B trong Trong đời sống, chúng ta thường gặp những thành phố là một đồ thị, với đỉnh là các giao lộ tình huống như sau: để đi từ địa điểm A đến địa (A và B coi như giao lộ), cạnh là đoạn đường điểm B trong thành phố, có nhiều đường đi, nối hai giao lộ. Trên mỗi cạnh của đồ thị này, ta nhiều cách đi; có lúc ta chọn đường đi ngắn gán một số dương, ứng với chiều dài của đoạn nhất (theo nghĩa cự ly), có lúc lại cần chọn đường, thời gian đi đoạn đường hoặc cước phí đường đi nhanh nhất (theo nghĩa thời gian) và vận chuyển trên đoạn đường đó, ... có lúc phải cân nhắc để chọn đường đi chi phí thấp nhất, v.v...30 October 2012 3 30 October 2012 4 MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ THUẬT TOÁN DIJKSTRA a) ĐN: Đồ thị có trọng số là đồ thị G=(V,E) mà mỗi cạnh Cho đơn đồ thị liên thông, có trọng số G=(V,E). Tìm e∈E được gán bởi một số thực m(e), gọi là trọng số của khoảng cách d(u0,v) từ một đỉnh u0 cho trước đến một cạnh (hoặc cung) e đỉnh v bất kỳ của G và tìm đường đi ngắn nhất từ u0 đến v. – Ở đây trọng số của mỗi cạnh được xét là một số dương và còn gọi là chiều dài của cạnh đó. Có một số thuật toán tìm đường đi ngắn nhất; ở đây, ta có – Mỗi đường đi từ đỉnh u đến đỉnh v, có chiều dài là m(u,v), bằng thuật toán do E. Dijkstra, nhà toán học người Hà Lan, đề tổng chiều dài các cạnh mà nó đi qua. Khoảng cách d(u,v) giữa xuất năm 1959. Trong phiên bản mà ta sẽ trình bày, người hai đỉnh u và v là chiều dài đường đi ngắn nhất trong các đường ta giả sử đồ thị là vô hướng, các trọng số là dương. Chỉ đi từ u đến v. cần thay đổi đôi chút là có thể giải được bài toán tìm Có thể xem một đồ thị G bất kỳ là một đồ thị có trọng số đường đi ngắn nhất trong đồ thị có hướng. mà mọi cạnh đều có chiều dài 1. Khi đó, khoảng cách d(u,v) giữa hai đỉnh u và v là chiều dài của đường đi từ u đến v ngắn nhất, tức là đường đi qua ít cạnh nhất.30 October 2012 5 30 October 2012 6 1 THUẬT TOÁN DIJKSTRA THUẬT TOÁN DIJKSTRA b) Phương pháp của thuật toán Dijkstra: xác định tuần b). Ma tr n kho ng cách. tự đỉnh có khoảng cách đến u0 từ nhỏ đến lớn. Cho G=(V,E) V={v1,v2,…,vn}là đơn đ th Trước tiên, đỉnh có khoảng cách đến a nhỏ nhất chính là a, với d(u0,u0)=0. Trong các đỉnh v ≠ u0, tìm đỉnh có khoảng có tr ng s .Ma tr n kho ng cách c a G là ma tr n D= (dij) xác đ nh như sau { cách k1 đến u0 là nhỏ nhất. Đỉnh này phải là một trong các đỉnh kề với u0. Giả sử đó là u1. Ta có: d(u0,u1) = k1. Trong các đỉnh v ≠ u0 và v ≠ u1, tìm đỉnh có khoảng cách 0 nếu i=j k2 đến u0 là nhỏ nhất. Đỉnh này phải là một trong các đỉnh kề với u0 hoặc với u1. Giả sử đó là u2. Ta có: d(u0,u2) = k2. d(ij)= W(vi,vj) khi (vi,vj) ∈ E Tiếp tục như trên, cho đến bao giờ tìm được khoảng cách ∞ khi ∉ E từ u0 đến mọi đỉnh v của G. Nếu V={u0, u1, ..., un} thì: 0 = d(u0,u0) < d(u0,u1) < d(u0,u2) < ... < d(u0,un)30 October 2012 7 30 October 2012 8 THUẬT TOÁN DIJKSTRA THUẬT TOÁN DIJKSTRAc)Thu t toánDijkstra Bài t p 1. Tìm đư ng đi ng n nh t t u0 đ n cácBư c1. i:=0, S:=V\{u0}, L(u0):=0, L(v):= ∞ v i m i v∈S đ nh còn l i và đánh d u đ ...