Memorizza algoritmi diversi e li usa per la dimostrazione

2

Ho un'app per creare grafici semplici (il tipo con vertici e bordi) e quindi utilizzare su di essi algoritmi diversi (BFS, DFS, topsort, Prim ecc.) per dimostrare come funzionano.

Ora sto lavorando per portarlo in un'app Rails e distribuirlo in modo che possa essere utilizzato dalla mia università (si spera).

Attualmente i grafici sono archiviati in un db SQLite e sto pensando di fare qualche magia D3 su di essi.

Quindi al vero problema, come devo implementare e memorizzare gli algoritmi?

Voglio essere in grado di "passare" attraverso l'algoritmo, mostrando passo per passo come funziona sul grafico. Nella mia precedente implementazione, scritta in Java, avevo una classe Algorithm astratta con metodi astratti come init, step e reset. Ma ora che siamo fuori dal mondo di Java e utilizziamo il meraviglioso Ruby, ho la sensazione che ci sia un modo davvero intelligente ed elegante per ottenere lo stesso risultato.

Sto pensando di comprimerlo in un motore Rails, solo per i calci.

Ecco l'implementazione Java citata: link

    
posta mfaerevaag 08.09.2013 - 18:13
fonte

1 risposta

1

Questo mi sembra una macchina a stati. Hai un grafico ( V , E ) e uno stato di attraversamento corrente S (è passato un po 'di tempo dalle mie classi di algoritmi, ma suppongo che si tratti di un passaggio ricorsivo di varie opzioni di esplorazione) tra cui un gestisci la tua strategia attualmente selezionata (es. l'algoritmo di attraversamento del grafico).

C'è una bella gemma di rubini chiamata state_machine che potrebbe darti la struttura di cui hai bisogno per spostarti tra stati come Initial -> In Progress (repeat as needed) -> Completed

La chiave qui sarà un modo per: - all'interno dello stato In Progress - serializzare i dettagli correnti del tuo attraversamento in modo che possa essere sospeso indefinitamente mentre lo mostri nel browser e poi riavviato su richiesta in per eseguire il passaggio successivo. Questo è un po 'come passare attraverso i punti di interruzione in un debugger, eccetto che probabilmente ne implementerai molto a mano piuttosto che fare affidamento su un vero debugger.

    
risposta data 09.09.2013 - 18:06
fonte

Leggi altre domande sui tag