Percorso più breve per trasformare una parola in un'altra

Question

Per un progetto Strutture di dati, devo trovare il percorso più breve tra due parole (come "cat" e "dog"), cambiando solo una lettera alla volta. Ci viene data una lista di parole Scrabble da utilizzare per trovare il nostro percorso. Per esempio:

cat -> bat -> bet -> bot -> bog -> dog 

Ho risolto il problema utilizzando una ricerca in ampiezza, ma sto cercando qualcosa di meglio (ho rappresentato il dizionario con un trie).

Per favore dammi alcune idee per un metodo più efficiente (in termini di velocità e memoria). Si preferisce qualcosa di ridicolo e/o impegnativo.

Ho chiesto a uno dei miei amici (lui è un junior) e ha detto che c'è no soluzione efficiente a questo problema. Ha detto che avrei imparato perché quando ho seguito il corso sugli algoritmi. Qualche commento su questo?

Dobbiamo passare da una parola all'altra. Non possiamo andare cat -> dat -> dag -> dog. Dobbiamo anche stampare l'attraversamento.

Answer 1

nuova risposta

Dato il recente aggiornamento, si potrebbe provare A * con la distanza di Hamming come euristica. Si tratta di un'euristica ricevibile in quanto non sta andando a sovrastimare la distanza

risposta Old

È possibile modificare la dinamica, programma utilizzato per calcolare il Levenshtein distance per ottenere la sequenza delle operazioni.

MODIFICA: Se c'è un numero costante di stringhe, il problema è risolvibile in tempo polinomiale. Altrimenti, è NP-difficile (è tutto lì in wikipedia) .. assumendo che il tuo amico stia parlando del problema essendo NP-hard.

MODIFICA: se le stringhe sono di uguale lunghezza, è possibile utilizzare Hamming distance.

Answer 2

È possibile trovare la sottosequenza comune più lunga e quindi trovare le lettere che devono essere modificate.

Answer 3

Questo è un tipico problema di dynamic programming. Verifica il problema di Modifica distanza.

Answer 4

Il mio istinto è che il tuo amico è corretto, nel senso che non c'è una soluzione più efficiente, ma questo è scontato che stai ricaricando il dizionario ogni volta. Se dovessi mantenere un database in esecuzione di transizioni comuni, sicuramente ci sarebbe un metodo più efficiente per trovare una soluzione, ma avresti bisogno di generare le transizioni in anticipo e scoprire quali transizioni sarebbero utili (dato che non puoi generare tutti loro!) è probabilmente un'arte a sé stante.

Answer 5

Ci sono metodi di diversa efficienza per trovare link - si può creare un grafico completo per ogni lunghezza di parola, oppure si può costruire un BK-Tree, per esempio, ma il tuo amico è giusto - BFS è l'algoritmo più efficiente.

Tuttavia, esiste un modo per migliorare in modo significativo il runtime: anziché eseguire un singolo BFS dal nodo di origine, eseguire due ricerche di ampiezza, a partire da entrambe le estremità del grafico, e terminare quando si trova un nodo comune nei loro set di frontiera. La quantità di lavoro che devi fare è all'incirca la metà di ciò che è necessario se cerchi da una sola estremità.

Answer 6

Con un dizionario, BFS è ottimale, ma il tempo di esecuzione necessario è proporzionale alla sua dimensione (V + E). Con n lettere, il dizionario potrebbe avere ~ a^n voci, dove a è la dimensione dell'alfabeto. Se il dizionario contiene tutte le parole tranne quella che dovrebbe essere alla fine della catena, allora attraverserai tutte le parole possibili ma non troverai nulla. Questo è attraversamento grafico, ma la dimensione potrebbe essere esponenzialmente grande.

Ci si potrebbe chiedere se è possibile farlo più velocemente - per esplorare la struttura "in modo intelligente" e farlo in tempo polinomiale. La risposta è, penso, no.

Il problema:

Ti danno un modo veloce (lineare) per controllare se una parola è nel dizionario, due parole u, v e sono per verificare se c'è una sequenza di u -> un -> un -> ... -> un _n -.> v

è NP-hard.

Dimostrazione: Prendete un po 'esempio 3SAT, come

(p o q o no r) e (p o no q o r)

Inizierete con 0 000 00 e sono per controllare se è possibile andare a 2 222 22.

Il primo carattere sarà "siamo finiti", tre bit successivi controlleranno p, q, re due clausole di controllo successivo.

parole ammessi sono:

• Tutto ciò che inizia con 0 e contiene solo 0 e 1 di
• Tutto ciò che inizia con 2 ed è legale. Ciò significa che consiste di 0 e 1 (eccetto che il primo carattere è 2, tutti i bit di clausole sono giustamente impostati in base ai bit delle variabili e sono impostati su 1 (quindi questo dimostra che la formula è soddisfacente.)
• Tutto ciò che inizia con almeno due 2 di e quindi è composto da (espressione regolare 0 e 1.: 222 * (0 + 1) *, come 22.221.101 ma non 2212001

Per produrre 2 222 22 da 0 000 00, quello che dovete fare in questo modo:..

(1) flip bit appropriati - ad esempio 0 100 111 in quattro fasi Ciò richiede di trovare una soluzione 3SAT

(2) Cambia il primo bit in 2: 2 100 111. Qui verrai verificato che si tratta di una soluzione 3SAT.

(3) modifica 2 100 111 -> 2 200 111 -> 2 220 111 -> 2 222 111 -> 2 222 211 -> 2 222 221 -> 2 222 222.

Tali norme impongono che non puoi imbrogliare (controllare). Passare a 2 222 22 è possibile solo se la formula è soddisfacente e controllare che sia NP-difficile. Sento che potrebbe essere ancora più difficile (probabilmente con #P o FNP), ma credo che la durezza NP sia sufficiente per quello scopo.

Modifica: Potresti essere interessato a disjoint set data structure. Questo richiederà il tuo dizionario e le parole di gruppo che possono essere raggiunte l'una dall'altra. Puoi anche memorizzare un percorso da ogni vertice a root o qualche altro vertice. Questo ti darà un percorso, non necessariamente il più breve.

Answer 7

Quello che stai cercando è chiamato Modifica distanza. Ci sono molti tipi diversi.

Da (http://en.wikipedia.org/wiki/Edit_distance): "Nella teoria dell'informazione e nell'informatica, la distanza di modifica tra due stringhe di caratteri è il numero di operazioni necessarie per trasformare una di esse nell'altra."

Questo articolo circa Jazzy (API Java controllo ortografico) ha una bella panoramica di questi tipi di confronti (si tratta di un problema simile - che forniscono correzioni suggerite) http://www.ibm.com/developerworks/java/library/j-jazzy/

Answer 8

si può rendere un po 'più veloce, eliminando le parole non sono della lunghezza giusta, per prima cosa. Più del dizionario limitato si adatterà alla cache della CPU. Probabilmente tutto.

Inoltre, tutti i confronti strncmp (supponendo che hai fatto tutto in minuscolo) possono essere paragoni memcmp, o anche i confronti srotolati, che può essere un aumento di velocità.

È possibile utilizzare un po 'di magia del preprocessore e compilare a mano l'attività per quella parola, oppure eseguire alcune variazioni ottimizzate dell'attività per le lunghezze di parole comuni. Tutti questi confronti extra possono "andare via" per puro divertimento srotolato.