Thuật toán mô hình cây
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 (145.26 KB, 4 trang )
ứng dụng mô hình cây
Ngô Quốc Hoàn
Cây là đồ thị vô hướng liên thông và không có chu trình. Khái niệm cây lần đầu tiên được
Cayley đưa ra vào năm 1857, khi ông sử dụng chúng để thể hiện một số dạng cấu trúc
phân tử của các hợp chất hoá học hữu cơ. Cây còn có nhiều các ứng dụng rộng rãi trong
rất nhiều các lĩnh vực khác nhau. Đặc biệt trong tin học, cây được dùng để xây dựng các
thuật toán tổ chức thư mục, các thuật toán mã hoá, nén và giải nén dữ liệu, các thuật toán
tìm kiếm.. Trong bài viết này tôi xin trình bày với các bạn ứng dụng mô hình cây vào việc
giải một số bài toán tin học cụ thể.
Bài toán 1. Song liên thông
Cho một đồ thị vô hướng liên thông có N đỉnh và M cạnh, ta tạm định nghĩa nút cầu trong
một đồ thị liên thông là một nút mà nếu xoá nó khỏi đồ thị thì đồ thị sẽ bị tách thành các
thành phần liên thông khác nhau, đồ thị không có nút cầu được gọi là đồ thị song liên
thông. Hãy tìm đồ thị song liên thông với số đỉnh nhiều nhất và là con của đồ thị đã cho.
Dữ liệu vào file: slt.inp
- Dòng đầu tiên ghi hai số N, M (N<=100)
- M dòng tiếp theo mỗi dòng chứa 2 số (x,y) thể hiện một cạnh của đồ thị.
Dữ liệu ra file: slt.out
- Dòng đầu tiên ghi K (số đỉnh của đồ thị con).
- Dòng thứ 2 chứa K số thể hiện các đỉnh của đồ thị con.
Ví dụ:
Trong đồ thị trên thì các nút cầu là 1, 7, 8. Đồ thị trên có thành phần song liên thông với số
đỉnh nhiều nhất là 1 3 7 5 4 6
Tư tưởng thuật toán:
Bài toán có thể được giải theo mô hình cây như sau:
- Mỗi đỉnh của cây là một tập đỉnh thể hiện cho một đồ thị con. Gốc là tập đỉnh thể hiện đồ
thị ban đầu.
- Giả sử có một đỉnh x={x1...xK}. Ta cần tìm một nút cầu xi trong đồ thị có tập đỉnh
{x1. ..xK} và bỏ nút cầu xưi đi thì đồ thị có tập đỉnh {x1...xK} sẽ bị phân thành những
thành phần liên thông có các tập đỉnh là y1</SUB>={Y1.1...y1.L} ..
yP</SUB>={YP.1..yP.M}, với k, L, M ≥ 1, L + M = k - 1, p >1. Lúc đó ta xây dựng p nút:
z1</SUB>=Y1 hợp với {xi},…, zP</SUB>=YP hợp với {xi}là nút con của x.
- Nếu không tìm được một nút cầu xi nào thì đỉnh x là nút lá và tập x={x1...xK} là tập các
đỉnh của một đồ thị song liên thông.
- Vậy tập các nút lá là tập các đồ thị con song liên thông của đồ thị ban đầu. Chúng ta phải
tìm một nút lá có số phần tử lớn nhất.
Hình vẽ mô hình cây minh họa ví dụ trên
Trên đây chỉ là ý tưởng, phần cài đặt chi tiết để dành cho các bạn, nếu bạn nào muốn có
toàn văn chương trình bài này thì xin liên hệ với tôi theo địa chỉ
Sau đây tôi xin chuyển sang bài thứ 2:
Bài toán 2. Lưới đánh cá:
Cho một lưới hình chữ nhật, có các cạnh song song với các trục tọa độ. Người ta nối các
dây của lưới chính là các đoạn thẳng nối 2 điểm thuộc biên của lưới. Mắt lưới là 1 đa giác
hạn bởi các đoạn dây và khung lưới. Tìm một mắt lưới có diện tích lớn nhất.
Dữ liệu vào file luoidc.inp:
- Dòng đầu tiên là số n, x1, y1, xư2, y2 (n ≤ 100). Trong đó n là số đoạn dây của lưới,
(x1, y1), (xư2, y2 ) lần lượt là tọa độ đỉnh trên trái và dưới phải của hình chữ nhật, các số
ghi cách nhau ít nhất một dấu cách
- N dòng tiếp theo mỗi dòng chứa 4 số x, y, z, t. Trong đó (x, y), (z, t) là toạ độ hai đầu mút
của một đoạn dây.
Dữ liệu ra file luoidc.out: ghi diện tích của mắt lưới lớn nhất, kết quả lấy đến 10 chữ số
thập phân.
Ví dụ:
trong ví dụ trên thì ta thấy mắt lưới số 4 là mắt lưới lớn nhất có diện tích xấp xỉ bằng
6,3333333333.
Tư tưởng thuật toán:
Ta có thể xây dựng mô hình cây nhị phân để giải bài toán như sau:
- Mỗi nút của cây là một đa giác được tạo ra từ các đoạn thẳng (đoạn dây) và các biên của
lưới. Gốc của cây chính là lưới chữ nhật ban đầu.
- Với mỗi nút X biểu diễn một đa giác p, tìm một đoạn thẳng có số hiệu i nhỏ nhất chia đa
giác này thành hai đa giác p 1 , p 2 . Ta xây dựng hai nút con của X là X1 và X2 . X1 biểu
diễn đa giác p1, X2 biểu diễn đa giác p2.
- Nếu không có đoạn thẳng nào chia đa giác thành 2 phần thì nút X là nút lá và đa giác p là
một mắt lưới.
- Lúc này bài toán trở thành tìm một nút lá biểu diễn đa giác có dịên tích lớn nhất.
Hình vẽ cây nhị phân mô tả ví dụ trên:
Dựa trên tư tưởng trên ta có thể xây dựng một chương trình con đệ quy để giải bài toán
trên như sau:
Procedure chiăp:poligon; i:integer);
{ thủ tục chia đa giác P bởi đoạn thẳng có số hiệu từ i trở đi}
var j:integer;
p1,p2:poligon;
begin
for j:=i to n do
if chiaduoc(p,j,p1,p2) then
{thủ tục chiaduoc có nhiệm vụ: kiểm tra xem đoạn thẳng j có chia đựơc đa giác p thành hai
đa giac con p1 và p2 không }
begin
chiăp1,j+1);
chiăp2,j+1);
exit;
end;
s:=dientich(p); {hàm dientich để tính diện tích đa giác P}
if s>smax then smax:=s; {cập nhật kỉ lục }
end;
