PDA

Visualizza la versione completa : [C] Algoritmo per gioco parcheggio


zephyrio
05-11-2011, 18:44
Salve a tutti.
Scrivo in questa sessione sperando di non sbagliare, in realtÓ Ŕ un problema di carattere algoritmico piuttosto che di programmazione.

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.

xxstykkyxx
06-11-2011, 11:45
Applicare l'algoritmo di Dijkstra e trovare la soluzione ottima (vincolato da consegna).


Questi tipi di algoritmi li studi all'universitÓ o l'hai trovato in internet? :D
Se la risposta Ŕ la seconda, mi daresti la fonte di questa bontÓ? :ecco:

zephyrio
06-11-2011, 14:16
UniversitÓ ma non capisco il perchŔ della domanda :/

xxstykkyxx
06-11-2011, 14:27
Originariamente inviato da zephyrio
UniversitÓ ma non capisco il perchŔ della domanda :/
sono argomenti che mi interessano per migliorare gli algoritmi :D

zephyrio
07-11-2011, 00:30
Direi che Dijkstra Ŕ abbastanza fondamentale.

Riguardo all'algoritmo qualcuno ha qualche idea :( ?

Loading