Bài toán tô màu

Chia sẻ: Truong Huong | Ngày: | Loại File: DOC | Số trang:11

Thêm vào BST

Báo xấu

172
lượt xem 28
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài toán tô màu rất quen thuộc với tất cả các bạn. Mà bài toán điển hình chính là bài toán 4 màu được phát biểu như sau : Mọi bản đồ trên mặt phẳng đều có thể tô bằng 4 màu sao cho không có hai nước láng giềng nào lại bị tô cùng 1 màu. Vậy chúng ta sẽ mở rộng bài toán trên thành một bài toán tổng quát mà hầu hết chúng ta đều đã quen thuộc : Cho một đồ thị vô hướng N đỉnh ( N

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài toán tô màu

ài toán tô màu rất quen thuộc với tất cả các bạn. Mà bài toán điển hình chính là bài toán 4 màu được phát biểu như sau : Mọi bản đồ trên mặt phẳng đều có thể tô bằng 4 màu sao cho không có hai nước láng giềng nào lại bị tô cùng 1 màu. Vậy chúng ta sẽ mở rộng bài toán trên thành một bài toán tổng quát mà hầu hết chúng ta đều đã quen thuộc : Cho một đồ thị vô hướng N đỉnh ( N N) then Begin Cap_nhat_min; Exit; End; Ok := false; For i := 1 to somau do If To_duoc_mau(i,k) then Begin Ok := true;
Dat_trang_thai(i,k); { Ghi nhan i co mau k, va danh so cac dinh ke voi i phai co mau khac i } Try(k+1); Tra_trang_thai(i,k); end; if (ok = false) { inc(somau); Dat_trang_thai(somau,k); Try(k+1); Tra_trang_thai(somau,k); Dec(somau); } End; Tuy nhiên với dữ liệu lớn một chút thì thuật toán Duyệt sẽ không tối ưu về mặt thời gian. Do đó chúng ta sẽ áp dụng thuật toán tham lam để giải bài toán trên. Thuật toán 1 : Tư tưởng chặt nhị phân rồi tham lam: Dau = 0; Cuoi = N; { số màu tối đa có thể tô } While (cuoi > dau) do Begin
Lim := (dau + cuoi ) div 2; If (To_duoc) then cuoi = lim else dau = lim; End; Chính là đáp án cần tìm. Lim = cuoi; Trongthủ tục To_duoc bạn áp dụng thuật toán tham lam . Có nhiều cách cho bạn lựa chọn. Sau đây là một cách : Tại mỗi bước bạn tìm tập có nhiều đỉnh nhất thỏa mãn và tô màu cho chúng. Muốn tìm như vậy mỗi lần bạn tìm đỉnh kề với ít đỉnh nhất mà không kề với đỉnh đã có trong tập đang xét ta cập nhật đỉnh đó vào tập đỉnh có thể tô màu. Cứ làm như vậy, nếu số tập tìm được > Lim thì sẽ không To_duoc còn ngược lại số tập
u ( a[v,w] =1 a[u,w] =1 and a[w,u] = 1 ) -Bước 4 : Lập lại bước 3 cho đến khi v = 0. -Bước 5 : Lặp lại bước 1 cho đến khi tô hết mầu các đỉnh của đồ thị. Sau đây là đoạn chương trình mô tả thuật toán trên : {$Q+,R+,B-,N+} var somau: integer; { Lưu trữ số màu cần tô } N : integer; { Số đỉnh của đồ thị } color : array[1..100] of integer; { Mảng lưu mầu của đỉnh đồ thị, color [i] = 0 nghĩa là đỉnh i chưa được tô màu } a : array[1..100,1..100]of integer; { a[u,v] = 1 tức hai đỉnh u và c có cạnh nối, a[u,v] = 0 tức hai đỉnh không có cạnh nối} count : integer; { Đếm số đỉnh đã tô màu ,Count = N ngừng chương trình } function dinh_bac_max : integer; { Hàm tìm ra đỉnh có bậc lớn nhất } var max,dem,i,j,u : integer; begin max := -1;{Vi co the co dinh co bac la 0} for i :=1to N do if color[i] = 0 then { Xét các đỉnh chưa được tô màu để tìm ra đỉnh bậc lớn nhất }
begin dem := 0; for j :=1 to n do if (color[j] = 0) and (a[i][j] = 1) then inc(dem); if (dem > max) then { Cập nhật giá trị lớn nhất } begin max := dem; u := i; end; end; dinh_bac_max := u; end; procedure tomau(u : integer); begin count := count + 1; color[u] := somau; end; procedure tim_dinh_cung_mau(u : integer; var v : integer); var i,j,k,max,dem : integer;
begin max := 0; { Max ở đây phải gán là 0 , do nếu tồn tại v thì bậc lớn nhất của v phải > 0 } for i := 1 to n do if (color[i] = 0) and (a[u][i] = 0) then { Xét các đỉnh mà u không kề mà đi đến u qua duy nhất 1 đỉnh khác } begin dem := 0; for j := 1 to n do if (color[j] = 0) and (a[i][j] = 1 ) and (a[u][j] = 1) theninc(dem); if (dem > max) then { Cập nhật giá trị max } begin max := dem; v := i; end; end; if (v > 0) then exit; { Nếu tồn tại v chưa tô màu đi đến được u thông qua duy nhất 1 đỉnh khác } max := -1; { Ở đây max phải = 0 vì có thể tồn tại v mà bậc chỉ là 0 } for i :=1 to n do if (color[i] = 0) and (a[u][i] =0) then { Xét các đỉnh i không kề với u và chư
được tô màu với số đỉnh lớn nhất } begin dem := 0; for j := 1 to n do if (color[j] = 0) and (a[i][j] = 1) then inc(dem); if (dem > max) then { Cập nhật giá trị lớn nhất } begin max := dem; v := i; end; end; end; procedure Nhapdinh(u,v : integer); { Nhập 2 đỉnh u và v coi như một đỉnh } var i : integer; begin for i := 1 to n do if a[v,i] = 1 then { Đỉnh i kề với đỉnh v thì coi như nó kề với đỉnh u } begin a[u,i] = 1; a[i,u] = 1;
end; end; procedure To_Mau; { Thủ tục tô màu để tìm ra số màu ít nhất } var u, v : integer; begin somau := 0; repeat somau := somau+1; u := dinh_bac_max; { u là đỉnh có bậc lớn nhất } tomau(u); { gán màu cho đỉnh u } repeat tim_dinh_cung_mau(u,v); { Tìm đỉnh v có thể tô màu giống mầu của u } if (v > 0) then begin tomau(v); { Gán mầu cho đỉnh v } nhap_dinh(u,v); { Nhập 2 đỉnh u,v coi như một đỉnh } end; until (v = 0); until (count = n); end;
Thuật toán trên chạy với tốc độ khá nhanh và rất hiệu quả. Độ chính xác của thuật toán trên là rất cao nếu không nói là thuật toán chuẩn. Trong trường hợp tồi tệ nhất cài đặt theo ma trận kề, độ phức tạp của thuật toán trên là O(n 3). Để cải tiến tốc độ cho thuật toán trên ta có thể sử dụng danh sách kề hoặc danh sách liên kết. Khi đó độ phức tạp thuật toán chỉ cỡ khoảng O(n2log(n)). Muốn cải tiến hơn nữa thì tại mỗi bước ta cập nhật số đỉnh kề của một đỉnh để tăng tốc độ của hàm tìm đỉnh max ( u )và đỉnh tô màu cùng với u ( v ) . Khi đó độ phức tạp thuật toán chỉ khoảng O(N2) .Tuy nhiên cài đặt khá rắc rối. Theo tôi cách tốt nhất là bạn cài đặt theo danh sách kề ( hoặc danh sách liên kết độ phức tạp là O(n2log(n)); ) Sau đây là một vài bài toán ứng dụng của thuật toán nêu trên: Bai 1 :XẾP LỊCH THI Một số trường đại học tổ chức học theo tín chỉ. Nếu sinh viên tích lũy đủ số chứng chỉ cho một số môn quy định của một ngành là có quyền nhận bằng tốt nghiệp của ngành đó. Đối với các đại học như thế, việc học và thi không tổ chứa theo lớp mà theo các môn học. Hàng năm nhà trường thông báo các môn sẽ học để sinh viên tự đăng ký học các môn học theo ngành mình chọn. Cuối năm nhà trường tổ chức thi cho các môn đã giảng trong năm. Mỗi môn thi trong một ngày nhưng trong một ngày có thể tổ chức thi nhiều môn. Do một sinh viên có thể đăng ký thi nhiều môn nên lịch thi cần phải bố trí để nếu có một sinh viên đăng ký thi hai môn nào đó thì các môn đó không được thi cùng ngày. Yêu cầu : Hãy xếp lịch thi sao cho tổng số ngày thi càng ít càng tốt. Input : LICHTHI.INP + M , N : lần lượt là số thí sinh và số môn học ( M
không đăng ký thi môn thứ j. Output : LICHTHI.OUT + Gồm N dòng mỗi dòng có một số tự nhiên. Số ở dòng thứ i là ngày thi tương ứng đối với môn thứ i. Ví dụ : LICHTHI.INP LICHTHI.OUT 10 8 1 10111000 1 01101100 2 10001011 3 01101010 4 10001101 3 00111000 3 00011001 2 01101100 10001011 01001101 Gợi ý : Tư tưởng thuật toán của bài toán trên là đưa về bài toán tô màu đồ thị. Ta xây dựng đồ thị như sau : + Mỗi đỉnh của đồ thị là một môn học (
học 2 môn đó. Như vậy ta xây dựng được một đồ thị vô hướng N đỉnh, trong đó a[i,j] = 1 nếu có cạnh nối, a[i,j] = 0 nếu không có cạnh nối. Sau khi xây dựng được đồ thị trên ta áp dụng thuật toán trên . Ta sẽ tìm ra được kết quả ( số ngày ít nhất cần tổ chức thi ). Trên đây tôi đã trình bày cho các bạn một giải thuật của bài toán tô màu. Hi vọng sẽ giúp ích cho các bạn. Có gì thắc mắc các bạn có thể liên hệ với tôi theo địa chỉ mail : khanhtn09@yahoo.com. Chúc các bạn thành công !!! School@net