Problema di efficienza ladder Word

Question

Problema di efficienza ladder Word

#1 da (2 voti)

4

Ho un problema con le word ladder. Il problema è: date due parole e un file di dizionario, trova la scala di parole più breve tra le due parole. Quindi se hai dato le parole cat e pot:

cat -> cot -> pot

Questo è solo un esempio facile. Hai un'idea.

Il problema è il vincolo temporale, Il problema richiede l'utilizzo di un grafico, che sarà veramente buono da usare poiché la seconda parte del problema riguarda la ricerca della scala con il minor peso.

Se pre-generi il grafico (generi il grafico completo all'esecuzione del programma) ci vorrà molto tempo. Dato che l'algoritmo che ho trovato confrontava ogni parola con tutte le altre parole del dizionario per trovare i nodi adiacenti. Questo arriva a O (n ^ 2) confronti, oltre a confrontare lettere di stesse parole di dimensioni. Che finisce per essere molto.

Ho eseguito un test con un elenco di parole da 1k e 3 lettere e ci sono voluti 2,6 secondi per generare il grafico. Ciò significa che con una lista di 200k ci vorranno 26 ore per generare il grafico.

Dopo averlo scoperto ho pensato di generare un grafico che inizia solo dalla parola di partenza e poi trova tutti i nodi adiacenti (parole che sono solo una lettera diversa) e quindi tutti i nodi adiacenti per i nodi adiacenti precedenti fino alla parola finale è stato trovato, o se non è stato trovato, non ci sarebbe alcun percorso.

Il linguaggio di programmazione è C ++. C'è un algoritmo più efficiente che potrei usare per questo?

c++ data-structures algorithms optimization graph

posta wax147 22.04.2016 - 12:36

fonte

1 risposta

Leggi altre domande sui tag c++ data-structures algorithms optimization graph

Ottenere gli stessi dati in più modi Che cosa significa "initialize event handler" in questo contesto?

score 2 · Answer 1

Questo è un esempio in cui i collegamenti in avanti nel grafico sono difficili da calcolare, ma i collegamenti inversi sono abbastanza facili, quindi indicizzali invece. Passare attraverso l'elenco di parole e creare voci per ogni collegamento alla parola. Ad esempio, la parola "cat" genererebbe le seguenti voci di indice:

".at" -> Set("cat")
"c.t" -> Set("cat")
"ca." -> Set("cat")

Quindi dopo aver indicizzato "cot", avresti:

".at" -> Set("cat")
"c.t" -> Set("cat", "cot")
"ca." -> Set("cat")
".ot" -> Set("cot")
"co." -> Set("cot")

Quando questo primo passaggio dell'indicizzazione, che può essere eseguito in O(n) , è completo, puoi eseguire un secondo passaggio O(n) per ottenere i collegamenti avanzati. Questa è solo l'unione di tutti gli insiemi a destra per una parola, meno la tua parola originale. A seconda della frequenza con cui utilizzi questa mappatura, potrebbe essere vantaggioso non eseguire questo passaggio completo, ma calcolarlo come necessario dal primo passaggio.