Chemin le plus court pour transformer un mot en un autre

Question

Pour un projet de structures de données, je dois trouver le chemin le plus court entre deux mots (comme "cat" et "dog"), changer une seule lettre à la fois. On nous donne une liste de mots Scrabble à utiliser pour trouver notre chemin. Par exemple:

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

J'ai résolu le problème en utilisant une première recherche d'étendue, mais je cherche quelque chose de mieux (j'ai représenté le dictionnaire avec un trie).

Veuillez me donner quelques idées pour une méthode plus efficace (en termes de vitesse et de mémoire). Quelque chose de ridicule et / ou difficile est préféré.

J'ai demandé à un de mes amis (c'est un junior) et il a dit qu'il y avait non solution efficace à ce problème. Il a dit que j'apprendrais pourquoi lorsque j'ai suivi le cours des algorithmes. Des commentaires à ce sujet?

Nous devons passer d'un mot à l'autre. Nous ne pouvons pas y aller cat -> dat -> dag -> dog. Nous devons également imprimer la traversée.

Answer 1

Nouvelle réponse

Compte tenu de la récente mise à jour, vous pouvez essayer un * avec la distance de Hamming comme une heuristique. C'est une heuristique admissible car elle ne va pas surestimer la distance

Ancienne réponse

Vous pouvez modifier le programme dynamique utilisé pour calculer le Distance de Levenshtein pour obtenir la séquence d'opérations.

EDIT: S'il y a un nombre constant de chaînes, le problème est résoluble en temps polynomial. Sinon, c'est du NP-dur (tout est là à Wikipedia) .. en supposant que votre ami parle du problème du NP.

Edit: si vos cordes sont de longueur égale, vous pouvez utiliser Distance de Hamming.

Answer 2

Avec un dictionnaire, BFS est optimal, mais le temps d'exécution nécessaire est proportionnel à sa taille (V + E). Avec n lettres, le dictionnaire pourrait avoir ~ a ^ n entires, où a est de la taille de l'alphabet. Si le dictionnaire contient tous les mots mais celui qui devrait être à la fin de la chaîne, alors vous traverserez tous les mots possibles mais ne trouverez rien. Il s'agit de la traversée du graphique, mais la taille peut être exponentiellement grande.

Vous vous demandez peut-être s'il est possible de le faire plus rapidement - de parcourir la structure "intelligemment" et de le faire en temps polynomial. La réponse est, je pense, non.

Le problème:

On vous donne un moyen rapide (linéaire) de vérifier si un mot est dans le dictionnaire, deux mots u, v et doivent vérifier s'il y a une séquence u -> a₁ -> A₂ -> ... -> A_n -> v.

est np-dur.

Preuve: prenez une instance 3SAT, comme

(p ou q ou non r) et (p ou non q ou r)

Vous commencerez par 0 000 00 et vous allez vérifier s'il est possible d'aller à 2 222 22.

Le premier personnage sera "Are Nous terminés", trois prochains bits contrôleront P, Q, R et deux Next contrôlera les clauses.

Les mots autorisés sont:

• Tout ce qui commence par 0 et ne contient que 0 et 1
• Tout ce qui commence par 2 et est légal. Cela signifie qu'il se compose de 0 et 1 (sauf que le premier caractère est 2, tous les bits de clauses sont à juste titre définis selon les bits de variables, et ils sont définis sur 1 (ce qui montre que la formule est satisfable).
• Tout ce qui commence par au moins deux 2, puis est composé de 0 et 1 (Expression régulière: 222 * (0 + 1) *, comme 22221101 mais pas 2212001

Pour produire 2 222 22 à partir de 0 000 00, vous devez le faire de cette manière:

(1) Retourner les bits appropriés - par exemple 0 100 111 en quatre étapes. Cela nécessite de trouver une solution 3SAT.

(2) Changer le premier bit en 2: 2 100 111. Ici, vous serez vérifié qu'il s'agit en effet d'une solution 3SAT.

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

Ces règles appliquent que vous ne pouvez pas tricher (vérifier). Aller à 2 222 22 n'est possible que si la formule est satisfaisante et que la vérification est du NP. Je pense que cela pourrait être encore plus difficile (#P ou FNP probablement), mais NP-Hardness est suffisant pour cette fin, je pense.

Éditer: Vous pourriez être intéressé par Structure de données de définition disjointe. Cela prendra votre dictionnaire et vos mots de groupe qui peuvent être atteints les uns des autres. Vous pouvez également stocker un chemin de chaque sommet à la racine ou à un autre sommet. Cela vous donnera un chemin, pas nécessaire le plus court.

Answer 3

Il existe des méthodes d'efficacité variable pour découverte Liens - Vous pouvez construire un graphique complet pour chaque longueur de mot, ou vous pouvez construire un Bk, par exemple, mais votre ami a raison - BFS est l'algorithme le plus efficace.

Il existe cependant un moyen d'améliorer considérablement votre exécution: au lieu de faire un seul BFS à partir du nœud source, effectuez deux premières recherches, à partir de l'une ou l'autre extrémité du graphique et à vous terminer lorsque vous trouvez un nœud commun dans leurs ensembles de frontières . La quantité de travail que vous devez faire est d'environ la moitié de ce qui est nécessaire si vous recherchez à partir d'une seule extrémité.

Answer 4

Vous pouvez le rendre un peu plus rapide en supprimant les mots qui ne sont pas la bonne longueur, d'abord. Plus du dictionnaire limité s'intégrera dans le cache du CPU. Probablement tout cela.

De plus, toutes les comparaisons STRNCMP (en supposant que vous avez tout fait en minuscules) peuvent être des comparaisons MEMCMP, voire des comparaisons déroulées, ce qui peut être une accélération.

Vous pouvez utiliser de la magie préprocesseur et compiler dur la tâche pour cette longueur de mot, ou laver quelques variations optimisées de la tâche pour les longueurs de mots communes. Toutes ces comparaisons supplémentaires peuvent «disparaître» pour un pur plaisir sans présélection.

Answer 5

C'est un typique programmation dynamique problème. Vérifiez le problème de distance de modification.

Answer 6

Ce que vous recherchez s'appelle la distance d'édition. Il existe de nombreux types différents.

De (http://en.wikipedia.org/wiki/edit_distance)) "Dans la théorie de l'information et l'informatique, la distance de modification entre deux chaînes de caractères est le nombre d'opérations nécessaires pour en transformer l'une en l'autre."

Cet article sur Jazzy (l'API de vérification orthographique Java) a un bel aperçu de ces types de comparaisons (c'est un problème similaire - fournissant des corrections suggérées) http://www.ibm.com/developerworks/java/library/j-jazzy/

Answer 7

Vous pouvez trouver la plus longue sous-séquence commune, et donc trouver les lettres qui doivent être modifiées.

Answer 8

Mon intestin est que votre ami a raison, en ce qu'il n'y a pas de solution plus efficace, mais c'est en train de vous recharger le dictionnaire à chaque fois. Si vous deviez conserver une base de données en cours d'exécution de transitions courantes, alors il y aurait sûrement une méthode plus efficace pour trouver une solution, mais vous devrez générer les transitions à l'avance et découvrir quelles transitions seraient utiles (car vous ne pouvez pas générer tous!) est probablement un art propre.

Answer 9

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 élément de file d'attente pour stocker le mot et la longueur de chaîne minimale // pour atteindre le mot.

struct QItem
{
  string word;
  int len;
};

// Renvoie la longueur de la chaîne la plus courte pour atteindre la «cible» de «start» // en utilisant le nombre minimum de mouvements adjacents. D est dictionnaire

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; 
}

Copié de: https://www.geeksforgeeks.org/word-ladder-lengthof-shortest-chain-to-reach-a-target-word/