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;
Bạn đang đọc truyện trên: Truyen2U.Pro