Bài giảng môn học : Trí tuệ nhân tạo

BAØI GIAÛNG MOÂN HOÏC : Trí Tueä Nhaân Taïo Noäi dung : Toång quan veà trí tueä nhaân taïo Caùc phöông phaùp giaûi quyeát vaán ñeà cô baûn Heä chuyeân gia Caùc phöông phaùp bieåu dieãn tri thöùc Vaøi öùng duïng trí tueä nhaân taïo lyù giaûi vôùi logic Xöû lyù tri thöùc khoâng chaéc chaén Vieäc hoïc maùy Bieân soïan : Tieán só Nguyeãn Thieän Thaønh Thaønh phoá Hoà Chí Minh Ngaøy 7 Thaùnh 01 Naêm 2006 Chöông 1 :Toång Quan Veà Trí Tueä Nhaân Taïo Chöông naøy goàm coù : Trí tueä nhaân taïo laø gì ? Lòch söû phaùt trieån trí tueä nhaân taïo Caùc thaønh phaàn cô baûn cuûa trí tueä nhaân taïo Giôùi Thieäu Veà Ngoân Ngöõ Laäp Trình Prolog Trí tueä nhaân taïo laø gì ? Trí tueä nhaân taïo laø lónh vöïc khoa hoïc chuyeân nghieân cöùu caùc phöông phaùp cheá taïo trí tueä maùy sao cho gioáng nhö trí tueä con ngöôøi. Vaøi ñònh nghóa cuûa trí tueä nhaân taïo ñieån hình laø Heä thoáng maø bieát suy nghó nhö con ngöôøi Heä thoáng maø bieát haønh ñoäng nhö con ngöôøi Ñeå heä thoáng maø bieát suy nghó vaø haønh ñoäng gioáng nhö con ngöôøi thì heä thoáng ñoù phaûi coù tri thöùc, phaûi coù khaû naêng lyù giaûi, phaûi coù khaû naêng hoïc, phaûi coù thò giaùc vaø thính giaùc ñoàng thôøi phaûi bieát di chuyeån gioáng nhö con ngöôøi. Trí tueä con ngöôøi laø gì ? Laø khaû naêng giaûi quyeát vaán ñeà cuûa con ngöôøi. Thöôøng, khaû naêng giaûi quyeát vaán ñeà cuûa con ngöôøi thoâng qua boán thao taùc cô baûn laø Xaùc ñònh taäp hôïp ñích Xeùt quaù trình suy nghó giaûi quyeát vaán ñeà cuûa con ngöôøi, quaù trình suy nghó naøy phaûi coù ñieåm baét ñaàu vaø ñieåm keát thuùc. Ñieåm baét ñaàu ñöôïc goïi laø traïng thaùi ban ñaàu vaø ñieåm keát thuùc ñöôïc goïi laø traïng thaùi ñích cuûa baøi toùan. Giöõa hai traïng thaùi cuûa quaù trình suy nghó ñöôïc phaân raõ ra nhieàu maûnh nhoû, moãi maûnh nhoû ñöôïc goïi laø ñích töøng phaàn. Taäp caùc ñích töøng phaàn naøy ñònh höôùng caùch giaûi quyeát vaán ñeà cuûa con ngöôøi. Thu thaäp caùc söï kieän vaø luaät suy dieãn Con ngöôøi thöôøng xuyeân thu thaäp caùc söï kieän vaø coâng thöùc hoùa caùc söï kieän thaønh luaät ñeå laøm cô sôû tri thöùc giaûi quyeát vaán ñeà. Luaät laø moái quan heä giöõa vaøi söï kieän ñaõ bieát vaø moät vaøi söï kieän chöa bieát. Tri tröùc laø söï hieåu bieát veà moät lónh vöïc naøo ñoù. Cô cheá taäp trung Khi giaûi quyeát vaán ñeà, coù nhieàu ñöôøng suy nghó khaùc nhau xuaát hieän cuøng luùc. Ñeå taäp trung baùm theo ñöôøng suy nghó giaûi quyeát vaán ñeà vaø ñoàng thôøi loïai boû caùc ñöôøng suy nghó khaùc nhôø moät cô cheá coù saün trong boä oùc con ngöôøi ñoù laø cô cheá taäp trung. Boä maùy suy dieãn Quaù trình giaûi quyeát vaán ñeà laø moät quaù trình laäp luaän töø söï kieän ñaõ bieát ñeå suy dieãn ra söï kieän chöa bieát. Quaù trình naøy ñöôïc laëp laïi cho ñeán khi daãn ñeán ñích. Ñeå laøm ñöôïc ñieàu naøy, nhôø moät cô cheá coù saün trong boä oùc con ngöôøi ñoù laø boä maùy suy dieãn. Trí tueä maùy laø gì ? Trí tueä maùy laø khaû naêng giaûi quyeát vaán ñeà cuûa maùy sao cho gioáng khaû naêng giaûi quyeát vaán ñeà cuûa con ngöôøi ñoù laø Haønh ñoäng gioáng nhö con ngöôøi. Suy nghó gioáng nhö con ngöôøi. Hoïc thích nghi vôùi tình huoáng gioáng nhö con ngöôøi. Xöû lyù thoâng tin gioáng nhö con ngöôøi. Haønh ñoäng vaø suy nghó treân cô sôû logic vaø chính xaùc gioáng nhö con ngöôøi. Neàn taûng cuûa trí tueä nhaân taïo caàn ñeán caùc nguoàn tri thöùc cuûa nhieàu lónh vöïc khoa hoïc khaùc nhau nhö Khoa hoïc maùy tính vaø kyõ thuaät maùy tính ( cheá taïo phaàn meàm vaø phaàn cöùng). Trieát hoïc ( Thieát keá luaät suy dieãn lyù giaûi ) Toùan hoïc ( Kieán thöùc suy luaän logic, thieát keá thuaät toùan vaø toái öu hoùa ) Tri hoïc vaø taâm lyù hoïc (Moâ hình hoùa suy nghó con ngöôøi ôû möùc cao ) Khoa hoïc thaàn kinh ( Moâ hình hoùa hoïat ñoäng boäc oùc con ngöôøi ôû möùc thaáp ) Ngoân ngöõ hoïc ( taïo ngoân ngöõ noùi töï nhieân cho maùy ) Neàn taûng naøy ñöôïc moâ taû nhö hình Lòch söû phaùt trieån trí tueä nhaân taïo YÙ töôûng cheá taïo trí tueä maùy ñaõ coù töø laâu nhöng maõi ñeán naêm 1950, nhaø toùan hoïc ngöôøi Anh coâng boá coâng trình khoa hoïc cuûa oâng ta ñoù laø “Maùy tính vaø Thoâng minh”. Ñaây ñöôïc xem nhö laø moác lòch söû baét ñaàu phaùt trieån khoa hoïc trí tueä nhaân taïo. Nhöõng naêm ngay sau ñoù coù caùc coâng trình ñöôïc coâng boá nhö Naêm 1956, chöông trình giaûi baøi toùan toång quaùt. Naêm 1958, chöông trình chöùng minh ñònh lyù hình hoïc. Ñænh cao cuûa vieäc phaùt trieån ôû lónh vöïc naøy phaûi noùi ñeán nhöõng naêm 1960. Duø raèng coøn bò haïn cheá nhieàu veà trang thieát bò nhöng nhöõng naêm naøy ñaõ coù nhieàu coâng trình ñöôïc coâng boá nhö Naêm 1960, ngoân ngöõ Lisp. Naêm 1961, chöông trình giaûi caùc baøi toùan ñaïi soá sô caáp. Naêm 1963, chöông trình troø chôi côø vua. Naêm 1964, chöông trình tính tích phaân. Naêm 1966, chöông trình phaân tích vaø hoïc noùi. Naêm 1968, chöông trình ñieàu khieån Robot theo phöông aùn maét vaø tay. Naêm 1972, ngoân ngöõ Prolog. Töø nhöõng naêm 1969 ñeán naêm 1999, coù nhieàu chöông trình ñöôïc xaây döïng treân caùc heä cô sôû tri thöùc. Thaät vaäy, lónh vöïc trí tueä ñaõ ñi vaøo ñôøi soáng daân duïng töø nhöõng naêm 1980 ñeán naøy. Caùc thaønh phaàn cô baûn cuûa trí tueä nhaân taïo Coù hai thaønh phaàn cô baûn cuûa trí tueä nhaân taïo ñoù laø bieåu dieãn tri thöùc vaø tìm kieám tri thöùc trong mieàn bieåu dieãn. Tri thöùc cuûa baøi toùan coù theå ñöôïc phaân ra laøm ba loïai tri thöùc cô baûn ñoù laø tri thöùc moâ taû, tri thöùc thuû tuïc vaø tri thöùc ñieàu khieån. Tri thöùc moâ taû : moâ taû nhöõng gì ñöôïc bieát veà baøi toùan. Loïai tri thöùc naøy bao goàm caùc söï kieän, caùc quan heä vaø caùc tính chaát cuûa baøi toùan. Tri thöùc thuû tuïc : moâ taû toång quaùt caùch giaûi quyeát baøi toùan. Loïai tri thöùc naøy bao goàm luaät suy dieãn hôïp leä, chieán löôïc tìm kieám vaø giaûi thuaät tìm kieám. Tri thöùc ñieàu khieån : laø luaät chuû choát ñeå ñieàu khieån quaù trình tìm kieám giaûi quyeát baøi toùan. Nhö vaäy, bieåu dieãn tri thöùc laø gì ? Ñoù laø phöông phaùp theå hieän tri thöùc trong maùy sao cho ñuû vaø hieäu löïc ñeå baøi toùan ñöôïc giaûi toát nhaát. Ví duï : Xeùt baøi toùan ngöôøi noâng daân, choàn, ngoãng vaø nguõ coác. Baøi toùan ñaët ra laø ngöôøi noâng daân muoán mang theo vôùi mình moät con choàn, moät con ngoãng vaø moät soá nguõ coác qua beân kia soâng baèng moät chieác thuyeàn. Tuy nhieân, thuyeàn cuûa oâng ta quaù beù chæ coù theå mang theo moät thöù duy nhaát vôùi oâng ta treân moãi chuyeán thuyeàn sang soâng. Neáu oâng ta ñeå laïi choàn vaø ngoãng beân naøy soâng thì choàn seõ aên ngoãng vaø neáu oâng ta ñeå laïi ngoãng vaø nguõ coác thì ngoãng seõ aên heát soá nguõ coác. Haõy saép xeáp caùc chuyeán thuyeàn qua laïi soâng sao cho ngöôøi noâng daân mang moïi thöù sang beân kia soâng an toøan? Vôùi baøi toùan naøy, caùch bieåu dieãn tri thöùc toát nhaát coù theå vaïch ra caùc raøng buoäc voán saün coù trong baøi toùan ñoù laø xaây döïng moät bieåu ñoà vôùi caùc nuùt coù ñaùnh nhaõn bieåu dieãn ngöôøi noâng daân mang theo thöù maø oâng ta caàn phaûi mang theo treân moãi chuyeán thuyeàn vaø caùc caïnh lieân keát giöõa caùc nuùt bieåu dieãn baèng caùc ñöôøng muõi teân chæ caùc chuyeán thuyeàn qua laïi soâng. Caùch bieåu dieãn naøy haøm chöùa caùc thaønh phaàn nhö ngöõ töø hoïc, caáu truùc, thuû tuïc vaø ngöõ nghóa. Ngöõ töø hoïc (Lexical) : laø caùc töø vöïng hôïp leä ñöôïc söû duïng nhö ø caùc kyù hieäu trong bieåu dieãn. Caáu truùc (Structure) : laø caùc ñöôøng muõi teân lieân keát giöõa caùc nuùt chæ ñònh caùc chuyeán thuyeàn qua laïi soâng. Thuû tuïc (Procedure) : laø moâ taû caùch giaûi baøi toùan töø nuùt naøy ñeán nuùt kia nhôø thoâng caùc ñöôøng chæ ñònh muõi teân. Ngöõ nghóa (Semantic) : laø yù nghóa cuûa caùc nuùt vaø caùc caïnh lieân keát thoâng qua caùch giaûi baøi toùan. Bieåu ñoà bieåu dieãn tri thöùc cuûa baøi toùan ngöôøi noâng daân ñöôïc moâ taû nhö hình Start End Vôùi ngöôøi noâng daân vaø ba thöù oâng ta muoán mang theo ôû beân naøy soâng hoaëc beân kia soâng, ta coù 21+3 = 16 laàn saép xeáp khaùc nhau, trong ñoù coù 10 laàn saép xeáp qua laïi soâng an toøan vaø 6 laàn saép xeáp khaùc qua laïi soâng khoâng an toøan ñoù laø Choàn, ngoãng vaø nguõ coác beân naøy soâng hoaëc beân kia soâng, Ngoãng vaø nguõ coác beân naøy soâng hoaëc beân kia soâng Choàn vaø ngoãng beân naøy soâng hoaëc beân kia soâng. Khi tri thöùc cuûa baøi toùan ñaõ ñöôïc bieåu dieãn, phöông phaùp giaûi baøi toùan trong lónh vöïc trí tueä nhaân taïo ñoù laø kyõ thuaät tìm kieám trong mieàn bieåu dieãn tri thöùc cuûa baøi toùan ñoù. Ñeå giaûi baøi toùan ngöôøi noâng daân, kyõ thuaät tìm kieám laø baèng caùch baùm doø tìm theo caùc ñöôøng muõi teân baét ñaàu töø nuùt khôûi taïo lieân keát qua caùc nuùt ñeå ñi ñeán ñích trong bieåu dieãn cuûa baøi toùan. Giôùi Thieäu Veà Ngoân Ngöõ Laäp Trình Prolog Ngoân ngöõ laäp trình Prolog laø coâng cuï laäp trình suy luaän logic daønh rieâng cho lónh vöïc trí tueä nhaân taïo vôùi caùc ñaëc ñieåm nhö sau : Noù laø ngoân ngöõ cho pheùp xöû lyù song song vaø ñeä quy. Noù laø ngoân ngöõ cho pheùp lieân keát vôùi nhieàu loïai ngoân ngöõ laäp trình khaùc nhö C, Assembler vaø Pascal. Gioáng nhö caùc ngoân ngöõ laäp trình khaùc, caáu truùc chöông trình cuûa ngoân ngöõ Prolog vôùi caùc töø khoùa ñöôïc moâ taû nhö sau : domains predicates clauses goal domains : laø töø khoùa cho pheùp vuøng khai baùo bieán trong moät chöông trình Prolog vôùi caùc kieåu döõ lieäu khoâng chuaån vaø döõ lieäu chuaån. Döõ lieäu chuaån cuûa prolog laø short, word, integer, real, string, symbol. Cuù phaùp khai baùo bieán vôùi caùc kieåu döõ lieäu laø = Ví duï : Khai baùo bieán d vôùi kieåu döõ lieäu integer vaø List laø bieán danh saùch chöùa caùc soá integer vôùi caùc caâu leänh laø domains d = integer List = d* predicates : laø töø khoùa cho pheùp vuøng khai baùo caùc haøm vò töø. Ví duï : Khai baùo haøm vò töø tính father vôùi hai bieán ñoái soá cuûa noù laø X vaø Y kieåu symbol vôùi caùc caâu leänh laø domains x = symbol predicates father(X, Y) Löu yù : Caùc bieán trong caùc haøm vò töø tính laø chöõ caùi in hoa hoaëc chuoåi baét ñaàu vôùi chöõ caùi in hoa. clauses : laø töø khoùa cho pheùp vuøng khai baùo caùc meänh ñeà söï kieän vaø meänh ñeà luaät suy dieãn. Meänh ñeà söï kieän : laø caùc haøm vò töø tính ñöôïc thieát laäp ñeå khai baùo caùc söï kieän. Cuù phaùp toång quaùt cuûa haøm vò töø laø predicate_name(, . . .,). Löu yù : Caùc ñoái soá trong caùc vò töø tính sö’kieän laø caùc chuoåi haèng soá vôùi caùc chöõ caùi in thöôøng. Ví duï : Söï kieän cho raèng John laø father cuûa marry, söï kieän naøy ñöôïc khai baùo vôùi meänh ñeà söï kieän father laø father(john, marry). Meänh ñeà luaät suy dieãn : Ñeå khai baùo luaät suy dieãn If Then trong chöông trình Prolog, meänh ñeà luaät suy dieãn ñöôïc khai baùo vôùi cuù phaùp toång quaùt laø predicate_name():- predicate_name(). Trong ñoù, veá traùi cuûa meänh ñeà laø töông öùng vôùi veá keát luaän vaø veá phaûi cuûa meänh ñeà laø töông öùng vôùi veá ñieàu khieän cuûa luaät if-Then. Ví duï : Chöông trình prolog vôùi meänh ñeà söï kieän vaø luaät laø domains x = symbol predicates nondeterm father(X, Y) nondeterm grandfather(X,Z) clauses father(john, marry). father(bod, john). grandfather(X,Z) :- father(X,Y), father(Y,Z). goal grandfather(X,Z), write(X, “Grandfather of “, Z),nl. Chaïy chöông trình cho keát quaû laø Bod is grandfather of marry Toùan töû trong prolog : Toùan töû logic : Toùan töû and : , Toùan töû or : ; Toùan töû not : not Toùan töû so saùnh : Toùan töû nhoû hôn : Toùan töû lôn hoaëc baèng : >= Toùan töû khoâng baèng : Toùan töû soá hoïc : Coäng : + Tröø : - Nhaân : * Chia : / Ví duï : Giaûi phöông trình baäc 2 : Ax2 + Bx + C = 0 vôùi thuaät toùan ñöôïc moâ taû nhö hình Ax2+ Bx + C = 0 A = 0 A ≠ 0 C = 0 B ≠ 0 C ≠ 0 B = 0 C = 0 C ≠ 0 B = 0 B ≠ 0 C = 0 C ≠ 0 C = 0 C ≠ 0 Any solution Undefined Zero solution X = -C/B Zero solution X = sqrt(-C/B) X = -B/A X1 = (-B + sqrt(B2 -4AC))/2A X2 = (-B - sqrt(B2 -4AC))/2A Luaät If- Then giaûi phöông trình baäc 2 vôùi thuaät toùan hình caây ñöôïc thieát laäp laø If A = 0 and B = 0 and C = 0 Then Display Any solution. If A = 0 and B = 0 and C ≠ 0 Then Display Undefined solution. If A = 0 and B ≠ 0 and C = 0 Then Display Zero solution If A = 0 and B ≠ 0 and C ≠ 0 Then Display x = -C/B. If A ≠ 0 and B = 0 and C = 0 Then Display Zero solution. If A ≠ 0 and B = 0 and C ≠ 0 Then Display x = ±sqrt(-C/A). If A ≠ 0 and B ≠ 0 and C = 0 Then Display x = 0 and x = -B/A. If A ≠ 0 and B ≠ 0 and C ≠ 0 Then Display x = (-B ±sqrt(B2 – 4AC))/2A. Chöông trình Prolog ñöôïc thieát laäp treân cô sôû luaät If-Then giaûi baøi toùan phöông trình baäc 2 laø domains r = real predicates solve(R, R, R) clauses solve(A, B, C) :- A = 0, B = 0, C = 0, write(“Any solution “),nl,!. solve(A, B, C) :- A = 0, B = 0, C 0, write(“Undefined solution “),nl,!. solve(A, B, C) :- A = 0, B 0, C = 0, write(“Zero solution “),nl,!. solve(A, B, C) :- A = 0, B 0, X = -C/B, write(“X = “,X),nl,!. solve(A, B, C):- A 0, B = 0, C = 0, write(“Zero solution “),nl,!. solve(A, B, C) :- A 0, B = 0, C 0, D = -C/A, D > 0, X1 = sqrt(D), X2 = -sqrt(D), write(“X1 = “, X1,” X2 = “,X2),nl,!. solve(A, B, C) :- A 0, B 0, C = 0, X1 = 0, X2 = -B/A, write(“X1 = “,X1,” X2 = “,X2),nl,!. solve(A, B, C) :- A 0, B 0, C 0, D = B*B – 4*A*C, D > 0, X1 = (-B + sqrt(D))/(2*A), X2 = (-B – sqrt(D))/(2*A), write(“X1 = “, X1,” X2 = “,X2),nl,!. goal write(“Enter coeffient A : ), readreal(A), write(“Enter coeffient A : ), readreal(A), write(“Enter coeffient A : ), readreal(A), solve(A, B, C). Xöû lyù danh saùch : Xaùc ñònh thaønh vieân cuûa danh saùch vôùi caùc meänh ñeà laø member(X, [X | _ ]) :- !. member(X, [_ | L ]) :- member(X, L). Neáu X laø thaønh vieân cuûa danh saùch L thì meänh ñeà traû veà giaù trò logic true; maët khaùc traû veà giaù trò logic false. Noái hai danh saùch vôùi caùc meänh ñeà laø append([ ], L, L). append([X | L1], L2, [X | L3]) :- append(L1, L2, L3). Noái hai danh saùch L1 vaø L2 cho keát quaû L3. Hieån thò noäi dung cuûa danh saùch vôùi caùc meänh ñeà laø writelist([ ]). Writelist([H | T]) :- write(H), nl, writelist(T). Hieån thò ñaûo noäi dung cuûa danh saùch vôùi caùc meänh ñeà laø reverse_writelist([ ]). reverse_writelist([H | T]) :- reverse_writelist(T), write(H),nl. Loïai boû phaàn töû ñaàu tieân cuûa danh saùch T vôùi meänh ñeà laø dequeue(E, [E | T], T). Coäng moät phaàn töû vaøo cuoái danh saùch vôùi caùc meänh ñeà laø add_to_queue(E, [ ],[E]). add_to_queue(E, [H | T], [H | Tnew]) :- add_to_queue(E,T,Tnew). Coäng theâm moät phaàn töû vaøo ñaàu danh saùch stack vôùi meänh ñeà laø stack(Top, Stack,[Top | Stack]). Coäng theâm moät danh saùch vaøo cuoái danh saùch stack vôùi meänh ñeà laø add_list_to_stack(L, Stack, Result) :- append(L, Stack, Result). Xaùc ñònh thaønh vieân laø cXa1cdanh saùch stack vôùi meänh ñeà laø member_stack(E, Stack) :- member(E, Stack). Hieån thò ñaûo noäi dung cuûa stack vôùi caùc meänh ñeà laø reverse_print-stack(S) :- empty_stack(S). reverse_print_stack(S) :- stack(E, Res, S), reverse_print_stack(Res), wrie(E),nl. Xaùc ñònh thaønh vieân thuoäc laø cuûa taäp hôïp S vôùi meänh ñeà laø member_set(X, S) :- member(X,S). Coäng thaønh vieân khoâng thuoäc veà danh saùch vaøo ñaàu danh saùch vôùi caùc meänh ñeà laø add_if_not_in_set(X, L, L) :- member(X, L), !. add_if_not_in_set(X, L, [X | L]). Xaùc ñònh taäp hôïp laø taäp con cuûa moät taäp hôïp khaùc vôùi caùc meänh ñeà laø subset([ ], _ ). Subset({H | T], L) :- member_set(H, L), subset(T,L). Lieät keâ taát caû caùc giaù trò cuûa cuøng thuoäc tính trong lôùp söû duïng leänh findall vôùi cuù phaùp laø findall(Property_name, Predicate_name, List). Ví duï : predicates person(Name, Address, Age) clauses person(“Alan”,”22 Bstreet”, 42). person(“Peter”,”21 C street”,36). goal findall(Age, person(_,_,Age), L). Ví duï : Chöông trình Prolog giaûi baøi toùan ngöôøi noâng daân choàn ngoãng vôùi maõ nguoàn laø domains LOC = east; west STATE = state(LOC farmer,LOC wolf,LOC goat,LOC cabbage) PATH = STATE* predicates go(STATE,STATE) % Start of the algorithm path(STATE,STATE,PATH,PATH) % Finds a path from one state to another nondeterm move(STATE,STATE) % Transfer a system from one side to another opposite(LOC,LOC) % Gives a location on the opposite side nondeterm unsafe(STATE) % Gives the unsafe states nondeterm member(STATE,PATH) % Checks if the state is already visited write_path(PATH) write_move(STATE,STATE) clauses go(StartState,GoalState):- path(StartState,GoalState,[StartState],Path), write("A solution is:\n"), write_path(Path). path(StartState,GoalState,VisitedPath,Path):- move(StartState,NextState), % Find a move not(unsafe(NextState)), % Check that it is not unsage not(member(NextState,VisitedPath)), % Check that we have not had this situation before path(NextState,GoalState,[NextState|VisitedPath],Path), !. path(GoalState,GoalState,Path,Path). % The final state is reached move(state(X,X,G,C),state(Y,Y,G,C)):- opposite(X,Y). % Move FARMER + WOLF move(state(X,W,X,C),state(Y,W,Y,C)):- opposite(X,Y). % Move FARMER + GOAT move(state(X,W,G,X),state(Y,W,G,Y)):- opposite(X,Y). % Move FARMER + CABBAGE move(state(X,W,G,C),state(Y,W,G,C)):- opposite(X,Y). % Move ONLY FARMER opposite(west,east). unsafe(state(F,X,X,_)):- % The wolf eats the goat opposite(F,X), !. unsafe(state(F,_,X,X)):- % The goat eats the cabbage opposite(F,X), !. member(X,[X|_]):-!. member(X,[_|L]):- member(X,L). opposite(east,west). write_path([H1,H2|T]):- write_move(H1,H2), write_path([H2|T]). write_path([]). write_move(state(X,W,G,C),state(Y,W,G,C)):-!, write("The farmer crosses the river from ",X," to ",Y),nl. write_move(state(X,X,G,C),state(Y,Y,G,C)):-!, write("The farmer takes the Wolf from ",X," of the river to ",Y),nl. write_move(state(X,W,X,C),state(Y,W,Y,C)):-!, write("The farmer takes the Goat from ",X," of the river to ",Y),nl. write_move(state(X,W,G,X),state(Y,W,G,Y)):-!, write("The farmer takes the cabbage from ",X," of the river to ",Y),nl. goal go(state(east,east,east,east),state(west,west,west,west)), write("solved"). Chaïy chöông trình cho keát quaû laø A solution is: The farmer takes the Goat from west of the river to east The farmer crosses the river from east to west The farmer takes the cabbage from west of the river to east The farmer takes the Goat from east of the river to west The farmer takes the Wolf from west of the river to east The farmer crosses the river from east to west The farmer takes the Goat from west of the river to east no