Trí tuệ nhân tạo:

I, thuật toán  tô màu:

    Lặp lại các bước sau đền khi tô hết các đỉnh:

            B1: Chọn đỉnh có bậc cao nhất để tô màu A.

            B2: Hạ bậc đỉnh vừa tô xuông bậc 0, những đỉnh có bậc liên quan hạ: bậc – 1.

            B3: Đành dấu các bậc liên hệ( bậc – 1 ), cấm tô màu 1.

   Chú ý: trong bảng tô màu thông thường người ta dùng dấu – để biểu thị là bậc 0, số     1 trong ô vuông là mầu đã tô và số 1 trong ô vuông gạch chéo là màu cấm tô.

II, Các thuật giải tìm kiếm:

1,Thuật giải AT:

            Thực hiện lặp đi lặp lại các bước sau đến khi gặp tập đích:

B1: Gán cho Open={điểm gốc}; Vd: open={s};

 B2:  Tìm Tmax(điểm gốc).    Tmax=s

        Tìm các tk của điểm gốc là các điểm xuất phát từ gốc.   các tk của s: A,B,C.

            Tình g(tk)=g(tmax)+cost(tmax,tk)       g(A)= …; g(B)=…;g(C)=…

            Open={A,B,C} a,b,c được sắp xếp từ nhỏ đến lớn

B3: Tìm Tmax của điểm nhỏ nhất, Tmax =A;

Tiếp tục làm theo các bước trên đến khi đi đến điểm thuộc tập đích.

2, Thuật giải A*:

II, Quilan( xây dựng cây định danh):

Một vector V(Aj ) được gọi là vector đơn vị nếu nó chỉ có duy nhất một thành phần có giá trị 1 và những thành phần khác có giá trị 0.

Thuộc tính được chọn để phân hoạch là thuộc tính có nhiều vector đơn vị nhất.

Trở lại ví dụ của chúng ta, ở trạng thái ban đầu (chưa phân hoạch) chúng ta sẽ tính vector đặc trưng cho từng thuộc tính dẫn xuất để tìm ra thuộc tính dùng để phân hoạch. Đầu tiên là thuộc tính màu tóc. Thuộc tính màu tóc có 3 giá trị khác nhau (vàng, đỏ, nâu) nên sẽ có 3 vector đặc trưng tương ứng là :

VTóc (vàng) = ( T(vàng, cháy nắng), T(vàng, không cháy nắng) )

Số người tóc vàng là : 4

Số người tóc vàng và cháy nắng là : 2

Số người tóc vàng và không cháy nắng là : 2

Do đ�

VTóc(vàng) = (2/4 , 2/4) = (0.5, 0.5)

Tương tự

VTóc(nâu) = (0/3, 3/3) = (0,1) (vector đơn vị)

Số người tóc nâu là : 3

Số người tóc nâu và cháy nắng là : 0

Số người tóc nâu và không cháy nắng là : 3

VTóc(đỏ) = (1/1, 0/1) = (1,0) (vector đơn vị)

Tổng số vector đơn vị của thuộc tính tóc vàng là 2

Các thuộc tính khác được tính tương tự, kết quả như sau :

VC.Cao(Cao) = (0/2,2/2) = (0,1)

VC.Cao(T.B) = (2/3,1/3)

VC.Cao(Thấp) = (1/3,2/3)

VC.Nặng (Nhẹ) = (1/2,1/2)

VC.Nặng (T.B) = (1/3,2/3)

VC.Nặng (Nặng) = (1/3,2/3)

VKem (Có) = (3/3,0/3) = (1,0)

VKem (Không) = (3/5,2/5)

Như vậy thuộc tính màu tóc có số vector đơn vị nhiều nhất nên sẽ được chọn để phân hoạch.

Sau khi phân hoạch theo màu tóc xong, chỉ có phân hoạch theo tóc vàng (Pvàng) là còn chứa những người cháy nắng và không cháy nắng nên ta sẽ tiếp tục phân hoạch tập này. Ta sẽ thực hiện thao tác tính vector đặc trưng tương tự đối với các thuộc tính còn lại (chiều cao, cân nặng, dùng kem). Trong phân hoạch Pvàng, tập dữ liệu của chúng ta còn lại là :

VC.Cao(Cao) = (0/1,1/1) = (0,1)

VC.Cao(T.B) = (1/1,0/1) = (1,0)

VC.Cao(Thấp) = (1/2,1/2)

VC.Nặng (Nhẹ) = (1/2,1/2)

VC.Nặng (T.B) = (1/2,1/2)

VC.Nặng (Nặng) = (0,0)

VKem (Có) = (0/2,2/2) = (0,1)

VKem (Không) = (2/2,0/2) = (1,0)

2 thuộc tính dùmg kem và chiều cao đều có 2 vector đơn vị. Tuy nhiên, số phân hoạch của thuộc tính dùng kem là ít hơn nên ta chọn phân hoạch theo thuộc tính dùng kem.

III, thuật giải đo đo hỗn loạn:

Học trong sách