Zadania z Elementów Sztucznej Inteligencji
Witold Alda
20 stycznia 2008
Zadanie projektowe nale»y zrobi¢ w formie dziaªaj¡cego programu w dowol-
nie wybranym j¦zyku programowania. Ka»dy student powinien zrobi¢ jedno
zadanie, wybrane z poni»szych siedmiu w opisany poni»ej sposób.
Wybór numeru zadania dokonuje si¦ na podstawie ilo±ci liter w nazwisku:
ilo±¢ liter w nazwisku numer zadania
3, 8
1
7
2
6
3
5
4
4, 10
5
9
6
11, 12, 13
7
Przygotowany projekt powinien obejmowa¢ kod ¹ródªowy, kod wynikowy
i krótki opis czego dotyczy zadanie i jak je rozwi¡zano (póª strony lub strona
wystarczy, ale mo»na oczywi±cie pisa¢ wi¦cej). Projekty mo»na dostarcza¢
w formie elektronicznej na adres alda@agh.edu.pl lub papierowej. Ocjalny
termin - 24 luty, ale niedu»e opó¹nienia s¡ akceptowane byle zd¡»y¢ przed
obron¡ pracy.
Obja±nienia, a mo»e nawet gotowe rozwi¡zania, mo»na znale¹¢ bez trudu
na stronach internetowych i np w ksi¡»ce Algorytmy + struktury danych =
programy N. Wirtha.
Poni»ej tematy zada«.
1
Farmer musi przewie¹¢ przez rzek¦ wilka, koz¦ i kapust¦. W ªódce mo»e
zmie±ci¢ si¦ tylko farmer i jedno z tych trojga. Farmer nie mo»e zostawi¢ na
brzegu wilka i kozy (wilk po»arªby koz¦) ani kozy i kapusty (koza zjadªaby
kapust¦). Wilk nie gustuje w kapu±cie ani w farmerze. W jaki sposób farmer
mo»e dokona¢ przeprawy?
2 Trzy maª»e«stwa mutacja misjonarzy i kani-
bali
Trzy maª»e«stwa - pa«stwo Abaccy, Babaccy i Cabaccy - przeprawiaj¡ si¦
przez rzek¦. ódka mo»e pomie±ci¢ tylko dwie osoby. Kªopot w tym, »e »adna
z pa« nie mo»e - z wiadomych powodów - znale¹¢ si¦ w towarzystwie innych
panów podczas nieobecno±ci swojego (bardzo zazdrosnego) m¦»a. Opracowa¢
plan przeprawy.
3 Jakie to zwierz¦?
Napisz program, który zadaje pytania, na które mo»na odpowiedzie¢ tak
lub nie i na tej podstawie próbuje odgadn¡¢ zzwierz¦, które masz na my±li.
Je±li program nie zna takiego zwierz¦cia, prosi pytaj¡cego o podanie jego
nazwy oraz pytania, po zadaniu którego i uzyskaniu odpowiedzi tak, pro-
gram b¦dzie mógª odgadn¡¢ zwierz¦ (jego nazw¦ wªa±nie podali±my). Pro-
gram dopisuje now¡ nazw¦ i pytanie do swojej bazy i w ten sposób uczy si¦.
Mo»na skorzysta¢ ze strony www.animalgame.org.
4 Wie»e Hanoi
Problem polega na przeªo»eniu, z zachowaniem ksztaªtu, wie»y z kr¡»ków
o ró»nych ±rednicach (popularna dzieci¦ca zabawka)ze sªupka A na sªupek
B. Podczas przekªadania wolno si¦ posªugiwa¢ buforem, reprezentowanym w
tym przypadku przez dodatkowy sªupek, jednak przy ogólnym zaªo»eniu, »e
nie mo»na kªa±¢ kr¡»ka o wi¦kszej ±rednicy na mniejszy ani przekªada¢ kilku
kr¡»ków jednocze±nie. Parametrem zadania jest liczba kr¡»ków. Jest to
2
przykªad zadania, którego zªo»ono±¢ obliczeniowa wzrasta niezwykle szybko
w miar¦ zwi¦kszania parametru wej±ciowego, tj. liczby elementów wie»y.
Rysunek 1: Wie»e Hanoi. Od lewej: wie»a A, bufor, wie»a B
5 Znalezienie drogi w grae
Znajd¹ w grae drog¦, której dªugo±¢ (koszt) wynosi 15. Znajd¹ drog¦, której
koszt jest wi¦kszy od 15. Znajd¹ drog¦ o maksymalnym koszcie. Spróbuj
uogólni¢ problem.
Rysunek 2: Przykªadowy graf skierowany
3
Hetman jest gur¡ szachow¡, która bije gury znajduj¡ce si¦ w tej samej
kolumnie, wierszu lub diagonali co on sam. W jaki sposób rozstawi¢ osiem
hetmanów na tradycyjnej szachownicy 8x8 tak, aby wzajemnie si¦ nie atakowaªy?
Ile jest mo»liwych rozstawie«? Przez rozstawienie podstawowe b¡d¹ rozwi¡zanie
podstawowe nale»y rozumie¢ rozwi¡zanie z dokªadno±ci¡ do izomorzmu, tzn.
z uwzgl¦dnieniem wszystkich pokrewnych pozycji wynikaj¡cych z przeksz-
taªce« o charakterze symetrii i obrotów.
7 Obej±cie szachownicy przez skoczka
Problem polega na znalezieniu takiego ciagu ruchów skoczka na szachown-
icy n × n, aby przechodziª on dokªadnie raz przez ka»de pole szachownicy.
Parametrem jest tu pocz¡tkowe poªo»enie skoczka oraz rozmiar szachownicy.
4