Algoritmo gioco parcheggio
Salve a tutti.
Per un progetto universitario dovrei creare un programma (in C ma questo non è importante) in grado di risolvere automaticamente il "gioco del parcheggio" (qua un esempio http://www.flashgames.it/rush.hour.html per capire a cosa mi sto riferendo).
Sostanzialmente l'idea che ho in mente è questa:
1. Caricare la "configurazione" iniziale delle vetture da file (secondo vincoli della consegna), inizializzazione delle varie strutture dati quali array di liste ecc.;
2. Calcolare tutte le possibili combinazioni escludendo quelle non possibili (ovvero quelle con sovrapposizioni tra alcune vetture);
3. Creare il grafo associato alle combinazioni; (vincolato da consegna)
4. Applicare l'algoritmo di Dijkstra e trovare la soluzione ottima (vincolato da consegna).
Il mio problema attualmente sta nel calcole di tutte le combinazioni e conseguente esclusione di combinazioni non possibili.
A livello matematico penso si possa trattare, appunto, di combinazioni semplici senza ripetizioni.
Tuttavia non riesco a venirne a capo e trovare un algoritmo in grado di aiutarmi nella creazione delle combinazioni.
La mia richiesta sarebbe quindi una qualche idea oppure qualche istruzione per iniziare a scrivere uno pseudocodice utile.
Grazie a tutti e scusate se non sono stato chiaro.
Per un progetto universitario dovrei creare un programma (in C ma questo non è importante) in grado di risolvere automaticamente il "gioco del parcheggio" (qua un esempio http://www.flashgames.it/rush.hour.html per capire a cosa mi sto riferendo).
Sostanzialmente l'idea che ho in mente è questa:
1. Caricare la "configurazione" iniziale delle vetture da file (secondo vincoli della consegna), inizializzazione delle varie strutture dati quali array di liste ecc.;
2. Calcolare tutte le possibili combinazioni escludendo quelle non possibili (ovvero quelle con sovrapposizioni tra alcune vetture);
3. Creare il grafo associato alle combinazioni; (vincolato da consegna)
4. Applicare l'algoritmo di Dijkstra e trovare la soluzione ottima (vincolato da consegna).
Il mio problema attualmente sta nel calcole di tutte le combinazioni e conseguente esclusione di combinazioni non possibili.
A livello matematico penso si possa trattare, appunto, di combinazioni semplici senza ripetizioni.
Tuttavia non riesco a venirne a capo e trovare un algoritmo in grado di aiutarmi nella creazione delle combinazioni.
La mia richiesta sarebbe quindi una qualche idea oppure qualche istruzione per iniziare a scrivere uno pseudocodice utile.
Grazie a tutti e scusate se non sono stato chiaro.
Risposte
Stiamo parlando di una quantità di combinazioni enormi (pensa a quante mosse possibili hai ad ogni turno) e non credo sia una buona idea quella di generare tutte le combinazioni possibili in questo modo. Una scelta migliore è quella di generare le combinazioni a richiesta e usare A* per navigare nel grafo. Avrai bisogno di calcolarti una qualche euristica per navigare nel grafo verso la soluzione più velocemente, di una lista di priorità per contenere le combinazioni visitabili e una qualche struttura dati per contenere le combinazioni già visitate. Per ogni combinazione dovrai anche determinare le combinazioni accessibili a partire da questa.
Ci sono parecchi articoli o libri sull'argomento, ma se hai bisogno di maggiori dettagli chiedi pure. Per quanto riguarda l'euristica da usare, prova a togliere alcune limitazioni necessarie per arrivare al risultato. Una possibile euristica può ad esempio essere calcolare il numero di vetture che si deve spostare per lasciar passare la tua auto (euristica che si ottiene togliendo la limitazione che le macchine non possono coesistere sulle stesse caselle). Più la funzione usata si avvicina al reale numero di mosse necessarie a risolvere il problema, più A* sarà efficace.
Ci sono parecchi articoli o libri sull'argomento, ma se hai bisogno di maggiori dettagli chiedi pure. Per quanto riguarda l'euristica da usare, prova a togliere alcune limitazioni necessarie per arrivare al risultato. Una possibile euristica può ad esempio essere calcolare il numero di vetture che si deve spostare per lasciar passare la tua auto (euristica che si ottiene togliendo la limitazione che le macchine non possono coesistere sulle stesse caselle). Più la funzione usata si avvicina al reale numero di mosse necessarie a risolvere il problema, più A* sarà efficace.
"apatriarca":
Stiamo parlando di una quantità di combinazioni enormi (pensa a quante mosse possibili hai ad ogni turno) e non credo sia una buona idea quella di generare tutte le combinazioni possibili in questo modo. Una scelta migliore è quella di generare le combinazioni a richiesta e usare A* per navigare nel grafo. Avrai bisogno di calcolarti una qualche euristica per navigare nel grafo verso la soluzione più velocemente, di una lista di priorità per contenere le combinazioni visitabili e una qualche struttura dati per contenere le combinazioni già visitate. Per ogni combinazione dovrai anche determinare le combinazioni accessibili a partire da questa.
Ci sono parecchi articoli o libri sull'argomento, ma se hai bisogno di maggiori dettagli chiedi pure. Per quanto riguarda l'euristica da usare, prova a togliere alcune limitazioni necessarie per arrivare al risultato. Una possibile euristica può ad esempio essere calcolare il numero di vetture che si deve spostare per lasciar passare la tua auto (euristica che si ottiene togliendo la limitazione che le macchine non possono coesistere sulle stesse caselle). Più la funzione usata si avvicina al reale numero di mosse necessarie a risolvere il problema, più A* sarà efficace.
In che senso "generare le combinazioni a richiesta?"
Da quel che ho capito dalla consegna (sono all'estero quindi la consegna è in lingua straniera), dalla presentazione di questo progetto e da qualche pdf in rete, la soluzione deve essere ottima tra tutte le combinazioni possibili. O almeno è l'idea che mi è venuta considerando le specifiche della consegna e gli argomenti trattati durante il corso.
Mi sto fortemente basando su questo pdf: http://www.cs.sjsu.edu/~stamp/cv/papers/rh.pdf
Per quanto riguarda A* ed euristiche non ho mai avuto modo di approfondire a riguardo quindi mi trovo assolutamente spiazzato
A* è un algoritmo per calcolare il percorso minimo in un grafo con archi pesati. Utilizza un'euristica per ridurre il numero di nodi che è necessario visitare per arrivare al percorso minimo. Se la funzione euristica è sempre inferiore della reale lunghezza del percorso minimo allora il percorso trovato dall'algoritmo è minimo. In caso contrario il percorso potrebbe non essere minimo, ma potrebbe essere comunque utile. Ti consiglio di cercarlo in rete.
Per quanto riguarda la ricerca di combinazione a richiesta, intendo dire che invece di generare tutte le combinazioni e il grafo, generi una specie di albero delle mosse e verifichi di volta in volta se la combinazione è stata già visitata. Mentre aggiungi nuovi nodi a quella che chiamo frontiera solo quando visiti un nodo che permette di arrivare a quella configurazione.
Per quanto riguarda la ricerca di combinazione a richiesta, intendo dire che invece di generare tutte le combinazioni e il grafo, generi una specie di albero delle mosse e verifichi di volta in volta se la combinazione è stata già visitata. Mentre aggiungi nuovi nodi a quella che chiamo frontiera solo quando visiti un nodo che permette di arrivare a quella configurazione.
"apatriarca":
A* è un algoritmo per calcolare il percorso minimo in un grafo con archi pesati. Utilizza un'euristica per ridurre il numero di nodi che è necessario visitare per arrivare al percorso minimo. Se la funzione euristica è sempre inferiore della reale lunghezza del percorso minimo allora il percorso trovato dall'algoritmo è minimo. In caso contrario il percorso potrebbe non essere minimo, ma potrebbe essere comunque utile. Ti consiglio di cercarlo in rete.
Per quanto riguarda la ricerca di combinazione a richiesta, intendo dire che invece di generare tutte le combinazioni e il grafo, generi una specie di albero delle mosse e verifichi di volta in volta se la combinazione è stata già visitata. Mentre aggiungi nuovi nodi a quella che chiamo frontiera solo quando visiti un nodo che permette di arrivare a quella configurazione.
Devo riuscire a comprendere bene la tua soluzione.
Attualmente mi riesce di difficile comprensione ma mi impegnerò per comprenderlo!
Per ora ti ringrazio veramente
A* (si pronuncia A star), è un algoritmo per calcolare percorsi minimi in un grafo esattamente come l'algoritmo di Dijkstra presentato in quell'articolo. La differenza principale è che Dijkstra espande l'area visitata del grafo in modo uniforme verso tutti i nomi, mentre A* utilizza una funzione per stabilire "in quale direzione muoversi". Lo fa stimando la "distanza" tra ogni singolo nodo e quello di destinazione. Se questa stima fosse esatta, allora il percorso corretto si troverebbe semplicemente visitando solo i nodi via via più vicino a destinazione. Più la stima è sbagliata e si avvicina allo zero, più il comportamento di A* si avvicina a quello di Dijkstra o altri algoritmi simili che non hanno alcuna conoscenza ulteriore del problema. Se consideri per esempio il tuo problema puoi osservare che una mossa che riduce il numero di macchine che ostruiscono il passaggio è in generale preferibile rispetto ad una altra che aumenta o mantiene costante questo numero. Non è detto che questa mossa sia effettivamente la migliore, ma è più probabile e questo è sufficiente per velocizzare la ricerca del percorso minimo. Volendo fare un altro esempio, considera un navigatore che debba trovare il percorso minimo tra due città. Dijkstra visiterebbe tutte le strade come in un cerchio, mentre A* cercherebbe di andare nella direzione dell'altra città minimizzando, oltre che alla distanza percorsa anche la distanza aerea verso la destinazione. Per problemi relativamente piccoli o nei casi in cui si desideri trovare la distanza minima tra un singolo nodo e tutti gli altri, Dijkstra è di più facile implementazione e si rivela comunque corretto e abbastanza efficiente. Ma A* è in pratica molto migliore quando si ha a che fare con grafi di enorme dimensione sui quali sia possibile definire un'euristica efficace. Ovviamente, nulla ti vieta di usare il metodo presentato in quell'articolo, ma credo che A* sia un interessante algoritmo da imparare. Un buon punto di partenza, anche se principalmente rivolto ad un problema differente, è questo.
Penso che a me manchi piuttosto lo step precedente alla visita.
Riassumendo: io attualmente mi trovo nella situazione in cui ho soltanto la "configurazione" iniziale.
Ovvero da consegna so soltanto che: il veicolo X si trova sulla tale riga/colonna, so che si può muovere orizzontalmente o verticalmente, so il numero di celle occupate ed in un'altra struttura dati (array di liste) conosco la posizione delle varie vetture (per le vetture "orizzontali" questa posizione è identificata dalla cella più a destra, per le "verticali" dalla cella più in basso).
Quello che manca a me è l'idea per iniziare a produrre altre "configurazioni" utili su cui creare un grafo e successivamente trovare il percorso minimo. Il grafo sarebbe composto dai nodi rappresentati una determinata configurazioni e gli archi sono il costo (in termini di spostamenti di un singolo mezzo) da una configurazione all'altra.
In sintesi prima di poterlo visitare devo riuscire a crearlo questo grafo, ed è ciò che mi manca in sostanza :\
Riassumendo: io attualmente mi trovo nella situazione in cui ho soltanto la "configurazione" iniziale.
Ovvero da consegna so soltanto che: il veicolo X si trova sulla tale riga/colonna, so che si può muovere orizzontalmente o verticalmente, so il numero di celle occupate ed in un'altra struttura dati (array di liste) conosco la posizione delle varie vetture (per le vetture "orizzontali" questa posizione è identificata dalla cella più a destra, per le "verticali" dalla cella più in basso).
Quello che manca a me è l'idea per iniziare a produrre altre "configurazioni" utili su cui creare un grafo e successivamente trovare il percorso minimo. Il grafo sarebbe composto dai nodi rappresentati una determinata configurazioni e gli archi sono il costo (in termini di spostamenti di un singolo mezzo) da una configurazione all'altra.
In sintesi prima di poterlo visitare devo riuscire a crearlo questo grafo, ed è ciò che mi manca in sostanza :\
L'unica cosa che puoi fare a partire da una qualsiasi configurazione è spostare una macchina qualsiasi (sia essa quella della soluzione o una dei vincoli lungo la direzione in cui si può spostare di un certo numero di passi. Per ogni macchina determini quindi di quante posizioni si può spostare (in direzione positiva e negativa) e aggiungi al grafo tutte queste nuove configurazioni con un nodo che va dalla configurazione attuale a quella nuova. La prima mossa da considerare è forse quella che risolve il puzzle. Se la mossa che risolve il puzzle è possibile allora tanto vale considerarla subito.
"zephyrio":
Penso che a me manchi piuttosto lo step precedente alla visita.
Riassumendo: io attualmente mi trovo nella situazione in cui ho soltanto la "configurazione" iniziale.
In sintesi prima di poterlo visitare devo riuscire a crearlo questo grafo, ed è ciò che mi manca in sostanza :\
Ho dato un occhiata al documento perchè è interessante come problema.
D'accordo, però prima devi crearti l'insieme delle possibili configurazioni, a prescindere da quale sia quella finale e iniziale.
Come dice anche il documento, in questo insieme ci sono molte meno combinazioni di tutte quelle possibili perchè i pezzi non si devono sovrapporre.
Direi che dovresti fare questi step per avere l'insieme delle configurazioni:
Fai un array di dimensione pari al numero di pezzi. Ogni elemento contiene la riga/colonna fissa e la lunghezza del pezzo.
Esempio: C3, 2 è un pezzo lungo 2 messo sulla colonna 3.
A quel punto fai una funzione ricorsiva per trovare tutte le combinazioni:
main
crei una scacchiera vuota
punti al primo elemento dell'array.
chiama funzione XYZ
.....
eccetera
....
end
Funz XYZ
segni le caselle della scacchiera occupate dal pezzo
begin ciclo for per tutte le possibili posizioni (index = lunghezza pezzo TO dim. scacchiera )
segna sulla scacchiera la nuova posizione del veicolo (alcuni celle erano già segnate) aggiungendo +1 alla cella
sono arrivato in fondo all'array di pezzi ?
no, allora chiama la funzione XYZ (ricorsivamente)
si, allora controlla se la configurazione sulla scacchiera è plausibile (se esiste una cella >1 allora non plausibile)
se la configurazione è plausibile, allora salva la configurazione in una array di configurazioni valide.
inizializza a zero la scacchiera
end ciclo for
return XYZ
Poi nell'insieme delle configurazioni valide (i nodi del grafo) devi capire quali sono raggiungibili da quale altra configurazione, cioè capire se dal nodo 3 puoi passare al nodo 10.
Ovviamente qui solo 1 veicolo deve muoversi di una casella. Così hai creato i collegamenti del grafo.
Chiarisco un attimo alcuni dei punti che ho considerato solo brevemente. In questo gioco il numero delle configurazioni è relativamente trattabile. E' quindi possibile generarle tutte. Ci sono però problemi in cui non è fattibile generare tutte le configurazioni perché le combinazioni sono tantissime o addirittura infinite. In questo genere di problemi si genera un albero delle mosse possibili a partire da uno specifico nodo. Se il numero dei nodi che è necessario visitare prima di arrivare alla soluzione è molto più basso del numero delle configurazioni, allora questo metodo è più efficiente. Se invece fosse necessario visitare quasi tutto il grafo o fosse necessario ripetere tante volte delle ricerche nel medesimo grafo (è il caso del navigatore), allora conviene muoversi direttamente nel grafo.
Noto comunque che non è sufficiente generare tutte le configurazioni possibili, ma è anche necessario definire gli archi tra queste configurazioni nel grafo. E' cioè necessario sapere quali sono le configurazioni possibili a partire da una qualche altra configurazione del grafo.
Noto comunque che non è sufficiente generare tutte le configurazioni possibili, ma è anche necessario definire gli archi tra queste configurazioni nel grafo. E' cioè necessario sapere quali sono le configurazioni possibili a partire da una qualche altra configurazione del grafo.
Non volevo criticare nessuno.... ho solo messo giù le idee, siccome il problemino mi ha appassionato e ci ho dedicato un po' di tempo.
"Quinzio":
[quote="zephyrio"]Penso che a me manchi piuttosto lo step precedente alla visita.
Innanzitutto grazie mille per l'interesse di entrambi e per il tempo che Quinzio hai speso in questo problema!
Riassumendo: io attualmente mi trovo nella situazione in cui ho soltanto la "configurazione" iniziale.
In sintesi prima di poterlo visitare devo riuscire a crearlo questo grafo, ed è ciò che mi manca in sostanza :\
Ho dato un occhiata al documento perchè è interessante come problema.
D'accordo, però prima devi crearti l'insieme delle possibili configurazioni, a prescindere da quale sia quella finale e iniziale.
Come dice anche il documento, in questo insieme ci sono molte meno combinazioni di tutte quelle possibili perchè i pezzi non si devono sovrapporre.
Direi che dovresti fare questi step per avere l'insieme delle configurazioni:
Fai un array di dimensione pari al numero di pezzi. Ogni elemento contiene la riga/colonna fissa e la lunghezza del pezzo.
Esempio: C3, 2 è un pezzo lungo 2 messo sulla colonna 3.
A quel punto fai una funzione ricorsiva per trovare tutte le combinazioni:
main
crei una scacchiera vuota
punti al primo elemento dell'array.
chiama funzione XYZ
.....
eccetera
....
end
Funz XYZ
segni le caselle della scacchiera occupate dal pezzo
begin ciclo for per tutte le possibili posizioni (index = lunghezza pezzo TO dim. scacchiera )
segna sulla scacchiera la nuova posizione del veicolo (alcuni celle erano già segnate) aggiungendo +1 alla cella
sono arrivato in fondo all'array di pezzi ?
no, allora chiama la funzione XYZ (ricorsivamente)
si, allora controlla se la configurazione sulla scacchiera è plausibile (se esiste una cella >1 allora non plausibile)
se la configurazione è plausibile, allora salva la configurazione in una array di configurazioni valide.
inizializza a zero la scacchiera
end ciclo for
return XYZ
Poi nell'insieme delle configurazioni valide (i nodi del grafo) devi capire quali sono raggiungibili da quale altra configurazione, cioè capire se dal nodo 3 puoi passare al nodo 10.
Ovviamente qui solo 1 veicolo deve muoversi di una casella. Così hai creato i collegamenti del grafo.[/quote]
Scusa se tardo a rispondere ma questo fine settimana mi ha impegnato parecchio.
Il tuo metodo mi intriga, dovrò spendere un pò di tempo a cercare di associare le assurde strutture dati a cui sono vincolato da consegna.
Però provando con un semplice esempio ammetto di avere qualche difficoltà nel capire un paio di passaggi della funzione ricorsiva.
Esempio pratico:
La situazione iniziale è la seguente (qui rappresentati i 2 veicoli nella configurazione iniziale):
0 0 0
1 1 2
0 0 2
0 0 2
Alla prima chiamata di XYZ, se ho ben capito, avrò la seguente funzione:
XYZ(...)
1."segna caselle occupate
2.for (i=2; i<=3; i++)
{
3. "sposto veicolo";
4. "segno la nuova posizione";
5. if ("Ci sono veicoli da spostare? (non sono alla fine dell'array dei veicoli?)")
6. NO-> XYZ;
7. SI-> "controlla se la conf. è plausibile (se si, salvala);
8. "azzera la matrice";
}
9. return;
Riga 1 (segno caselle) avremo:
0 0 0
1 1 0
0 0 0
0 0 0
Inizio il For
Ora il problema...alla prima iterazione abbiamo uno spostamento del veicolo? Se si, questo dovrebbe generare una mancanza di combinazioni?
Inoltre l'azzeramento della matrice in riga 8, per poi riprendere il for, non va ad inficiare sulla creazione delle altre configurazioni?
Altra domanda è se con questo metodo non mi si generino delle configurazioni doppie
E' per prima cosa necessario prendere in considerazione anche la prima macchina (quella che deve uscire dal parcheggio). In alcune soluzioni è infatti necessario muovere anche quella. Per il resto si tratta di un normale algoritmo di backtracking. Scegli la posizione di una macchina e poi elenchi tutte le configurazioni possibili con le posizioni scelte per tutte le macchine precedenti. Se non ce ne sono torni semplicemente "indietro" e fai una nuova scelta della posizione esattamente come faresti nel caso in cui siano state trovate delle configurazioni. Siccome c'è un ordine delle macchine e la scelta delle posizioni avviene secondo questo ordine, le configurazioni sono anche uniche. Una volta trovate le configurazioni è però necessario trovare anche gli archi tra una configurazione e l'altra in modo da poter far girare un qualche algoritmo per trovare il percorso di costo minimo. Un algoritmo naif consiste nel aggiungere un arco tra due configurazioni se differiscono per la posizione di una sola macchina. Si tratta però di un algoritmo \(O(n^2\,k)\) dove \(k\) è il numero di macchine. Non mi viene però in mente nessun metodo per velocizzare il codice senza fare uso di strutture dati più o meno complicate.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo