Câu 1

1. Tìm kiếm theo chiều rộng

*  Ý tưởng:

Tại mỗi bước ta sẽ chọn trạng thái để phát triển là trạng thái đc sinh ra đầu tiên trong số tất cả các trạng thái đang chờ phát triển.

* Giải thuật

     Procedure Tk_rong;

Begin

     Khởi tạo L chỉ chứa trạng thái đầu;

While true do

       Begin

                If  L rỗng then

            Begin

                    Tìm kiếm thất bại;

                    Exit;

             End;

Loại phần tử u đứng đầu danh sách L;

    If u kết thúc then

Begin

   Tìm kiếm thành công;

   Exit;

End;

   For với mỗi v con trỏ của u do

   Đưa v vào cuối L;

   Father(v) = u;

          End;

End;

* Nhận xét

-Vì trạng thái nào sinh ra trước sẽ đc kiểm tra trước. Do đó, L đc xử lý như hàng đợi.

-Để kt 1 trạng thái U nào đó là trạng thái kết thúc k^0 ta thực tế phải xem U có thỏa mản 1 số đk nào đó k^0.

-Nếu bài toán có nghiệm thì chắc chắn bài toán tìm ra nghiệm(dù đồ thị lớn tới mức nào)

-Khi bài toán vô nghiệm thì thuật toán sẽ dừng và thông báo vô nghiệm.

-Độ phức tạp 0(b^d)

-Đối với những đồ thị k0 gian trạng thái lớn và độ sâu tk lớn sẽ xảy ra hiện tượng bùng nổ tổ hợp và việc áp dụng thuật toán là k0 khả thi.

2. Tìm kiếm theo chiều sâu

* Ý tưởng: Tại mỗi bước trạng thái đc chọn để chờ phát triển là trạng thái đc sinh ra sau cùng trong số tất cả các trạng thái đang chờ phát triển.

* Giải thuật

Procedure Tk_sau;

Begin

     Khởi tạo L chỉ chứa trạng thái đầu;

While true do

       Begin

                If  L rỗng then

            Begin

                    Tìm kiếm thất bại;

                    Exit;

             End;

Loại phần tử u đứng đầu danh sách L;

    If u kết thúc then

Begin

   Tìm kiếm thành công;

   Exit;

End;

   For với mỗi v con trỏ của u do

      Begin

         If v chưa xét then

            Begin

               Đưa v vào đầu L;

               Father(v) = u;

                                 End;

                           End;

         End;

End;

* Nhận xét

 - Độ phức tạp : 0(b^d)

 - Với các đthị có chiều sâu nhỏ thì thuật toán hoạt động rất tốt

 -  Nếu đthị có 1 nhánh vô hạn mà nghiệm lại k0 nằm trên nhánh đó nếu ta xét nhánh đó trước nhánh có nghiệm thì thuật toán sẽ k^0 tìm đc nghiệm.

 - Vì tk theo chiều sâu nên tính hướng đích của thuật toán cao hơn tk theo chiều rộng.

3. Tìm kiếm tốt nhất đầu tiên

* Ý tưởng

Là tk theo chiều rộng nhưng đc hướng dẫn bởi hàm đánh giá. Cụ thể tại mỗi bước ta sẽ ktra trạng thái có giá trị hàm đánh giá nhỏ nhất trong số tất cả các trạng thái đang chờ phát triển.

* Giải thuật  

Procedure Tk_totnhat;

Begin

     Khởi tạo L chỉ chứa đỉnh đầu;

While true do

       Begin

                If  L rỗng then

            Begin

                    Tìm kiếm thất bại;

                    Exit;

             End;

Loại phần tử u đứng đầu danh sách L;

    If u kết thúc then

Begin

   Tìm kiếm thành công;

   Exit;

End;

   For với mỗi v kề u do

        Begin

   Đưa v vào L;

   Father(v) = u;

                             End;

           Sắp xếp L tăng dần theo giá trị hàm đánh giá;

          End;

End;

* Nhận xét

- Sắp xếp :

                 + mất 2 vòng lặp 0(n^2)

                 + 0(n.log2n)

- Tìm kiếm : độ phức tạp dùng 1 vòng lặp 0(n) vì vậy dùng cách 2 tốt hơn

Cách 2

     Procedure Tk_totnhat;

Begin

     Khởi tạo L chỉ chứa đỉnh đầu;

While true do

                If  L rỗng then

            Begin

                    Tìm kiếm thất bại;

                    Exit;

             End;

Loại phần tử u đứng đầu danh sách L;

    If U kết thúc then

Begin

   Tìm kiếm thành công;

   Exit;

End;

   For với mỗi v kề u do

Begin

   Đưa v vào L;

   Father(v) = u;

                      End;

End;

4. Tìm kiếm leo đồi

* Ý tưởng: Tại mỗi bước ta sẽ ktra đỉnh có giá trị hàm đánh giá nhỏ nhất trong số các đỉnh con của đỉnh vừa đc phát triển ở bước trước đó

* Giải thuật

     Procedure Tk_leodoi;

Begin

     Khởi tạo L chỉ chứa đỉnh đầu; L1= null;

While true do

                If  L rỗng then

            Begin

                    Tìm kiếm thất bại;

                    Exit;

             End;

Loại phần tử u đứng đầu danh sách L;

    If u kết thúc then

Begin

   Tìm kiếm thành công;

   Exit;

End;

   For với mỗi v kề u do

Begin

   Đưa v vào L1;

   Father(v) = u;

                      End;

Sắp xếp L1 tăng dần theo giá trị của hàm đánh giá;

Nối L1 vào đầu danh sách L;

End;

End;

5. Tìm kiếm theo thuật toán A*

* Ý tưởng

Thuật toán A* là thuật toán tk sử dụng kỹ thuật tốt nhất đầu tiên với hàm đánh giá là f(x). Tại mỗi bước đỉnh đc ktra sẽ là đỉnh có giá trị f(x) nhỏ nhất trong số tất cả các đỉnh đang chờ xem xét.

* Giải thuật

     Procedure A*;

Begin

     Khởi tạo L chỉ chứa đỉnh đầu; L= null;

While true do

                If  L rỗng then

            Begin

                    Tìm kiếm thất bại;

                    Exit;

             End;

Loại phần tử U đứng đầu danh sách L;

    If U kết thúc then

Begin

   Tìm kiếm thành công;

   Exit;

End;

   For với mỗi v kề U do

Begin

   g(v):=g(u)+(u,v);

   f(v):=g(v)+h(v);

Đặt u vào đầu danh sách L;

                      End;

Sắp xếp danh sách L theo thứ tự tăng dần của hàm f sao cho f có giá trị min

End;

End;

* Nhận xét

Người ta chứng minh đc rằng hàm đánh giá h(u) là hàm đánh giá thấp, trong trường hợp đặc biệt (h(u)=0u ) thì thuật toán A* là thuật toán tối ưu, ngoài ra nếu độ dài của các cung k0<1 số dương  nào đó thì thuật toán A* là thuật toán đầy đủ với ý nghĩa luôn đúng và luôn tìm đc ra nghiệm

Trong trường hợp đặc biệt h(u)=0 với mọi u =>f(u)=g(u) thì khi đó thuật toán A* trỏ thành thuật toán tốt nhất đầu tiên với hàm đấnh giá là g(u). Thuật toán A* là 1 trong số thuật toán đầy đủ và tối ưu trong vấn đề tìm đường đi ngắn nhất.

6. Thuật toán nhánh cận

* Ý tưởng

Là thuật toán sử dụng phương pháp tk leo đồi với hàm đánh giá S(u). Tại mỗi bước ta sẽ phát triển trạng thái u trong số tất cả trạng thái con của trạng thái vừa đc phát triển bước trước.Cứ làm như vậy cho tối khi gặp trạng thái X. Khi đó, đương đi từ điểm đầu tới điểm X là đương đi tạm thời. Trong quá trình tk mà gặp 1 trạng thái nào đó ở 1 nhánh mà có giá trị đường đi lớn hỏn đường đi tạm thời thì ta loại bỏ nhánh đó. QT tiếp tục cho tới khi k0 còn trạng thái để kt.

* Giải thuật

     Procedure Tk_nhanhcan;

Begin

     Khởi tạo L chỉ chứa đỉnh đầu;

L1= null;

While true do

                If  L rỗng then

            Begin

                    Tìm kiếm thất bại;

                    Exit;

             End;

Loại phần tử u đứng đầu danh sách L;

    If u kết thúc then

        If g(u)<tam then

Begin

Tam=g(u);

Quay lại a;

End;

If g(u)>=tam then

Quay lại a;

   For với mỗi v kề U do

Begin

   g(v):=g(u)+(u,v);

   f(v):=g(v)+h(v);

Đặt u vào đầu danh sách L1;

                      End;

Sắp xếp L1 tăng dần theo f;

Gán L1 vào đầu L;

Khởi tạo lại L1=null;

End;

End;

7. Thuật toán Vương Hạo

* Ý tưởng

Input: GT1,GT2,...,GTn

           KL1,KL2,...,KLn

Out put: GT=>KL

B1: -chuẩn hóa GT1,GT2,...,GTn

       -đưa các mệnh đề GT vào mệnh đề vế trái.

-chuẩn hóa KLi (i=1->n) đưa vào vế phải

-đưa cặp (VT,VP)=>P

B2: -chừng nào tập P # rỗngthì còn làm

       -lấy 1 cặp(VT,VP) từ P ra nếu VT = rỗng thì

-lấy 1 cặp(VT,VP) từ P ra nếu VT giao VP = rỗng thì

              +chuyển vế, thay dấu

               +nếu VT  thì tách (VT,VP)=(VT1,VP1);(VT2,VP2)

                Đưa các cặp mới vừa tách vào P

        -ngược lại: VT giao VP # rỗng thì1 ĐPCM

        -ngược lại: 1 ĐPCM

* Giải thuật

Procedure vuonghao;

   Begin

         For i:=1 to n do

             Begin

                 Chuanhoa(GTi);

                  VT=VT giao {GTi};

             End;

                  For i:=1 to m do

              Begin

                  Chuanhoa(KLi);

                  VP=VP giao {KLi};

               End;

              (VT,VP) giao P;

While (P# rỗng) do

              Begin

                  Chuyenve(VT,VP);

                  Thaydau(VT,VP);

If (VT giao VP = rỗng) then

               If not tach(Vt,VP) then

                      Begin

                             Thatbai;

                              Exit;

                       End

Else

                  Đưa cặp VT,VP mới tách vào P;

Else

                  Thành công; end;

Else

                   Thành công;

End;

* Nhận xét

- chuyển vế: là thủ tục chuyển các giat thiết i và kết luận j ở dạng phủ định sang vế bên kia.

- thay dấu: có quyền thay đấu hội ở bên trái và dấu tuyển ở bên phải bằng dấu phẩy.

- tách: nếu ở VT(VP) phép toán tuyển (v), KL đó ta có thể tách mệnh đề này ra làm 2 mệnh đề sau đó kết hợp với từng mệnh đề này với phàn còn lại để có các cặp VT, Vp mới.

-> từ chứng minh trên ta suy ra phát biểu trên là đúng.

- chỉ cần k^0 tìm thấy 1 sự mâu thuẫn thì ta KL phát biểu trên là sai.

8. Thuật toán Robinson

* Ý tưởng

Thực chất phương pháp hợp giải do R. đề xuất là CM bằng phản chứng, để CM từ GT có thể suy ra KL người ta lấy phủ định của KL hợp cùng GT. Nếu bằng 1 cách nào đó suy ra đc mâu thuẫn thì quá trình CM thành công.

* Giải thuật

Procedure robinson;

  Begin

      For i:=1 to n do

         Begin

                 Chuanhoa(GTi);

                 P=P hợp{GTi};

         End;

            For i:=1 to n do

            Begin

                 Chuanhoa(KLi);

                 P=P họp {KLi};

            End;

If mauthuan(P) then

           Begin

             Thành công; Exit; end;

              P1= rỗng;

While ((P<>P1) and not mauthuan(P))

             Begin

            P1=P; hopgiai(P);

            End;

If mauthuan(P) then thành công;

Else thất bại;

End;

* Viết hàm mauthuan(P)

Function mt(P):boolean;

Var kt:boolean;

   Begin

     Kt:=false;

  For với mỗi p thuoc P do

            For với mỗi q thuoc P và qdo

               If (q= >P) then kt:=true;

mt=kt;

end;

procedure hopgiai(P);

begin

               for với mỗi u thuoc P và q # u do

                   if (q=a  v  b) and (u=┐a v b) then

đưa cặp P=Pgiao{b v c)};

end;

* Nhận xét

 - thuật toán R. là thuật toán CM từ GT có thể suy ra đc KL, CM đi tìm sự mâu thuẫn lấy phủ định của KL hợp cùng GT  để tìm ra sự mâu thuẫn thì quá trình thành công.

9. Thuật toán suy diễn tiến

* Ý tưởng

Input: - tập mệnh đề: GT

            -tập mệnh đề:KL

            -tập luật:R chứa các luật dạng:P1 /\P2 .../\ Pn->q

Out put: - KL: từ GT có thể suy ra KL hay không?

            - GT có thể suy ra KL khi sau quá trình suy diễn thì KL là con của GT( KLchua trong GT)

Căn cứ vào tập luật ta sẽ biến đổi tập GT như sau:

Nếu có luật r: P1/\ P2/\ .../\ Pn/\q

Trong đó: các Pi  thuoc GT  thì GT=GTgiao {q}. Cứ làm như vậy cho đến khi áp dụng hết các luật có thể, nếu KL chứa trong GT thì suy ra ĐFCM. Ngược lại thất bại.

* Giải thuật

Begin

          tg=GT;

           S=loc(R,tg);

While (KL chua  tg) and (S#0) do

Begin

r =get(s);

tg=tg hop {q};

right(r);

R=R\{r};

S=loc(R,tg);

End;

       If   KLtg then

Thành công;

Else

Thất bại;

End;