Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
Bảng giá phần mềm
Educations Software

Đại Lý - Chi Nhánh

Bản tin điện tử
 
Đăng nhập/Đăng ký
Bí danh
Mật khẩu
Mã kiểm traMã kiểm tra
Lặp lại mã kiểm tra
Ghi nhớ
 
Quên mật khẩu | Đăng ký mới

 
Giỏ hàng

Xem giỏ hàng


Giỏ hàng chưa có sản phẩm

 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (701 bài viết)
  • Sản phẩm mới (217 bài viết)
  • Dành cho Giáo viên (552 bài viết)
  • Lập trình Scratch (3 bài viết)
  • Mô hình & Giải pháp (155 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (126 bài viết)
  • Hỗ trợ khách hàng (482 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (242 bài viết)
  • Học tiếng Việt (182 bài viết)
  • Thông tin khuyến mại (80 bài viết)
  • Download - Archive- Update (289 bài viết)
  • Các Website hữu ích (71 bài viết)
  • Cùng Học (98 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (74 bài viết)
  • Thông tin tuyển dụng (55 bài viết)
  • School@net 15 năm (153 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (123 bài viết)
  • Khám phá phần mềm (122 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (36 bài viết)
  • Phần mềm cho em (13 bài viết)
  • ĐỐ VUI - THƯ GIÃN (360 bài viết)
  • Các vấn đề giáo dục (1209 bài viết)
  • Bài học trực tuyến (1033 bài viết)
  • Hoàng Sa - Trường Sa (17 bài viết)
  • Vui học đường (276 bài viết)
  • Tin học và Toán học (220 bài viết)
  • Truyện cổ tích - Truyện thiếu nhi (181 bài viết)
  • Việt Nam - 4000 năm lịch sử (97 bài viết)
  • Xem toàn bộ bài viết (8179 bài viết)
  •  
    Thành viên có mặt
    Khách: 6
    Thành viên: 0
    Tổng cộng: 6
     
    Số người truy cập
    Hiện đã có 55894136 lượt người đến thăm trang Web của chúng tôi.

    BÀI TOÁN TÔ MÀU ĐỒ THỊ

    Ngày gửi bài: 23/01/2009
    Số lượt đọc: 3406

    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 <= 200 ), mỗi đỉnh được nối với 1 số đỉnh khác bằng 1 cung nối trực tiếp duy nhất ( không có 2 đỉnh nào có nhiều hơn 1 đường nối trực tiếp ). Bài toán đặt ra là : Hãy tô màu các đỉnh sao cho không có hai đỉnh nào có 2 màu giống nhau mà lại nối trực tiếp với nhau với số màu cần tô là ít nhất.

    Bài toán trên có rất nhiều cách giải. Trong đó cách đơn giản nhất để giải bài toán trên là Duyệt có chặn nhánh. Thuật toán trên khá hiệu quả. Có thể phát biểu qua cách trên như sau :

    Procedure try(k : integer) ;

    Var ok : boolean;

    Begin

    If ( k > 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;

    Lim = cuoi; Chính là đáp án cần tìm.

    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 <= Lim thì có thể To_duoc. Duyệt chặn nhánh thì có thể ra kết quả tối ưu nhưng không đáp ưng nhu cầu về thời gian trong trường hợp N lớn. Còn làm theo thuật toán tham lam thứ nhất thì kết quả sẽ không tối ưu trong nhiều trường hợp.

    Để khắc phục cả 2 khuyết điểm của 2 thuật toán trên, tôi xin đưa ra một thuật toán dựa trên tư tưởng tham lam, nhưng với tư tưởng khá mới mẻ, và thuật toán trên tương đối chuẩn xác .

    Dưới đây là tư tưởng thuật toán:

    -Trước hết ta định nghĩa bậc của một đỉnh làsố đỉnh trên đồ thị chưa được tô mầu mà đỉnh này được nối trực tiếp với đỉnh đang xét bằng một cạnh nối trực tiếp. Nếu đỉnh đó không được nối với bất kỳ đỉnh nào thì bậc của đỉnh đó là 0

    -Bước 1 : Tìm đỉnh có bậc cao nhất trên đồ thị ( gọi là đỉnh u )

    -Bước 2 : Tăng số màu cần tô lên 1 và tô màu cho đỉnh vừa tìm

    -Bước 3 : Tìm đỉnh v để tô màu giống u thỏa mãn các điều kiện sau : v đi đến đỉnh u thông qua duy nhất 1 đỉnh w khác và v có số bậc lớn nhất. Nếu không tìm được đỉnh như vậy ta sẽ tìm đỉnh v có số bậc lớn nhất mà không kề với u. Nếu tìm được v thỏa mãn thì ta tô màu cho v chính là màu của đỉnh u. Sau đó nhập đỉnh u và v vào làm 1 đỉnh. Tức : đỉnh w kể với v thì cũng coi như kề với 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(n3).

    Để 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 <= 1000, N <= 100);

    + M dòng tiếp theo ghi thông tin về đăng ký thi của mỗi sinh viên, mỗi dòng gồm N số 0 hoặc số 1 cách nhau một dấu cách, số thứ j trong dòng thứ i là 1 nếu sinh viên thứ i đăng ký học và thi môn thứ j và bằng 0 nếu sinh viên thứ i 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 0 1 1 1 0 0 0

    0 1 1 0 1 1 0 0

    1 0 0 0 1 0 1 1

    0 1 1 0 1 0 1 0

    1 0 0 0 1 1 0 1

    0 0 1 1 1 0 0 0

    0 0 0 1 1 0 0 1

    0 1 1 0 1 1 0 0

    1 0 0 0 1 0 1 1

    0 1 0 0 1 1 0 1

    1

    1

    2

    3

    4

    3

    3

    2

    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 ( <= 100 )

    + Hai đỉnh của đồ thị được gọi là có cạnh nối nếu có một sinh viên tham gia 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



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 1407 - Nhà 17T2 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Điện thoại: (024) 62511017 - Fax: (024) 62511081
    Email: school.net@hn.vnn.vn / thukhachhang@yahoo.com


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.