Codice: Seleziona tutto
'''Consideriamo una versione ridotta del "gioco del 15" (si veda ad esempio,
http://en.wikipedia.org/wiki/15_puzzle), invece di 15 tessere in una tavola 4x4,
abbiamo 8 tessere in una tavola 3x3. Le tessere sono numerate da 1 a 8 e 0
indica la casella vuota. Un esempio di configurazione e' la seguente:
-------------
| 1 | 2 | 3 |
-------------
| 4 | 0 | 6 |
-------------
| 7 | 5 | 8 |
-------------
L'obiettivo del gioco e' di ritornare alla configurazione standard
-------------
| 1 | 2 | 3 |
-------------
| 4 | 5 | 6 |
-------------
| 7 | 8 | 0 |
-------------
potendo far scorrere ad ogni passo una tessera adiacente (in orizzontale o in
verticale) alla casella vuota, nella casella vuota. Ogni mossa puo' essere anche
vista come lo scambio della casella 0 con una delle tessere adiacenti.
Indichiamo le 4 possibili mosse con i seguenti caratteri:
'U': up, la casella 0 e' spostata in alto;
'D': down, la casella 0 e' spostate in basso
'L': left, la casella 0 e' spostata a sinistra
'R': right, la casella 0 e' spostata a destra
La configurazione sopra puo' essere portata nella configurazione standard con 2
mosse: 'D', 'R'.
Vogliamo scrivere un programma che data una configurazione trova una sequenza di
mosse ottimale (cioe' di lunghezza minima) che la riporta nella configurazione
standard. Rappresentiamo ogni configurazione con una tupla di 9 interi che
riporta i contenuti delle caselle per righe. Ad esempio, la configurazione sopra
e' rappresentata con (1,2,3,4,0,6,7,5,8) e la configurazioen standard con
(1,2,3,4,5,6,7,8,0). Per risolvere il problema possiamo considerare un grafo i
cui nodi sono tutte le possibili configurazioni (che sono 9!) e tra due nodi
c'e' un arco se e' possibile passare da l'uno all'altro tramite una mossa (si
osservi che le mosse sono simmetriche, cioe' invertibili). Per determinare una
sequenza ottimale per una configurazione basta quindi trovare un cammino di
lunghezza minima in tale grafo che collega la configurazione data a quella
standard.
Scrivere due funzioni. La prima, puzzle_tree(), deve ritornare un albero,
rappresentato come dizionario dei genitori, che ha come radice la configurazione
standard, i nodi sono tutte le configurazioni raggiungibili e ogni cammino
da una configurazione alla radice deve essere ottimale. In altre parole,
e' l'albero di visita di una BFS a partire dalla configurazione standard.
La seconda funzione, puzzle_sol(tree, cnf), preso in input un albero tree come
quello descritto sopra e una configurazione cnf, deve ritornare una lista che
contiene la sequenza di mosse che corrisponde al cammino in tree che va dalla
configurazione cnf alla radice. Se cnf non appartiene a tree, la funzione deve
ritornare None. La funzione non deve fare controlli su tree, si assume che
l'argomento tree sia un albero come sopra detto. Ad esempio,
puzzle_sol(tree, (1,2,3,4,0,6,7,5,8)) deve ritornare ['D', 'R']. La sequenza di
mosse ottimale potrebbe non essere unica, ad esempio,
puzzle_sol(tree, (6,0,4,2,1,8,5,7,3)) potrebbe ritornare la lista
['R','D','L','L','U','R','D','R','U','L','D','L','D','R','U','R','D','L','U',
'L','U','R','R','D','D'] oppure
['L','D','D','R','R','U','U','L','L','D','R','R','U','L','L','D','R','D','R',
'U','L','U','R','D','D']. E' sufficiente che la sequenza sia ottimale, non
importa quale tra quelle ottimali e' ritornata, stesso discorso per l'albero
ritornato da puzzle_tree().
Codice: Seleziona tutto
class Graph(object):
def __init__(self):
self._nodes = {}
def addNode(self, name, info=None):
'''Aggiunge un nodo name, se non esiste'''
if name not in self._nodes:
self._nodes[name] = (set(), info)
def addEdge(self, name1, name2):
'''Aggiunge un arco che collega i nodi name1 e name2'''
if not (name1 in self._nodes and name2 in self._nodes):
return
self._nodes[name1][0].add(name2)
self._nodes[name2][0].add(name1)
def adjacents(self, name):
'''Ritorna una lista dei nomi dei nodi adiacenti al nodo name,
se il nodo non esiste, ritorna None'''
if name in self._nodes:
return list(self._nodes[name][0])
return None
def nodes(self):
'''Ritorna una lista dei nomi dei nodi del grafo'''
return self._nodes.keys()
def nodeInfo(self, name):
'''Ritorna l'info del nodo name'''
return self._nodes[name][1] if name in self._nodes else None
Io stavo pensando di crearmi prima il grafo, una volta fatto, scrivere quelle due funzioni diventa molto facile però ho un bel problema.
Ieri ho scritto una funzione per crearmi il grafo ma ci mette troppo troppo ma troppo tempo. Le varie configurazioni dovrebbero essere 9! quindi anche i nodi dovrebbero essere 9! ma dopo 4 ore di lavoro aveva calcolato solo 150000 configurazioni...
Quindi la domanda è: sono io che sto sbagliando tutto e non ha senso creare il grafo con tutte le combinazioni oppure è la funzione che ho scritto che non va bene?
Ora non vi ho copiato anche la funzione che ho scritto io perché ce l'ho su un altro pc, se comunque volete dargli un'occhiata ve la copio appena posso.
Se poi volete darmi una mano con l'esercizio sarebbe fantastico ma al momento mi basta anche risolvere il problema che ho scritto sopra.
Grazie in anticipo
:
