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

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 usando una ricerca per 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 non esiste una soluzione efficace 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.

    NUOVA RISPOSTA

    Dato il recente aggiornamento, potresti provare A * con la distanza di Hamming come euristica. È un’euristica ammissibile poiché non sopravvaluterà la distanza

    VECCHIA RISPOSTA

    È ansible modificare il programma dinamico utilizzato per calcolare la distanza di Levenshtein per ottenere la sequenza di operazioni.

    EDIT: 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 tue corde sono di uguale lunghezza, puoi usare la distanza di Hamming .

    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 sia ansible farlo più velocemente – per esplorare la struttura “in modo intelligente” e farlo in tempo polinomiale. La risposta è, penso, no.

    Il problema:

    Ti viene dato un modo veloce (lineare) per verificare se una parola è in dizionario, due parole u, v e servono per verificare se c’è una sequenza u -> a 1 -> a 2 -> … -> a n -> v.

    è NP-difficile.

    Prova: prendi alcune istanze 3SAT, come

    (p o q o non r) e (pe non q o r)

    Inizierai con 0 000 00 e dovrai verificare se è ansible andare a 2 222 22.

    Il primo carattere sarà “siamo finiti”, tre bit successivi controlleranno p, q, r e due successive clausole di controllo.

    Le parole consentite sono:

    • Tutto ciò che inizia con 0 e contiene solo 0 e 1
    • Tutto ciò che inizia con 2 ed è legale. Ciò significa che consiste di 0 e di 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 e quindi è composto da 0 e 1 (espressione regolare: 222 * (0 + 1) *, come 22221101 ma non 2212001

    Per produrre 2 222 22 da 0 000 00, devi farlo in questo modo:

    (1) Capovolgere i bit appropriati, ad es. 0 100 111 in quattro passaggi. Ciò richiede la ricerca di 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.

    Queste regole fanno rispettare il fatto che non puoi imbrogliare (controllare). Passare a 2 222 22 è ansible 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 alla struttura dei dati dell’insieme disgiunto . 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.

    Esistono metodi di efficienza variabile per la ricerca di collegamenti: puoi build un grafico completo per ogni lunghezza di parola oppure puoi build un albero BK , ad esempio, ma il tuo amico ha ragione: BFS è l’algoritmo più efficiente.

    C’è, tuttavia, un modo per migliorare in modo significativo il tuo runtime: invece di fare un singolo BFS dal nodo sorgente, fai due ampie ricerche prima, a partire da entrambe le estremità del grafico, e terminando quando trovi 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à.

    Puoi renderlo un po ‘più veloce rimuovendo prima le parole che non sono della lunghezza giusta. Più del dizionario limitato si adatterà alla cache della CPU. Probabilmente tutto.

    Inoltre, tutti i confronti strncmp (supponendo che tu abbia reso tutto minuscolo) possono essere confronti tra memcmp, o anche confronti srotolati, che possono essere un aumento di velocità.

    Potresti usare un po ‘di magia per il preprocessore e compilare a mano il compito per quel word-length, o tirare alcune variazioni ottimizzate del compito per lunghezze di parole comuni. Tutti questi confronti extra possono “andare via” per puro divertimento srotolato.

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

    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 su Jazzy (l’API di controllo ortografico java) ha una buona panoramica di questi tipi di confronti (è un problema simile – fornendo correzioni suggerite) http://www.ibm.com/developerworks/java/library/j-jazzy/

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

    La mia sensazione istintiva è che il tuo amico sia corretto, nel senso che non esiste una soluzione più efficiente, ma ciò presuppone che tu stia 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.

     bool isadjacent(string& a, string& b) { int count = 0; // to store count of differences int n = a.length(); // Iterate through all characters and return false // if there are more than one mismatching characters for (int i = 0; i < n; i++) { if (a[i] != b[i]) count++; if (count > 1) return false; } return count == 1 ? true : false; } 

    // Un object in coda per memorizzare la parola e la lunghezza minima della catena // per raggiungere la parola.

     struct QItem { string word; int len; }; 

    // Restituisce la lunghezza della catena più breve per raggiungere ‘target’ da ‘start’ // usando il numero minimo di mosse adiacenti. D è un dizionario

     int shortestChainLen(string& start, string& target, set &D) { // Create a queue for BFS and insert 'start' as source vertex queue Q; QItem item = {start, 1}; // Chain length for start word is 1 Q.push(item); // While queue is not empty while (!Q.empty()) { // Take the front word QItem curr = Q.front(); Q.pop(); // Go through all words of dictionary for (set::iterator it = D.begin(); it != D.end(); it++) { // Process a dictionary word if it is adjacent to current // word (or vertex) of BFS string temp = *it; if (isadjacent(curr.word, temp)) { // Add the dictionary word to Q item.word = temp; item.len = curr.len + 1; Q.push(item); // Remove from dictionary so that this word is not // processed again. This is like marking visited D.erase(temp); // If we reached target if (temp == target) return item.len; } } } return 0; } // Driver program int main() { // make dictionary set D; D.insert("poon"); D.insert("plee"); D.insert("same"); D.insert("poie"); D.insert("plie"); D.insert("poin"); D.insert("plea"); string start = "toon"; string target = "plea"; cout << "Length of shortest chain is: " << shortestChainLen(start, target, D); return 0; } 

    Copiato da: https://www.geeksforgeeks.org/word-ladder-length-of-shortest-chain-to-reach-a-target-word/