UL/FRI/VSP-RI/OAPS2/Seminarske/2006-05-19
Iz E-študij, proste zakladnice študentskega znanja
2. seminarska naloga: primerjava strategij preiskovanja
V igri drsečih ploščic je potrebno začetno neurejeno pozicijo s premikanjem ploščic na sosednjo prazno polje preurediti tako, da dobimo končno urejeno razporeditev, kot to prikazuje slika. Sprogramirajte prostor stanj in prehode med pozicijami, ki predstavljajo to igro in na njej preskusite naslednje preiskovalne algoritme:
- preiskovanje v širino,
- omejeno preiskovanje v globino,
- iterativno poglabljanje in
- iskanje najprej najboljši, za katerega uporabite ustrezno oceno kvalitete stanja.
možni začetni stanji
4 3 2 7 15 5 14
1 5 8 9 10 2
6 7 1 3 13 8
11 4 12 6
končni stanji
1 2 3 1 2 3 4
4 5 6 5 6 7 8
7 8 9 10 11 12
13 14 15
Algoritme primerjajte tako, da z datoteke preberete po 20 začetnih pozicij za igre velikosti 3x3 in 4x4, ki jih dobite na http://oaps2.fri.uni-lj.si, ter nato štejte število zgeneriranih in preiskanih pozicij ter izmerite čas, ki ga preiskovalni algoritem porabi do končne pozicije.
Pred zagovorom pripravite pisno poročilo, kjer opišete vašo rešitev in uporabljeno oceno kvalitete. Poročilo mora obvezno vsebovati tabelo, ki za vsak problem in za vsak algoritem vsebuje število preiskanih in generiranih stanj in porabljen čas. Izračunajte tudi povprečja po problemih in algoritmih. Problemi velikosti 3x3 so spravljeni v datotekah s končnicami .3p, velikosti 4x4 pa v datotekah s končnicami .4p. Elementi so zapisani po vrsti od leve proti desni in od zgoraj navzdol, 0 predstavlja prazno polje. Začetno stanje 3x3 s slike je tako zapisano kot 4 3 2 1 5 8 6 0 7, končno pa kot 1 2 3 4 5 6 7 8 0.
Kriteriji za ocenjevanje so pravilnost algoritmov in predstavitev, hitrost preiskovanja, elegantnost in učinkovitost kode ter predstavitev rezultatov v poročilu in na ustnem zagovoru.
Zadnji rok za zagovor naloge je v tednu od 15. do 19. maja 2006, glede na skupino kamor spadate.
Ploščice
3 x 3
cat *.3p | awk '{print $0"\n"}'
3 2 1 7 4 6 8 0 5
8 7 1 3 5 4 6 2 0
5 1 6 0 2 8 3 4 7
1 5 6 0 7 2 3 8 4
3 8 0 5 2 4 7 6 1
3 4 8 7 1 2 6 5 0
2 3 7 6 4 0 8 1 5
0 3 8 2 1 7 6 4 5
2 3 1 8 4 6 0 7 5
2 1 3 5 4 8 6 0 7
5 1 3 6 8 0 7 2 4
0 5 1 6 7 8 2 4 3
4 2 3 6 5 8 0 1 7
5 8 0 1 7 3 4 2 6
4 8 0 5 1 6 7 2 3
1 0 8 2 6 4 5 7 3
3 4 2 7 5 1 0 8 6
7 1 3 4 6 8 0 2 5
6 3 4 7 8 5 0 2 1
5 6 8 1 2 4 3 0 7
4 x 4
cat *.4p | awk '{print $0"\n"}'
6 1 0 5 4 11 9 10 3 13 12 15 14 7 2 8
3 8 14 15 4 10 12 7 6 1 9 5 11 0 13 2
4 15 14 8 13 2 3 9 0 10 5 11 6 1 12 7
11 5 10 0 3 6 8 13 2 14 4 12 1 7 15 9
2 5 1 12 0 11 3 4 13 15 9 14 8 10 6 7
10 8 1 0 2 14 11 3 5 13 4 9 15 6 7 12
1 0 11 2 8 5 7 9 10 13 6 3 14 15 12 4
5 9 0 3 2 4 11 12 13 10 15 6 7 1 14 8
14 6 8 4 9 5 13 1 12 3 10 0 11 2 7 15
12 13 1 6 2 11 14 3 10 4 5 8 15 9 7 0
6 2 9 12 14 8 15 3 7 11 13 4 0 10 1 5
4 7 3 14 6 9 2 1 13 15 12 8 0 5 10 11
9 12 2 6 0 3 1 10 5 15 13 4 14 8 7 11
6 4 8 7 3 13 11 1 9 5 15 14 12 0 2 10
7 2 15 9 5 1 8 10 6 14 3 12 4 11 13 0
8 1 13 5 11 6 4 3 15 2 12 0 14 9 7 10
0 11 5 10 4 13 14 6 3 12 9 7 2 15 1 8
4 5 6 10 14 12 1 3 8 9 15 13 11 0 2 7
11 14 2 9 6 4 5 1 13 12 0 7 3 15 8 10
2 9 3 7 10 5 6 0 1 11 13 8 14 12 4 15
