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

IV, Thuật giải vương họa và robinson

a, Vương hạo: 

Bước 1: Ta đưa VT và VP cùa bài toán cần chứng minh về dạng chuẩn      bằng cách:

  Thay các phép toán (tương đương) bằng phép toán →(kéo theo) tương ứng.

  Thay các phép toán →(kéo theo) bằng các phép toán ┐(phủ định),  (phép tuyển) tương ứng.

-Từ các phép toán ┐(phủ định),  (phép tuyển),  (phép hội) ta có dạng chuẩn GT ≡ VT và KL ≡ VP của bài toán cần chứng minh dạng:

          GT1, GT2, GT3,………, GTn → KL1, KL2, KL3,……., KLm

    Bước 2: Chuyển vế này sang vế kia các GTi, KLj có dạng phủ định.

          Chỉ những mệnh đề phủ định đứng độc lập thì mới chuyển vế

GT1, GT2, ┐GT3,….., GTn-1, GTn → KL1, ┐KL2, KL3,…., KLm-1, KLm.

Chuyển vế ta có:

GT1, GT2, KL2,….., GTn-1, GTn → KL1, GT3,  KL3,…., KLm-1, KLm  

                        Bước 3: Thay phép toán Ùở GTi và phép toán Ú ở KLj bằng dấu “,”.

GT1, GT2, a Ù b, GT3,….,, GTn-1, GTn → KL1, c Ú d, KL2,…,          KLm-1, KLm.

                               Bài toán chuyển vể dạng:

GT1, GT2, a , b, GT3,….,, GTn-1, GTn → KL1, c , d , KL2,…, KLm-1, KLm.

                        Bước 4:  Nếu  dòng hiện hành có một trong hai dạng sau:

Dạng 1:

GT1, GT2,…,a Ú b,…, GTn-1, GTn® KL1, KL2,…., KLm-1, KLm

Thì thay bằng hai dòng:

  GT1, GT2,…, a,…, GTn-1, GTn®  KL1, KL2,…., KLm-1, KLm

  GT1, GT2,…, b,…, GTn-1, GTn®  KL1, KL2,…., KLm-1, KLm

Dạng 2:

GT1, GT2,…, GTn-1, GTn® KL1, KL2,…,a Ù b,…, KLm-1, KLm

Thì thay bằng hai dòng:

  GT1, GT2,…., GTn-1, GTn® KL1, KL2,…,a,…, KLm-1, KLm

  GT1, GT2,…., GTn-1, GTn®  KL1, KL2,…,b,…, KLm-1, KLm

- Chúng ta có thể tách cùng lúc nhiều nhóm mệnh đề với nhau, nhưng cách hay nhất là nên chọn một nhóm mệnh đề mà thấy khi tách dòng có mệnh đề trong nhóm mệnh đề đó ở gt giống mệnh đề ở kl. Như vậy ta sẽ giảm được số dòng tách tiết kiệm thời gian.

                  Bước 5:  Một dòng được chứng minh nếu tồn tại chung một mệnh đề ở cả hai vế.

  Ví dụ: a Ùb, c ®c(được chứng minh)

B, Robinson:

Bước 1: Ta đưa VT và VP cùa bài toán cần chứng minh về dạng chuẩn      bằng cách:

  Thay các phép toán (tương đương) bằng phép toán →(kéo theo) tương ứng.

  Thay các phép toán →(kéo theo) bằng các phép toán ┐(phủ định),  (phép tuyển) tương ứng.

-Từ các phép toán ┐(phủ định),  (phép tuyển),  (phép hội) ta có dạng chuẩn GT ≡ VT và KL ≡ VP của bài toán cần chứng minh dạng:

          GT1, GT2, GT3,………, GTn → KL1, KL2, KL3,……., KLm

Bước 2:  Thay phép toán Ùở GTi và phép toán Ú ở KLj bằng dấu “,”.

    Chỉ những mệnh đề phủ định đứng độc lập thì mới chuyển vế

     GT1, GT2, a Ù b, GT3,….,, GTn-1, GTn → KL1, c Ú d, KL2,…,            KLm-1, KLm.

                                   Bài toán chuyển vể dạng:

GT1, GT2, a , b, GT3,….,, GTn-1, GTn → KL1, c , d , KL2,…, KLm-1, KLm.

Bước 3: Biến đổi dòng trên thành danh sách các mệnh đề

{GT1, GT2, a, b, ,… , GTn , ┐KL1, ┐KL2, ┐c, ┐d … , ┐KLm}

Bước 4:Nếu trong danh sách mệnh đề ở bước 2 có 2 mệnh đề đối ngẫu nhau thì bài toán được chứng minh. Ngược lại thì chuyển sang B5. (a và ┐ a gọi là hai mệnh đề đối ngẫu nhau).

Bước 5:Xây dựng một mệnh đề mới bằng cách tuyển một cặp mệnh đề trong danh sách mệnh đề ở bước 2. Nếu mệnh đề mới có các biến mệnh đề đối ngẫu nhau thì các biến đối ngẫu được loại bỏ.

Ví dụ : p Ú ┐qÚr Ú s Ú q

Hai mệnh đề ┐ q, q là đối ngẫu nên sẽ được loại bỏ

p Ú r Ú s .

Bước 6 :Thay thế hai mệnh đề vừa tuyển trong danh sách mệnh đề bằng mệnh đề mới.Áp dụng heuristic cho thuật toán này ”áp dụng hợp giải sau khi  thu được mệnh đề mới {p Ú r Ú s} có thể bỏ 2 mệnh đề cũ {p Ú ┐q } và { r Ú s Ú q}”. Nếu mệnh đề là mệnh đề nguyên tử thì không rút gọn mà chuyển về cuối danh sách. Có thể hợp giải nhiều thứ tự mệnh đề có biến đối ngẫu với  nhau, nhưng cách hay hợp giải mệnh đề nào ra được mâu thuẫn nhanh thì nên chọn.