Tài liệu Bồi dưỡng học sinh giỏi môn tin học thpt chuyên đề vai trò cấu trúc dữ liệu trong các bài toán đồ thị

  • Số trang: 13 |
  • Loại file: PDF |
  • Lượt xem: 1975 |
  • Lượt tải: 0

Mô tả:

VAI TRÒ CẤU TRÚC DỮ LIỆU TRONG CÁC BÀI TOÁN ĐỒ THỊ Những tiến bộ của công nghệ và sự phát triển của lý thuyết tính toán khoa học đã mang lại những thay đổi về chất lượng cho các hệ thống lập trình. Điều này kéo theo sự thay đổi cần thiết bắt buộc trong việc tiếp cận các bài toán Tin học nói chung và các bài toán trên đồ thị nói riêng. Báo cáo này đề cập tới một tác nhân thay đổi mà học sinh cần phải quán triệt trong quá trình học tập hiện tại và làm việc sau này, đó là vai trò của cấu trúc dữ liệu trong việc nâng cao hiệu quả của các giải thuật đã có cũng như việc tìm ra các giải thuật mới. 1. ĐẶT VẤN ĐỀ Các bài toán tin học ngày nay, ngay trong phạm vi chương trình phổ thông trung học cũng đã có những đặc thù đòi hỏi phải có cách tiếp cận mới trong việc xây dựng và cài đặt giải thuật. Đặc điểm của phần lớn các bài toán hiện nay là: Số đỉnh n là rất lớn, từ vài trăm ngàn đến vài triệu, Độ dàn đầy thấp: số cạnh chỉ vài cho đến vài chục phần trăm so với ma trận đầy đủ, Không đơn thuần tìm độ dài đường đi ngắn nhất mà phải xác định cả bản thân đường đi ngắn nhất, thực hiện các phân tích và đánh giá khác nhau về nhóm đường đi có độ dài ngắn nhất, Thực hiện các truy vấn động trên đồ thị: Các thông số về đỉnh, cạnh, điểm xuất phát, điểm đích . . . có thể thay đổi từ truy vấn này sang truy vấn khác. Các giải thuật cơ sở kinh điển được xem xét và giảng dạy ở thế kỷ XX vẫn rất cần thiết, nhưng là chưa đủ trong việc đào tạo và bồi dưỡng học sinh năng khiếu tin học phù hợp với yêu cầu thực tế hiện tại. Một giải thuật nói chung và trong các bài toán đồ thị nói riêng, muốn có hiệu quả phải tận dụng được tối đa và hợp lý các khả năng mà môi trường kỹ thuật cung cấp, cụ thể là: Cho phép sử dụng khối lượng bộ nhớ lớn, Khai thác được một cách hợp lý các cấu trúc dữ liệu mà các hệ thống lập trình cung cấp, Tốc độ cao của các thiết bị tính toán. Thông thường các bài toán cần giải cho phép sử dụng không ít hơn 64MB. Người giải bài toán được quyền sử dụng mọi dịch vụ do thư viện chuẩn của hệ thống lập trình cung cấp. Việc sử dụng các cấu trúc dữ liệu này, khi triển khai, mang lại hiệu quả ngay cả với các bài toán kinh điển. 1 2. HÀNG ĐỢI ƯU TIÊN VÀ GIẢI THUẬT DIJSKTRA 2.1 - BÀI TOÁN Cho đồ thị n đỉnh và m cạnh. Đồ thị có thể có hướng hoặc không. Trọng số của mỗi cạnh là không âm. Hãy xác định đường đi ngắn nhất từ đỉnh s cho trước tới mỗi đỉnh còn lại và độ dài của đường đi đó. 2.2 - GIẢI THUẬT Tổ chức mảng D = (d1, d2, . . ., dn), dv lưu trữ độ dài đường đi ngắn nhất từ s tới v, v = 1 ÷ n. Ban đầu ds = 0, dv = , v= 1 ÷ n, v ≠ s. Ngoài ra, còn cần tới mảng lô gic U = (u1, u2, . . ., un) để đánh dấu, cho biết đỉnh v đã được xét hay chưa. Ban đầu, uv = false với v= 1 ÷ n. Bản thân giải thuật Dijsktra gồm n bước. Ở mỗi bước cần chọn đỉnh v có dv là nhỏ nhất trong số các đỉnh v chưa được đánh dấu, tức là dv = min{di | ui = false, i = 1 ÷ n } Công việc tiếp theo trong bước này là điều chỉnh D: xét tất cả các cạnh (v, t). Gọi lt là trọng số của cạnh (v, t). Giá trị dt được chỉnh lý theo công thức dt = min{dt, dv+lt} Sau n bước, tất cả các đỉnh đều được đánh dấu và dv sẽ là độ dài đường đi ngắn nhất từ s đến v. Nếu không tồn tại đường đi từ s đến v thì dv vẫn nhận giá trị . Để khôi phục đường đi có độ dài ngắn nhất cần tổ chức mảng P = (p1, p2, . . ., pn), trong đó pv lưu đỉnh cuối cùng trước đỉnh v trong đường đi ngắn nhất từ s đến v. Mỗi lần, khi dt thay đổi giá trị thì đỉnh đạt min: pt = v. Tính đúng đắn của giải thuật được nêu trong nhiều tài liệu khác nhau và là điều không cần phải trình bày ở đây. Điều quan trọng là đánh giá độ phức tạp của giải thuật và làm thế nào để giảm độ phức tạp đó. Giải thuật bao gồm n bước lặp, ở mỗi bước lặp cần duyệt tất cả các đỉnh và sau đó – chỉnh lý dt. Như vậy giải thuật có độ phức tạp là O(n2+m). 2.3 - KỸ THUẬT CÀI ĐẶT HIỆU QUẢ CAO VỚI ĐỒ THỊ MA TRẬN THƯA Với đồ thị có số cạnh m nhỏ hơn nhiều so với n2 thì độ phức tạp của giải thuật có thể giảm xuống bằng việc cải tiến cách duyệt đỉnh ở mỗi bước lặp. Mục tiêu này có thể đạt được thông qua việc sử dụng Cấu trúc vun đống Fibonacci (Fibonacci Heap), Cấu trúc tập hợp (Set) hoặc cấu trúc Hàng đợi ưu tiên (Priority_Queue). Cấu trúc vun đống Fibonacci cho phép giải bài toán tìm đường đi ngắn nhất với độ phức tạp O(nlogn+m). Về mặt lý thuyết, đây là độ phức tạp tối ưu cho chương trình giải các bài toán 2 dựa trên cơ sở giải thuật Dijkstra. Tuy nhiên việc cài đặt khác phức tạp vì thư viện chuẩn STL của các hệ thống lập trình dựa trên C++ chưa trực tiếp hỗ trợ Fibonacci Heap. Các giải thuật dựa trên Set hoặc Priority_Queue tuy không hiệu quả bằng sử dụng Fibonacci heap nhưng cũng cho độ phức tạp khá tốt, đủ chấp nhận được – O(mlogn). Với cấu trúc tập hợp (Set), mỗi đơn vị dữ liệu input cần được tổ chức dưới dạng cặp số nguyên (pair), phần tử thứ nhất là trọng số và phần tử thứ hai là đỉnh của cạnh. Dữ liệu sẽ được tự động sắp xếp theo trọng số tăng dần – điều mà ta đang cần! Việc tổ chức mảng đánh dấu U cũng trở nên không cần thiết. Khi điều chỉnh D, mỗi khi có sự thay đổi, trước hết cần xóa cặp dữ liệu cũ, tính lại dt và nạp lại cặp dữ liệu mới ứng với dt vừa tính được. Chương trình làm việc với hàng đợi ưu tiên hoạt động nhanh hơn một chút so với phương án sử dụng tập hợp. Tuy vậy, theo bản chất của cấu trúc dữ liệu, hệ thống không cung cấp dịch vụ xóa thông tin nếu nó không đứng ở đầu hàng đợi. Chính vì vậy phần lớn các giải thuật sử dụng hàng đợi (kể cả hàng đợi ưu tiên) đều phải giải quyết vấn đề lọc dữ liệu thừa trong quá trình xử lý. Trong giải thuật này, việc đó đơn thuần là so sánh giá trị lưu trữ ở đầu hàng đợi q với dv. Khi chỉnh lý D, cặp giá trị (dt, t) được nạp vào hàng đợi. Cặp giá trị mới này sẽ đứng trước các cặp khác có cùng giá trị t. Cần lưu ý là với khai báo priority_queue < pair > q; việc tổ chức ngầm định sẽ đặt giá trị lớn nhất lên đầu hàng đợi. Muốn có hàng đợi sắp xếp theo thứ tự tăng dần ta cần khai báo: typedef pi2 pair; priority_queue ,greater > q; Trong giải thuật nàycác giá trị khóa đều không âm, vì vậy ta có thể dùng khai báo đơn giản theo kiểu ngầm định, nhưng nạp giá trị khóa âm. Kết quả là giá trị thực sự nhỏ nhất vẫn đứng ở đầu hàng đợi. Chương trình sau giải bài toán đã nêu với dữ liệu đưa vào từ file Dijsktra.inp theo quy cách: Dòng đầu tiên chứa 2 số nguyên n và m (n > 0, m ≥ 0), Nếu m > 0 thì mỗi dòng trong m dòng tiếp theo chứa 3 số nguyên a, b và r cho biết có cạnh nối từ a tới b với trọng số r (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ r ≤ 106), không có hai nào giống nhau, Dòng m+2 chứa số nguyên s (1 ≤ s ≤ n), Dòng cuối cùng chứa số nguyên k và sau đó là k số nguyên c1, c2, . . ., ck cho biết phải dẫn xuất đường đi ngắn nhất từ s tới ci, i = 1 ÷ k, 1 ≤ ci ≤ n. Kết quả được đưa ra file Dijsktra.out: Dòng đầu tiên chứa n số nguyên, số thứ i là độ dài đường đi ngắn nhất từ s đến đỉnh i. Độ dài bằng -1 nếu không tồn tại đường đi từ s đến đỉnh đó, Dòng thứ i trong k dòng sau chứa thông tin về đường đi ngắn nhất (theo quy cách nêu trong ví dụ). 3 Ví dụ: xét đồ thị 2 10 3 5 1 9 1 2 5 4 10 3 2 6 15 Các file dữ liệu Input và output: 6 1 1 2 3 2 3 4 4 5 2 2 DIJSKTRA.INP 9 2 10 3 1 4 5 4 2 5 3 6 15 6 10 5 9 6 2 DIJSKTRA.OUT 8 0 7 5 3 5 Shortets route from 2 to 1: 2 4 3 1 Shortets route from 2 to 6: 2 5 6 Time: 0 sec 1 6 Chương trình trên C++ sử dụng cấu trúc dữ liệu Hàng đợi ưu tiên: #include #include #include #include using namespace std; const int INF = 1000000000; ifstream fi ("Dijsktra.inp"); ofstream fo ("Dijsktra.out"); pairx; int a,b,dd,k; int main() { clock_t aa=clock(); int n,m; fi>>n>>m; vector < vector < pair > > g (n+1); for(int i=1;i<=m;++i) {fi>>a>>b>>dd;x.first=a;x.second=dd; 4 g[b].push_back(x); x.first=b;g[a].push_back(x); } int s ; fi>>s; vector d (n+1, INF), p (n+1); d[s] = 0; priority_queue < pair > q; q.push (make_pair (0, s)); while (!q.empty()) { int v = q.top().second, cur_d = -q.top().first; q.pop(); if (cur_d > d[v]) continue; for (size_t j=0; j>k; for(int i=0;i>t; vector path; fo<<"\n Shortets route from "< #include #include #include #include using namespace std; 5 const int INF = 1000000000; ifstream fi ("Dijsktra.inp"); ofstream fo ("Dijsktra.out"); pairx; int a,b,dd,k; int main() { clock_t aa=clock(); int n,m; fi>>n>>m; vector < vector < pair > > g (n+1); for(int i=1;i<=m;++i) {fi>>a>>b>>dd;x.first=a;x.second=dd; g[b].push_back(x); x.first=b;g[a].push_back(x); } int s ; fi>>s; vector d (n+1, INF), p (n+1); d[s] = 0; set < pair > q; q.insert (make_pair (d[s], s)); while (!q.empty()) { int v = q.begin()->second; q.erase (q.begin()); for (size_t j=0; j>k; for(int i=0;i>t; vector path; fo<<"\n Shortets route from "< 0 – điểm đã được xử lý, Hàng đợi p kiểu deque lưu các điểm tiềm năng cần thăm và duyệt tiếp, mỗi phần tử của hàng đợi là một cặp dữ liệu (i, j). Xử lý Với mỗi vị trí (i, j) có ai,j ≠ ‘.’ và cần để lại xử lý sau – phân biệt các trường hợp:  Cùng giá trị với ô đang xử lý – nạp (i, j) vào cuối hàng đợi (p.push_back(pp);)  Khác giá trị với ô đang xử lý – nạp (i, j) vào đầu hàng đợi (p.push_front(pp);) Trong mọi trường hợp – cần đánh dấu bi,j = -1 Mỗi lần chuyển sang duyệt giá trị mới – tăng bộ đếm lớp lên 1. Bộ đếm lớp sẽ là kết quả cần tìm. Việc kiểm tra giá trị bi,j > 0 cho phép loại ngay khỏi hàng đợi các điểm tiềm năng trở thành nhiễu. Chương trình #include #include #include 11 #include #include #include using namespace std; typedef pair p2; int w,h,k,b[4002][4002]={0},i1,j1; char c,c1,ct,a[4002][4002]={'.'}; pairpp; deque p; string s; ifstream fi ("tracks.inp"); ofstream fo ("tracks.out"); void swp() {ct=c;c=c1; c1=ct;} void upd_p(int x,int y) {if(x>1 && b[x-1][y]==0 && a[x-1][y]!='.') {pp.first=x-1;pp.second=y;if(a[x-1][y]==c)p.push_back(pp); p.push_front(pp);b[x-1][y]==-1;} if(x1 && b[x][y-1]==0 && a[x][y-1]!='.') {pp.first=x;pp.second=y-1;if(a[x][y-1]==c)p.push_back(pp); p.push_front(pp);b[x][y-1]==-1;} if(y>h>>w; for(int i=1;i<=h;++i) {fi>>s; for(int j=1;j<=w;++j)a[i][j]=s[j-1];} c=a[1][1]; if(c=='F')c1='R'; else c1='F'; pp.first=1; pp.second=1; p.push_back(pp); while(!p.empty()) {pp=p.back(); i1=pp.first;j1=pp.second; if(b[i1][j1]<=0) {{if(a[i1][j1]==c)b[i1][j1]=k; else {b[i1][j1]=++k; swp();}} p.pop_back();upd_p(i1,j1); } else p.pop_back(); } fo< - Xem thêm -