Il percorso più breve per trasformare una parola in un'altra

StackOverflow https://stackoverflow.com/questions/1521958

Domanda

Per un progetto di strutture dati, devo trovare il percorso più breve tra due parole (come "cat" E "dog"), cambiando solo una lettera alla volta.Ci viene fornito un elenco di parole di 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).È preferibile qualcosa di ridicolo e/o provocatorio.

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

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

È stato utile?

Soluzione

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

È possibile modificare il programma dinamico utilizzato per calcolare il file Distanza di Levenshtein per ottenere la sequenza delle operazioni.

MODIFICARE:Se il numero di stringhe è costante il problema è risolvibile in tempo polinomiale.Altrimenti è NP-difficile (è tutto lì su Wikipedia) ..supponendo che il tuo amico stia parlando del fatto che il problema è NP-difficile.

MODIFICARE:Se le tue corde hanno la stessa lunghezza, puoi usare Distanza di Hamming.

Altri suggerimenti

Con un dizionario, BFS è ottimale, ma il tempo di calcolo necessaria è proporzionale alle sue dimensioni (V + E). Con lettere n, il dizionario potrebbe avere ~ a ^ n interi, dove a è formato alfabeto. Se il dizionario contiene tutte le parole, ma quello che dovrebbe essere alla fine della catena, allora si attraversano tutte le parole possibili, ma non troverete nulla. Questo è il grafico attraversamento, ma la dimensione potrebbe essere esponenzialmente grande.

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

Il problema:

Si è dato un modo veloce (lineare) per controllare se una parola è nel dizionario, due parole u, V e per verificare se c'è una sequenza di u -> un 1 -> un 2 -> ... -> un n -.> v

è NP-hard.

Prova: Prendete un po 'esempio 3SAT, come

(p o q o meno r) e (p o meno q o r)

Si inizierà con 0 000 00 e sono per verificare se è possibile andare a 2 222 22.

Il primo carattere sarà "siamo finito", tre successivi bit controlleranno p, q, r e due accanto controlleranno clausole.

parole ammessi sono:

  • Tutto ciò che inizia con 0 e contiene solo 0 e 1.
  • Tutto ciò che inizia con 2 ed è legale. Ciò significa che esso consiste di 0 e di 1 (ad eccezione che il primo carattere è 2, tutte le clausole bit vengono giustamente stabiliti in base alle variabili bit, e stanno impostato a 1 (quindi questo dimostra che la formula è satisfable).
  • Tutto ciò che inizia con almeno due di 2 e poi è composto di (espressione regolare 0 e 1.: 222 * (0 + 1) *, come 22.221.101 ma non 2.212.001

Per produrre 2 222 22 da 0 000 00, si deve fare in questo modo:

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

(2) Modificare il primo bit a 2:. 2 100 111. Qui sarete verificato questa è davvero una soluzione 3SAT

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

Queste regole impongono che non si può barare (controllo). Andando a 2 222 22 è possibile solo se la formula è satisfable, e verificando che è NP-hard. Sento che potrebbe essere ancora più difficile (o #P FNP probabilmente), ma NP-difficile è sufficiente a tal fine penso.

Modifica : Potreste essere interessati a insieme disgiunto struttura dati . Questo richiederà il dizionario e di gruppo le parole che si possono raggiungere gli uni dagli altri. È anche possibile memorizzare un percorso da ogni vertice di sradicare o qualche altro vertice. Questo vi darà un percorso, non neccessarily il più breve.

Ci sono metodi di diversa efficienza per trovando link - è possibile costruire 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.

V'è, tuttavia, un modo per migliorare in modo significativo il tempo di esecuzione: Invece di fare un unico BFS dal nodo di origine, fare due ampiezza prime ricerche, a partire alle due estremità del grafico, e chiude quando si trova un nodo comune in i loro set di frontiera. La quantità di lavoro che dovete fare è circa la metà ciò che è richiesto se si cerca da un solo lato.

Si può rendere un po 'più veloce, eliminando le parole che non sono della lunghezza giusta, in primo luogo. Più del dizionario limitata si adatta nella cache della CPU. Probabilmente tutto questo.

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

Si potrebbe usare un po 'di magia preprocessore e hard-compilare il compito per quella parola di lunghezza, o rotolare alcune varianti ottimizzate del compito per lunghezze di parola comuni. Tutti questi paragoni in più può 'andare via' per gioco srotolato puro.

Questo è un tipico dinamica problema di programmazione . Verificare per il problema Edit distanza.

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

Da ( http://en.wikipedia.org/wiki/Edit_distance ): "In teoria dell'informazione e informatica, la distanza di montaggio tra due stringhe di caratteri è il numero di operazioni necessarie per trasformare uno di questi giunge l'altro".

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

Si potrebbe trovare la più lunga sottosequenza comune, e quindi trovare le lettere che devono essere modificati.

La mia sensazione è che il tuo amico è corretto, in quanto non v'è una soluzione più efficiente, ma che si assume di si sta ricaricando il dizionario ogni volta. Se si dovesse mantenere un database in esecuzione di transizioni comuni, quindi sicuramente ci sarebbe un metodo più efficiente per trovare una soluzione, ma si avrebbe bisogno di generare le transizioni in anticipo, e scoprire quali transizioni sarebbe utile (dal momento che non può generare tutti!) è 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 elemento della coda per memorizzare la parola e la lunghezza minima della catena // per raggiungere la parola. 

struct QItem
{
  string word;
  int len;
};

// lunghezza rendimenti di breve catena per raggiungere il 'target' da 'start' // utilizzando il numero minimo di mosse adiacenti. D è dizionario 

int shortestChainLen(string& start, string& target, set<string> &D)
{
  // Create a queue for BFS and insert 'start' as source vertex
  queue<QItem> 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<string>::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<string> 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/

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top