[C++] Simulazione stazione ferroviaria: gestire scambi

[Dani88]

Ciao a tutti
Avrei bisogno di un aiuto per questo progetto: in pratica devo simulare una stazione ferroviaria in cui arriva un treno da un binario e devo decidere su quale degli N presenti in stazione mandarlo (evitando tamponamenti ovviamente) azionando gli scambi in modo corretto.

Inizialmente ho pensato una cosa del tipo: cerco il primo binario libero (suppongo ognuno possegga un ID numerico e cerco da 0 in poi uno libero) a questo punto devo determinare la sequenza di attivazione scambi. Qui sto riscontrando un po di problemi, in quanto "il binario deve sapere" a quali scambi è collegato e come devono essere attuati per raggiungerlo.
Ho iniziato con un certo metodo ma arrivato ad un punto non riesco ad identificare in modo univoco la strada, o meglio lo scambio da far scattare... (non metto pseudo codice per non influenzarvi con la mia scelta)

Voi come affrontereste il problema?
Direi che la struttura è ad albero binario (un ingresso -> 2 uscite per ogni scambio) però qui si tratta di risalire dalle foglie alla radice diciamo.
Non posso inoltre usare strutture dati troppo complesse (problemi di ram e memoria).

Ringrazio tutti per qualunque aiuto o spunto

[Varilion]

La prima cosa che mi viene in mente è vedere il Treno che impegna i binari X,Y,Z come oggetto diciamo. E la strutture della stazione come un set di vincoli. In questo modo usando un qualsiasi tool di model checking si dovrebbe poter giungere ad una soluzione ed essere in grado di gestire N treni simultaneamente...ma forse è un "overkill".


Se tu devi gestire esclusivamente il fatto che UN treno arrivi e debba essere mandato tramite un apposita configurazione di scambi su di UN binario vuoto la cosa è più semplice.

Ipotizziamo che il grafo che rappresenta i binari della stazione sia aciclico (quindi hai un albero) si potrebbe fare una struttura dati piuttosto banale in cui hai come radice il binario in cui sta arrivando il treno e poi tutto l'albero binario a cascata sapendo che i nodi hanno due uscite. (In realtà hai più nodi in ingresso, ma non ti interessa perché il treno è su di uno di essi).
Quindi ti limiti ad esplorare sto grafo fino a che non trovi un percorso "valido", puoi usare l'algoritmo che più preferisci...deep-first (ti devi però memorizzare da qualche parte una pila con il tuo percorso di esplorazione, che costituisce la tua soluzione) o altro. Se ogni nodo conosce il suo "padre" puoi anche fare un po' di pruning rimuovendo i binari occupati..ma..non saprei..

Non sono 100% sicuro di aver capito il problema però.

[Dani88]

Dalla soluzione che mi hai detto direi che si, hai capito il problema.
Io ora studiandoci ancora un po ho fatto la seguente cosa: uso in pratica una matrice.
Per ogni binario creo un array, ogni posizione corrisponde ad uno scambio e il valore può essere:
- LEFT
- RIGHT
- NOT USED
In questo modo ogni binario "sa" come settare gli scambi per essere raggiunto
Poi uso un array di binari in cui metto gli array precedenti.
Quando cerco un binario vuoto recupero l'array del binario trovato vuoto e leggo i vari elementi per settare gli scambi.

Non so se sia più efficiente sia in termini di computazione che di spazio.
La ricerca di un binario libero è però lineare (ho un vettore con lo stato dei binari e cerco il primo libero) dopodichè settare gli scambi anche è un'altra operazione lineare (scorro il vettore e setto)

PS: il tutto deve girare su un microcontroller quindi come dicevo lo spazio è limitato, ho cercato di non usare oggetti e altro.

[marco.r]

non va bene un semplice algoritmo di ricerca su albero che quando trova il target "riempie" il percorso ? in pseudo-codice qualcosa tipo

// rappresento ogni scambio con una tupla (from,left,right), dove from left e right sono i binari di parteza, sinistro e destro

find_path(switch, destination, result ):
  if (switch == null) return false;
  if (switch.from == destination)
    result.push(destination);
    return true;
  if (find_path(switch.left, destination, result))
    result.push(switch.from)
    return true
  if (find_path(switch.right, destination, result))
    result.push(switch.from)
    return true
  return false

Alla fine ti trovi in result i valori in ordine inverso (ovviamente in microcontrollore invece che aggiugnere ad una struttura dati non farai che salvare in un puntatore e incrementare/decrementare. il concetto e' quello)

[sottovento]

Secondo me una semplice politica di assegnazione dei nomi ti risolverebbe il problema facilmente.
Esempio: supponi per semplicita' di avere una albero binario completo per rappresentare i binari, diciamo fino ad avere 8 foglie (= posizioni finali).

Occorre resistere alla tentazione di chiamare gli 8 binari finali con i numeri 1..8; invece si potrebbe fare cosi':

- il binario di partenza (beh potrebbe non avere un nome ma noi glielo assegnamo lo stesso) lo chiamiamo "1000";
- i due binari che dipartono da questo li potremmo chiamare
"1100" e "1200";
- i binari che dipartono da questi due ovviamente li chiameremo
"1110", "1120" e "1210", "1220";
- infine gli ultimi binari saranno
"1111", "1112" (i figli di "1110")
"1121", "1122" (figli di "1120")
"1211", "1212" (figli di "1210")
"1221", "1222" (figli di "1220")

Immagino che ti suoni familiare, ed immagino che gia' avrai capito come generalizzare la politica di naming.

Puoi fare questa operazione di assegnazione dei nomi in inizializzazione, una volta che ti sia stato dato il layout della stazione.
Ora, e' tutto facile: se vuoi mandare il treno su un certo binario perche' sai che e' vuoto (per esempio, 1121), saprai che il treno attraversera' gli scambi:
1000->1100->1120->1121
e potrai controllare l'occupazione di ogni scambio

Trattandosi di politica di assegnazione dei nomi e nient'altro, sara' sicuramente veloce e molto compatto, quindi potrai inserire il tutto in un microcontroller