Có 3 thầy tu và 3 con quỷ. Làm sao đưa cả 6 qua sông. Biết rằng có 1 chiếc thuyền, thuyền chở 1 lần nhiều nhất là 2, ít nhất là 1. Chú ý rằng số thầy tu ở mỗi bờ không ít hơn số quỷ, nếu không quỷ sẽ ăn thịt thầy tu Giải dạng tốn qua sơng sử dụng prolog *Đề bài: 1, Con quỷ thầy tu: Có thầy tu quỷ Làm đưa cả qua sông Biết rằng có chiếc thuyền, thuyền chở lần nhiều nhất 2, ít nhất Chú ý rằng số thầy tu mỗi bờ không ít số quỷ, nếu không quỷ sẽ ăn thịt thầy tu 2, Nông dân, cáo, ngỗng hạt đậu: Làm cách để đưa qua sông Biết khơng có người nơng dân cạnh bờ cáo ăn ngỗng, ngỗng ăn hạt đậu Bài toán quỷ thầy tu (qua sông) -> Không quan trọng thứ tự 1, mô toán *định nghĩa trạng thái: - Trạng thái ban đầu: ba quỷ ba nhà sư bờ phía bên trái Tương ứng [3,3, 0, 0, 1] - Thông tin số lượng nhà sư quỷ hai bên bờ: [A,B,C,D] đó: + A,B số quỷ, số sư bờ bên trái + C, D số sư, số quỷ bờ bên phải - Trạng thái mục tiêu: Cả nhà sư ba quỷ bờ bên phải, tương ứng với [0, 0, 3, 3, 0] 2, Các thao tác trạng thái: - Chuyển sư từ bờ trái qua bờ phải - Chuyển quỷ từ bờ trái qua bờ phải - Chuyển hai sư từ bờ trái qua bờ phải - Chuyển hai quỷ từ bờ trái qua bờ phải - Chuyển sư quỷ từ bờ trái qua bờ phải - Chuyển sư từ bờ phải qua bờ trái - Chuyển quỷ từ bờ phải qua bờ trái - Chuyển hai sư từ bờ phải qua bờ trái - Chuyển hai quỷ từ bờ phải qua bờ trái - Chuyển sư quỷ từ bờ phải qua bờ trái 3, Các ràng buộc: - Số quỷ phải nhỏ số sư bờ trái phải 4, Phương pháp cài đặt: Biểu diễn trạng thái dạng [A, B, C, D] tương ứng với: - A số sư bờ bên trái, B số quỷ bờ bên trái, C số sư bờ bên phải, D số quỷ bờ bên phải - Trạng thái ban đầu: [3, 3, 0, 0, 1] - Trạng thái mục tiêu: [0, 0, 3, 3, 0] 5, Chương trình cài đặt (prolog) trans([A,B,C,D,1],[X,Y,Z,T,0]):-A>0,B>0,X is A-1,Y is B-1, Z is C+1, T is D+1 trans([A,B,C,D,0],[X,Y,Z,T,1]):-C>0,D>0,X is A+1,Y is B+1, Z is C-1, T is D-1 trans([A,B,C,D,0],[X,B,Z,D,1]):-C>1,X is A+2,Z is C-2 trans([A,B,C,D,1],[X,B,Z,D,0]):-A>1,X is A-2,Z is C+2 trans([A,B,C,D,1],[A,Y,C,T,0]):-B>1,Y is B-2,T is D+2 trans([A,B,C,D,0],[A,Y,C,T,1]):-D>1,Y is B+2,T is D-2 trans([A,B,C,D,0],[X,B,Z,D,1]):-C>0,X is A+1,Z is C-1 trans([A,B,C,D,1],[X,B,Z,D,0]):-A>0,X is A-1,Z is C+1 trans([A,B,C,D,0],[A,Y,C,T,1]):-D>0,Y is B+1,T is D-1 trans([A,B,C,D,1],[A,Y,C,T,0]):-B>0,Y is B-1,T is D+1 dangers([A,B,C,D,_]):-A>=B,C>=D dangers([A,B,0,_,_]):-A>=B dangers([0,_,A,B,_]):-A>=B goal([0,0,3,3,0]) dfs(X,P,[X|P]):-goal(X),! dfs(X,P,L):-trans(X,Y),X\=Y,dangers(Y),\+member(Y,P),dfs(Y,[X|P],L) Bài toán qua sông (nông dân, cáo ,ngỗng hạt đậu): -> quan trọng thứ tự (Cáo ăn ngỗng, ngỗng ăn đậu k có nơng dân cùng) 1, Mơ toán: Định nghĩa trạng thái: - Trạng thái ban đầu nông dân, cáo,ngỗng hạt đậu bờ bên trái Tương ứng: [1,1,1,1,0,0,0,0] - Tráng thái mục tiêu: nông dân, cáo,ngỗng hạt đậu bờ bên phải, tương ứng [0,0,0,0,1,1,1,1] - vị trí tương ứng với bờ bên trái, vị trí lại tương ứng với bờ bên phải -Thuyền sức chứa đối tượng 2, Các tháo tác trạng thái: - Chuyển nông dân từ bờ trái qua bờ phải - Chuyển nông dân với cáo từ bờ trái qua bờ phải - Chuyển nông dân với ngỗng từ bờ trái qua bờ phải - Chuyển nông dân với hạt đậu từ bờ trái qua bờ phải - Chuyển nông dân từ bờ phải qua bờ trái - Chuyển nông dân với cáo từ bờ phải qua bờ trái - Chuyển nông dân với ngỗng từ bờ phải qua bờ trái - Chuyển nông dân với hạt đậu từ bờ phải qua bờ trái 3, Các ràng buộc: - Ngỗng không chung với cáo khơng có nơng dân ở bờ - Hạt đậu không chung với ngỗng khơng có nơng dân 4, Phương pháp cài đặt: Biểu diễn trạng thái dạng [A, B, C, D, E, F, G, H] tương ứng với: A, B, C, D ứng với nông dân, cáo, ngỗng, hạt đậu bờ bên trái E, F, G, H ứng với nông dân, cáo, ngỗng, hạt đậu bờ bên phải Trạng thái ban đầu: [1, 1, 1, 1, 0, 0, 0, 0] Trạng thái mục tiêu: [0, 0, 0, 0, 1, 1, 1, 1] 5, Chương trình cài đặt (prolog) goal([0,0,0,0,1,1,1,1]) dangerous([0,1,1,_,1,0,0,_]) dangerous([0,_,1,1,1,_,0,0]) dangerous([1,0,0,_,0,1,1,_]) dangerous([1,_,0,0,0,_,1,1]) famlr([1,F_l,G_l,B_l,0,F_R,G_R,B_R],[0,F_l,G_l,B_l,1,F_R,G_R,B_R]) famrl([0,F_l,G_l,B_l,1,F_R,G_R,B_R],[1,F_l,G_l,B_l,0,F_R,G_R,B_R]) famFoxlr([1,1,G_l,B_l,0,0,G_R,B_R],[0,0,G_l,B_l,1,1,G_R,B_R]) famFoxrl([0,0,G_l,B_l,1,1,G_R,B_R],[1,1,G_l,B_l,0,0,G_R,B_R]) famGoslr([1,F_l,1,B_l,0,F_R,0,B_R],[0,F_l,0,B_l,1,F_R,1,B_R]) famGosrl([0,F_l,0,B_l,1,F_R,1,B_R],[1,F_l,1,B_l,0,F_R,0,B_R]) famBeanlr([1,F_l,G_l,1,0,F_R,G_R,0],[0,F_l,G_l,0,1,F_R,G_R,1]) famBeanrl([0,F_l,G_l,0,1,F_R,G_R,1],[1,F_l,G_l,1,0,F_R,G_R,0]) trans(X,Y):-famlr(X,Y) trans(X,Y):-famrl(X,Y) trans(X,Y):-famFoxlr(X,Y) trans(X,Y):-famFoxrl(X,Y) trans(X,Y):-famGoslr(X,Y) trans(X,Y):-famGosrl(X,Y) trans(X,Y):-famBeanrl(X,Y) trans(X,Y):-famBeanlr(X,Y) dfs(X,P,[X|P]):-goal(X),! dfs(X,P,L):-trans(X,Y),X\=Y,\+member(Y,P),\+dangerous(Y),dfs(Y,[X|P],L) ... hai quỷ từ bờ trái qua bờ phải - Chuyển sư quỷ từ bờ trái qua bờ phải - Chuyển sư từ bờ phải qua bờ trái - Chuyển quỷ từ bờ phải qua bờ trái - Chuyển hai sư từ bờ phải qua bờ trái - Chuyển hai quỷ. .. sư quỷ từ bờ phải qua bờ trái 3, Các ràng buộc: - Số quỷ phải nhỏ số sư bờ trái phải 4, Phương pháp cài đặt: Biểu diễn trạng thái dạng [A, B, C, D] tương ứng với: - A số sư bờ bên trái, B số quỷ. ..- Trạng thái mục tiêu: Cả nhà sư ba quỷ bờ bên phải, tương ứng với [0, 0, 3, 3, 0] 2, Các thao tác trạng thái: - Chuyển sư từ bờ trái qua bờ phải - Chuyển quỷ từ bờ trái qua bờ phải - Chuyển Xem thêm: Các bài toán qua sông giải bằng prolog (con quỷ và thầy tu,...) |
