Bai toan co so lieu lon

Kỹ thuật dùng Bộ nhớ ảo trong các bài toán có số liệu lớn
I. Mở đầu:`Bộ nhớ ảó (Virtual Memory − VM) là thuật ngữ chỉ việc hệ điều hànhđã tự nâng cấp dung lượng bộ nhớ thực (RAM) bằng cách sử dụng mộtkhông gian đĩa cứng làm nơi lưu trữ dữ liệu tạm thời lúc đang xửlí. Nhờ đó, tránh được việc đứng máy. Dù sao, con RAM của máy tínhcòn lớn đến hàng trăm Mb, trong khi con `RAM` của Pascal chúng ta chỉcó 64Kb, nghĩa là chứa khoảng 32 000 phần tử là tối đa. Vậy thì làmsao giải quyết những bài toán yêu cầu tổ chức dữ liệu lớn? Vấn đềmở rộng bộ nhớ của Pascal bằng VM được đặt ra và rất đáng lưu tâm.ở đây, tôi xin trình bày cách sử dụng VM bằng kiểu file, một kiểu dữliệu quen thuộc, sau khi đã lĩnh hội được, các bạn có thể sáng tạocho mình một phương pháp tối ưu. II. Bài toán: Ta hãy xétlại bài toán xếp ba lô quen thuộc: Cho n vật có thể tích A[i] và giátrị B[i]. Hãy liệt kê ra chỉ số của 1 số vật sao cho tổng thể tích củachúng không vượt V cho trước và tổng giá trị là lớn nhất. Phương phápquen thuộc mà chúng ta được học là quy hoạch động: 1. Lập bảngF[i,j] cho biết tổng giá trị max của i vật được chọn từ 1 đến i vàgiá trị không vượt quá j. 2. Lập hàmquy hoạch động tính F[i,j] theo F[i-1,ji] (ji=1..n) để tìm F[n,v]. 3. Truy xuấtngược các chỉ số các vật được chọn. Vấn đề là:Với V ≤ 10000, n ≤ 10000 (giới hạn thêm
) thì sẽ không giải quyết theo phương pháp bình thường được vì bảngF sẽ có 108 phần tử (quá lớn so với 32000). Vì thế ta sẽchia bảng thành n hàng, mỗi hàng V số, và vì tính giá trị hàng i chỉphụ thuộc vào hàng i-1 nên ta sẽ xử lí từng hàng một bằng bảng mộtchiều duy nhất, xong hàng nàoghi lại hàng đó ra file, để dành sau truy xuất. Cụ thể, ở mỗi bướctính giá trị hàng i: + F1[1..V] làbảng lưu các giá trị hàng i-1, F2[1..V] là bảng lưu giá trị hàng i (cầntính), do V ≤ 10000nên giá trị F1[i],F2[i] đủ lớn để xử lí được. + Tiến hànhđọc giá trị A[i]; B[i] + Lập hàmtính F2[j] theo F1[jj-1] với tham số A[i], B[i] (j,jj=1..n) + GhiF2[1..v] vào file tạm, gán F1:=F2 cho lần xử lý kế tiếp. Như vậyfile tạm sẽ chứa n x v số, tương ứng với giá trị bảng F, nhưng tađã tích hợp nó thành 2 mảng một chiều F1, F2 duy nhất với VM là filechứa tạm. Tuy nhiên,việc file truy xuất ngược yêu cầu đọc file từ dưới lên, trong khifile text chỉ cho đọc tuần tự từ trên xuống. Do đó, Chúng ta phải thựchiện 1 `thao tác nhỏ` ghi ngược file để tạm thời truy xuất. Procedureinnguoc; Begin {Mở filecần ghi ngược} For i:=ndownto 1 do Begin {Mởfile tạm để đọc, xuống dòng n-1 lần, đọc dòng hiện thời của con trỏvà ghi vào file ngược, đóng file đọc} End; End; Như vậyfile tạm ban đầu sẽ được mở ra đóng lại n lần. Vấn đề còn lạixin dành cho bạn đọc, tất nhiên việc truy xuất cũng dựa vào quan hệhai dòng liên tiếp nên ta dùng lại 2 mảng F1,F2 ban nãy để giải quyết.Lưu ý hàng n của bảng F giờ đã thành hàng i của file ngược, nên việctruy xuất các chỉ số có ngược lại một chút. Chương trình:(xem phụ lục 1) Như thế, kĩthuật dùng VM giống như việc mã hoá vậy: - DùngF1, F2 giả làm các hàng liên tiếp để ghi bảng giá trị vào file tạm. - In ngược(nếu cách làm bắt buộc) rồi lại dùng F1, F2 để xuất kết quả ra. VM đã chophép ta sử dụng bộ nhớ gấp 3125 lần (đối với bài toán trên), mộtcon số không nhỏ phải không các bạn? Nhưng phương pháp này cũng bộclộ 2 nhược điểm: chỉ áp dụng cho các phép tính tuần tự, tăng độphức tạp chương trình nên thời gian chạy lâu. Vì thế, nóđặc biệt thích hợp cho quy hoạchđộng và đồ thị, nhiều lúc đây còn là phương án duy nhất vượtqua rào cản về dung lượng. Việc cân nhắc giữa độ phức tạp và độlớn bộ nhớ là việc đáng suy ngẫm, để cải thiện tối đa bài toán. Ví dụ: Dướiđây cho