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 [e-mail] 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

1 Farmer i koza

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

6 Problem 8 hetmanów

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