Tài liệu Bồi dưỡng học sinh giỏi tin học thpt chuyên đề hàng đợi ưu tiên và một số ứng dụng

Đề tài: HÀNG ĐỢI ƯU TIÊN VÀ MỘT SỐ ỨNG DỤNG I. ĐIỀU KIỆN HOÀN CẢNH TẠO RA SÁNG KIẾN Đối với những học sinh khối chuyên Tin của trường chuyên, để đáp ứng đúng chương trình khung đã đề ra và cũng là để phát hiện, bồi dưỡng các học sinh tham gia các đội tuyển học sinh giỏi các cấp thì kiến thức cơ bản, nâng cao về đồ thị rất quan trọng. Một trong những phần nâng cao về đồ thị là các giải thuật có sử dụng cấu trúc dữ liệu và “Hàng đợi ưu tiên - Heap” là một trong số đó. Để có thể hiểu rõ hơn về cấu trúc dữ liệu này tôi cung cấp thêm một cách cài đặt Heap đơn giản và hiệu quả để giải các bài toán đưa ra. II. THỰC TRẠNG Do một số năm gần đây việc sử dụng cấu trúc dữ liệu nâng để giải các bài toán tin trong đề thi HSG Tin học rất phổ biến. Các tài liệu viết về cấu trúc dữ liệu Heap (Tài liệu chuyên tin, Giải thuật và lập trình, …) rất khó cài đặt, đòi hỏi học sinh phải có kĩ năng thật tốt mới có thể cài đúng và sử dụng được cấu trúc dữ liệu này. III. GIẢI PHÁP Vì vậy, để có thể giải quyết các bài toán có sử dụng cấu trúc dữ liệu Heap một cách thuận tiện và đơn giản nhất. Trong khuôn khổ bài viết này, tôi xin giới thiệu một cách cài đặt cấu trúc dữ liệu Heap rất đơn giản và cũng hiệu quả không kém so với cách thông thường. Phần lí thuyết về hàng đợi ưu tiên tôi không nói kĩ nữa vì đã có đầy đủ trong tài liệu chuyên tin. Tôi chỉ tập trung vào phần cài đặt và ứng dụng Heap làm một số bài tập cụ thể. IV. NỘI DUNG: HÀNG ĐỢI ƯU TIÊN VÀ MỘT SỐ ỨNG DỤNG  Khái niệm về hàng đợi ưu tiên:  Hàng đợi ưu tiên là một kiểu dữ liệu danh sách chứa các phần tử của một tập hữu hạn , mỗi phần tử của được gán một mức độ ưu tiên nhất định.  Với một hàng đợi ưu tiên ta có hai thao tác chính: + Push(): Đẩy vào hàng đợi ưu tiên. + Pop(): Trả về phần tử có mức độ ưu tiên lớn nhất trong hàng đợi ưu tiên và loại bỏ phần tử đó khỏi hàng đợi ưu tiên.  Cài đặt hàng đợi ưu tiên Để cài đặt hàng đợi ưu tiên ta sử dụng cấu trúc dữ liệu để biểu diễn danh sách: Heap là một cây nhị phân gần hoàn chỉnh đặc biệt mà phần tử lưu tại mỗi nút luôn có độ ưu tiên lớn hơn hay bằng độ ưu tiên của các phần tử nằm trong hai nhánh con.  Biểu diễn Heap  Một dãy khóa là biểu diễn của một cây nhị phân gần hoàn chỉnh mà lưu trong nút thì nút cha nút là và nút con trái là , con phải là . Ta dùng phương pháp này để biểu diễn Heap: + nheap là số phần tử thực sự đang nằm trong hàng đợi ưu tiên. + heap[1..nheap] lưu các khóa gồm hai thành phần (pos, value: tương ứng là vị trí I của khóa và giá trị p[i] của khóa) trong hàng đợi ưu tiên. Mảng này biểu diễn một cây nhị phân gần hoàn chỉnh mà nút là cha của nút con và . Ta có và .  Khai báo Type Tnode=record Pos,value:longint; End; Var Nheap:longint; Heap:array[1..MaxNheap] of Tnode;  Khởi tạo hàng đợi ưu tiên Procedure Init; Begin Nheap:=0; End.  Thủ tục Push(i): thêm i vào cuối hàng đợi và thực hiện chỉnh lại heap Procedure push(i:longint); Var c,x,r:longint; Begin nheap:=nheap+1; //chinh lai heap bang cach di len cac nut cha c:=nheap; Repeat r:=c div 2;//di len nut cha If (r=0) or (heap[r].value≥P[i]) then Break; Heap[c]:=heap[r];//keo nut cha xuong nut con c:=r; //tiep tuc di len Until false; Heap[c].pos:=i;//dat i vao dung vi tri Heap[c].value:=p[i]; End; Vì độ sâu của cây nhị phân gần hoàn chỉnh không vượt quá lg(nheap) nên thủ tục push(i) thực hiện trong thời gian O(lg(nheap)).  Hàm Pop: trả về phần tử có độ ưu tiên cao nhất trong hàng đợi, đưa phần tử cuối về , giảm số phần tử đi . Function Pop:Tnode; Var r,c:longint; Begin Pop:=heap[1];//trả về phần tử ở gốc heap Heap[1]:=heap[nheap];//đưa phần tử cuối về đầu Nheap:=nheap-1;//giam so phan tu di 1 If nheap>1 then//chinh lai heap bang cach di xuong tu nut 1 Begin i:=heap[1].pos; r:=1; Repeat C:=r*2;//đi xuống nút con trái If (cnheap) or (heap[c].value<=p[i]) then break;//dừng nếu r không có nút con nào có độ ưu tiên lớn hơn heap[r]:=heap[c];//kéo nút con lên nút cha r:=c;//tiếp tục đi xuống Until false; Heap[r].pos:=i; //đặt i vào cuối đường đi Heap[r].value:=p[i]; End; End; Thủ tục pop(i) thực hiện trong thời gian O(lg(nheap))  Một số ứng dụng Heap:  Cải tiến thuật toán Dijkstra có thời gian thực hiện O(|V|lg(|V|) Tìm đường đi ngắn nhất từ s đến t: Gọi d[i] là khoảng cách ngắn nhất khi đi từ đỉnh s đến đỉnh i. Hàng đợi ưu tiên là là một cây nhị phân gần hoàn chỉnh đặc biệt mà phần tử lưu tại nút i luôn có d[i] nhỏ hơn hay bằng d[.] của các phần tử nằm trong hai nhánh con. Cải tiến Dijkstra sử dụng Heap như sau: procedure dijkstra(s:longint); var u,v,w:longint; p:graph; x:Tnode; begin for u:=1 to n do d[u]:=oo; d[s]:=0; push(s); repeat x:=pop; u:=x.pos; if d[u]nil do begin v:=p^.v; w:=p^.w; if d[u]+wnil do begin v:=p^.v; w:=p^.w; if dd[v] and (d[v]>w) then begin d[v]:=w; push(v); end; p:=p^.link; end; x:=pop; u:=x.pos; if not dd[u] then continue; count:=count+1; dd[u]:=false;//them dinh u vao cay khung s:=s+d[u]; if count=n then break; until nheap=0; end;  Một số bài tập có sử dụng hàng đợi ưu tiên: Bài 1:SPOJ-Cây khung nhỏ nhất ( HEAP ) Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm cây khung nhỏ nhất của đồ thị G Input Dòng 1: Chứa hai số n, m (1 <= n <= 10000; 1 <= m <= 15000) M dòng tiếp theo, dòng thứ i có dạng ba số nguyên u, v, c. Trong đó (u, v) là chỉ số hai đỉnh đầu mút của cạnh thứ i và c trọng số của cạnh đó (1 <= u, v <= n; 0 <= c <= 10000). Output Gồm 1 dòng duy nhất: Ghi trọng số cây khung nhỏ nhất Example Input 69 121 131 241 232 251 351 361 452 562 Output 5 - Hướng dẫn: bài này đơn giản dung thuật toán Prim + Heap tìm cây khung nhỏ nhất. - Chương trình: const fi='QBMST.inp'; fo='QBMST.out'; oo=1000000000+5; type Graph=^node; node=record v,w:longint; link:Graph; end; Tnode=record Pos,value:longint; End; Var s,n,m,nheap:longint; d:array[0..10000+5] of longint; g:array[0..10000+5] of graph; dd:array[0..10000+5] of boolean; Heap:array[1..10005] of Tnode; x:TNode; Procedure Init; Begin Nheap:=0; End; Procedure push(i:longint); Var c,x,r:longint; Begin nheap:=nheap+1; //chinh lai heap bang cach di len cac nut cha c:=nheap; Repeat r:=c div 2;//di len nut cha If (r=0) or (heap[r].value<=d[i]) then Break; Heap[c]:=heap[r];//keo nut cha xuong nut con c:=r; //tiep tuc di len Until false; Heap[c].pos:=i;//dat i vao dung vi tri Heap[c].value:=d[i]; End; Function Pop:Tnode; Var r,c,i:longint; Begin Pop:=heap[1]; Heap[1]:=heap[nheap]; Nheap:=nheap-1; If nheap>1 then Begin i:=heap[1].pos; r:=1; Repeat C:=r*2; If (c heap[c+1].value) then C:=c+1; If (c>nheap) or (heap[c].value>=d[i]) then break; heap[r]:=heap[c]; r:=c; Until false; Heap[r].pos:=i; Heap[r].value:=d[i]; End; End; procedure Prim; var i,u,v,w,count:longint; p:graph; x:TNode; begin for i:=1 to n do begin d[i]:=oo;dd[i]:=true;end; d[1]:=0; u:=1; count:=0; dd[u]:=false; s:=0; repeat p:=g[u]; while p<>nil do begin v:=p^.v; w:=p^.w; if dd[v] and (d[v]>w) then begin d[v]:=w; push(v); end; p:=p^.link; end; x:=pop; u:=x.pos; if not dd[u] then continue; count:=count+1; dd[u]:=false;//them dinh u vao cay khung s:=s+d[u]; if count=n then break; until nheap=0; end; procedure add(u,v,w:longint); var p:graph; begin new(p); p^.v:=v; p^.w:=w; p^.link:=g[u]; g[u]:=p; end; procedure readf; var begin i,u,v,w:longint; assign(input,fi); reset(input); readln(n,m); for i:=1 to n do g[i]:=nil; for i:=1 to m do begin readln(u,v,w); add(u,v,w); add(v,u,w); end; close(input); end; procedure writef; begin assign(output,fo); rewrite(output); write(s); close(output); end; BEGIN readf; init; prim; writef; END. Bài 2: Vòng đua F1 (Tìm cây khung lớn nhất) Singapore sẽ tổ chức một cuộc đua xe Công Thức 1 vào năm 2008. Trước khi cuộc đua diễn ra, đã xuất hiện một số cuộc đua về đêm trái luật. Chính quyền muốn thiết kế một hệ thống kiểm soát giao thông để bắt giữ các tay đua phạm luật. Hệ thống bao gồm một số camera đặt trên các tuyến đường khác nhau. Để đảm bảo tính hiệu quả cho hệ thống, cần có ít nhất một camera dọc theo mỗi vòng đua. Hệ thống đường ở Singapore có thể được mô tả bởi một dãy các nút giao thông và các đường nối hai chiều (xem hình vẽ). Một vòng đua bao gồm một nút giao thông xuất phát, tiếp theo là đường đi bao gồm ít nhất 3 tuyến đường và cuối cùng quay trở lại điểm xuất phát. Trong một vòng đua, mỗi tuyến đường chỉ được đi qua đúng một lần, theo đúng một hướng. Chi phí để đặt camera phụ thuộc vào tuyến đường được chọn. Các số nhỏ trong hình vẽ cho biết chi phí để đặt camera lên các tuyến đường. Các số lớn xác định các nút giao thông. Camera được đặt trên các tuyến đường chứ không phải tại các nút giao thông. Bạn cần chọn một số tuyến đường sao cho chi phí lắp đặt là thấp nhất đồng thời vẫn đảm bảo có ít nhất một camera dọc theo mỗi vòng đua. Viết chương trính tìm cách đặt các camera theo dõi giao thông sao cho tổng chi phí lắp đặt là thấp nhất. Dữ liệu  Dòng đầu tiên chứa 2 số nguyên n, m ( 1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000) là số nút giao thông và số đường nối. Các nút giao thông được đánh số từ 1 đến n.  m dòng tiếp theo mô tả các đường nối, mỗi dòng bao gồm 3 số nguyên dương cho biết hai đầu mút của tuyến đường và chi phí lắp đặt camera. Chi phí lắp đặt thuộc phạm vi [1, 1000]. Kết qủa In ra 1 số nguyên duy nhất là tổng chi phí lắp đặt thất nhất tìm được. Ví dụ Input 67 Output 6 125 233 145 454 564 633 523 - Hướng dẫn: bài này đơn giản dung thuật toán Prim + Heap tìm cây khung lớn nhất. - Chương trình: chỉnh sửa lại chương trình ở bài trên là đạt yêu cầu. Bài 3. TRÒ CHƠI (Dijktra heap cơ bản) Cho một sơ đồ trên đó có n thành phố đánh số từ 1 đến n. Có m đường, mỗi đường nối 2 thành phố khác nhau (1 ≤ n, m ≤ 105 ). Từ một thành phố ta có thể tới được thành phố khác bằng mạng đường này. Một trong các thành phố là thủ đô. Các đường có độ dài khác nhau. Nếu đường có độ dài c thì trên đường đó có c-1 làng ở các vị trí cách đều nhau (1 ≤ c ≤ 109 ). Các làng đầu tiên và cuối cùng trên đường cách thành phố gần nhất là 1. Có 2 người chơi trò lái ô tô về thủ đô. Người thứ nhất xuất phát từ thành phố s1, người thứ 2 – từ thành phố s2. Mỗi người, đến lượt mình đi – chuyển tới thành phố hoặc làng kề cận trên đường đi qua chổ mình đang đứng hoặc có quyền dừng. Nếu ai đó đang ở một làng thì người kia không được vào làng nào trong số các làng của đường nối 2 thành phố của làng đó. Yêu cầu: Hãy xác định ai là người tới thủ đô trước và đưa ra thông báo First hoặc Second. Dữ liệu: Vào từ file văn bản GAME.INP:  Dòng đầu tiên chứa 2 số nguyên n và m,  Mỗi dòng trong m dòng sau chứa 3 số nguyên a, b và c, cho biết đường nối 2 thành phố a và b có độ dài c,  Dòng cuối cùng chứa 3 số nguyên s1, s2 và t, trong đó t là thủ đô. Kết quả: Đưa ra file văn bản GAME.OUT thông báo First hoặc Second. Ví dụ: GAME.INP 43 GAME.OUT Second 132 323 431 142 - Hướng dẫn: Tìm đường đi ngắn nhất từ đỉnh t đến hai đỉnh s 1 và s2 . Nếu đường đi ngắn nhất từ t đến s1 nhỏ hơn đường đi ngắn nhất từ t đến s2 thì người 1 tới trước ngược lại thì người 2. - Chương trình: const fi='game.inp'; fo='game.out'; MaxN=100005; MaxM=100005; oo=1000000000000000; type Graph=^node; node=record v,w:longint; link:Graph; end; Tnode=record Pos,value:int64; End; var G:array[0..maxN] of Graph; d:array[0..MaxN] of int64; Heap:array[1..2*maxN] of Tnode; N,M,s1,s2,t,nheap:longint; f:text; Procedure Init; Begin Nheap:=0; End; Procedure push(i:longint); Var c,x,r:longint; Begin nheap:=nheap+1; //chinh lai heap bang cach di len cac nut cha c:=nheap; Repeat r:=c div 2;//di len nut cha If (r=0) or (heap[r].value<=d[i]) then Break; Heap[c]:=heap[r];//keo nut cha xuong nut con c:=r; //tiep tuc di len Until false; Heap[c].pos:=i;//dat i vao dung vi tri Heap[c].value:=d[i]; End; Function Pop:Tnode; Var r,c,i:longint; Begin Pop:=heap[1];//tr? v? ph?n t? ? g?c heap Heap[1]:=heap[nheap];//dua ph?n t? cu?i v? d?u Nheap:=nheap-1;//giam so phan tu di 1 If nheap>1 then//chinh lai heap bang cach di xuong tu nut 1 Begin i:=heap[1].pos; r:=1; Repeat C:=r*2;//di xu?ng n£t con tr i If (c heap[c+1].value) then C:=c+1;//chuy?n sang n£t con ph?i c¢ d? uu tiˆn l?n hon If (c>nheap) or (heap[c].value>=d[i]) then break;//d?ng n?u r kh“ng c¢ n£t con n…o c¢ d? uu tiˆn l?n hon heap[r]:=heap[c];//k‚o n£t con lˆn n£t cha r:=c;//ti?p t?c di xu?ng Until false; Heap[r].pos:=i; //d?t i v…o cu?i du?ng di Heap[r].value:=d[i]; End; End; procedure add(u,v,w:longint); var p:graph; begin new(p); p^.v:=v; p^.w:=w; p^.link:=g[u]; g[u]:=p; end; procedure readf; var i,u,v,w:longint; begin assign(f,fi); reset(f); readln(f,n,m); for i:=1 to n do g[i]:=nil; for i:=1 to m do begin readln(f,u,v,w); add(u,v,w); add(v,u,w); end; readln(f,s1,s2,t); close(f); end; procedure writef; begin assign(f,fo); rewrite(f); if d[s1]<=d[s2] then write(f,'First') else write(f,'Second'); close(f); end; procedure dijkstra(s:longint); var u,v,w:longint; p:graph; x:Tnode; begin for u:=1 to n do d[u]:=oo; d[s]:=0; push(s); repeat x:=pop; u:=x.pos; if d[u]nil do begin v:=p^.v; w:=p^.w; if d[u]+w - Xem thêm -