Kürzester Weg, um ein Wort in ein anderes zu verwandeln

https://stackoverflow.com/questions/1521958

19-09-2019
|

Frage

Für ein Datenstrukturenprojekt muss ich den kürzesten Weg zwischen zwei Wörtern finden (wie wie "cat" und "dog"), wechseln Sie jeweils nur einen Buchstaben. Wir erhalten eine Scrabble -Wortliste, um unseren Weg zu finden. Zum Beispiel:

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

Ich habe das Problem mit einer breiten ersten Suche gelöst, suche aber etwas Besseres (ich habe das Wörterbuch mit einem Trie dargestellt).

Bitte geben Sie mir einige Ideen für eine effizientere Methode (in Bezug auf Geschwindigkeit und Speicher). Etwas Lächerliches und/oder Herausforderndes wird bevorzugt.

Ich fragte einen meiner Freunde (er ist ein Junior) und er sagte, dass es gibt nein Effiziente Lösung für dieses Problem. Er sagte, ich würde erfahren, warum, als ich den Algorithmenkurs belegte. Irgendwelche Kommentare dazu?

Wir müssen uns vom Wort zum Wort bewegen. Wir können nicht gehen cat -> dat -> dag -> dog. Wir müssen auch den Traversal ausdrucken.

Lösung

Neue Antwort

Angesichts des letzten Updates können Sie A* mit der Hamming -Distanz als Heuristik versuchen. Es ist eine zulässige Heuristik, da es die Entfernung nicht überschätzen wird

Alte Antwort

Sie können das Dynamikprogramm ändern, das zur Berechnung der Berechnung verwendet wird Levenshtein -Entfernung Um die Abfolge von Operationen zu erhalten.

Bearbeiten: Wenn es eine konstante Anzahl von Zeichenfolgen gibt, ist das Problem in der Polynomzeit lösbar. Sonst ist es np-hard (es ist alles in Wikipedia da). Angenommen, Ihr Freund spricht über das Problem, das NP-Hard ist.

Bearbeiten: Wenn Ihre Saiten gleich lang sind, können Sie verwenden Hamming -Entfernung.

Andere Tipps

Bei einem Wörterbuch ist BFS optimal, aber die benötigte Laufzeit ist proportional zu seiner Größe (V+E). Bei N -Buchstaben kann das Wörterbuch ~ a^n verdrängt haben, wobei a Alphabetgröße ist. Wenn das Wörterbuch alle Wörter enthält, aber das, das sich am Ende der Kette befinden sollte, werden Sie alle möglichen Wörter durchqueren, aber nichts finden. Dies ist ein Graph -Traversal, aber die Größe könnte exponentiell groß sein.

Sie fragen sich vielleicht, ob es möglich ist, es schneller zu machen - die Struktur "intelligent" zu durchsuchen und sie in Polynomzeit zu tun. Die Antwort ist, denke ich, nein.

Das Problem:

Sie haben einen schnellen (linearen) Weg, um zu überprüfen, ob sich ein Wort im Wörterbuch befindet, zwei Wörter u, v und überprüft, ob es eine Sequenz u -> a₁ -> a₂ -> ... -> a_n -> v.

ist np-hard.

Beweis: Nehmen Sie eine 3SAT -Instanz wie

(p oder q oder nicht r) und (p oder nicht q oder r)

Sie beginnen mit 0 000 00 und müssen prüfen, ob es möglich ist, zu 2 222 22 zu gehen.

Der erste Charakter wird "sind wir fertig", drei nächste Bits steuern P, Q, R und zwei nächste Klauseln.

Erlaubte Wörter sind:

Alles, was mit 0 beginnt und nur 0 und 1 enthält
Alles, was mit 2 beginnt und legal ist. Dies bedeutet, dass es aus 0 und 1 besteht (außer dass der erste Charakter 2 ist, alle Klauseln zu Recht nach Variablen -Bits eingestellt und auf 1 gesetzt werden (so zeigt dies, dass die Formel zufrieden ist).
Alles, was mit mindestens zwei 2er beginnt und dann aus 0er und 1 besteht (regulärer Ausdruck: 222* (0+1)*, wie 22221101, aber nicht 2212001

Um 2 222 22 von 0 000 00 zu produzieren, müssen Sie dies auf diese Weise tun:

(1) Geeignete Bits umdrehen - zB 0 100 111 in vier Schritten. Dies erfordert eine 3SAT -Lösung.

(2) Ändern Sie das erste Bit auf 2: 2 100 111. Hier werden Sie verifiziert, dass dies tatsächlich eine 3SAT -Lösung ist.

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

Diese Regeln erzwingen, dass Sie nicht betrügen können (überprüfen). Wenn die Formel befriedigt ist, ist es nur möglich, zu 2222 22 zu gehen und dies zu überprüfen. Ich denke, es könnte noch schwieriger sein (#P oder FNP wahrscheinlich), aber NP-Hartness ist für diesen Zweck ausreichend, denke ich.

Bearbeiten: Sie könnten interessiert sein disjunkte Datenstruktur. Dadurch werden Ihr Wörterbuch und Ihre Gruppenwörter angenommen, die voneinander erreicht werden können. Sie können auch einen Pfad von jedem Scheitelpunkt zu Wurzel oder einem anderen Scheitelpunkt speichern. Dies gibt Ihnen einen Weg, nicht merkwürdigsten.

Es gibt Methoden unterschiedlicher Effizienz für finden Links - Sie können für jede Wortlänge einen vollständigen Diagramm erstellen oder a konstruieren a Bk-Baum, Zum Beispiel, aber Ihr Freund hat Recht - BFS ist der effizienteste Algorithmus.

Es gibt jedoch eine Möglichkeit, Ihre Laufzeit erheblich zu verbessern: Anstatt ein einzelnes BFS aus dem Quellknoten durchzuführen, machen Sie zwei Breite zuerst, beginnend an beiden Engagements und enden Sie, wenn Sie einen gemeinsamen Knoten in ihren Grenzsätzen finden . Die Menge an Arbeit, die Sie leisten müssen, ist ungefähr die Hälfte, was erforderlich ist, wenn Sie nur von einem Ende suchen.

Sie können es ein wenig schneller machen, indem Sie zuerst die Wörter entfernen, die nicht die richtige Länge sind. Mehr des begrenzten Wörterbuchs passt in den CPU -Cache. Wahrscheinlich alles.

Außerdem können alle STRNCMP -Vergleiche (vorausgesetzt, Sie haben alles Kleinbuchstaben gemacht) MEMCMP -Vergleiche oder sogar abgerollte Vergleiche, die eine Beschleunigung sein können.

Sie können einige Präprozessorenmagie verwenden und die Aufgabe für diese Wortlänge fest kompilieren oder einige optimierte Variationen der Aufgabe für gemeinsame Wortlängen rollen. All diese zusätzlichen Vergleiche können für einen reinen, ungeholfenen Spaß "verschwinden".

Dies ist typisch Dynamische Programmierung Problem. Überprüfen Sie das Problem mit der Entfernung bearbeiten.

Was Sie suchen, heißt die Bearbeitungsentfernung. Es gibt viele verschiedene Typen.

Aus (http://en.wikipedia.org/wiki/edit_distance): "In Informationstheorie und Informatik ist die Bearbeitungsentfernung zwischen zwei Zeichenzeichenfolgen die Anzahl der Vorgänge, die erforderlich sind, um einen in den anderen zu verwandeln."

Dieser Artikel über Jazzy (die Java -Zauber -Check -API) hat einen schönen Überblick über diese Art von Vergleiche (es ist ein ähnliches Problem - Voraussetzungen vorgeschlagene Korrekturen) http://www.ibm.com/developerworks/java/library/j-jazzy/

Sie könnten die längste gemeinsame Subsequenz finden und daher die Buchstaben finden, die geändert werden müssen.

Mein Bauchgefühl ist, dass Ihr Freund korrekt ist, da es keine effizientere Lösung gibt, aber das ist, dass Sie das Wörterbuch jedes Mal neu laden. Wenn Sie eine laufende Datenbank mit gemeinsamen Übergängen beibehalten würden, würde es sicherlich eine effizientere Methode zum Auffinden einer Lösung geben, aber Sie müssten die Übergänge im Voraus generieren und herausfinden, welche Übergänge nützlich sind (da Sie nicht generieren können Sie alle!) Ist wahrscheinlich eine eigene Kunst.

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

// ein Warteschlangenelement zum Speichern von Wort und minimaler Kettenlänge //, um das Wort zu erreichen.

struct QItem
{
  string word;
  int len;
};

// gibt die kürzeste Kette zurück, um das Ziel von 'Start' zu erreichen // mit der minimalen Anzahl benachbarter Bewegungen. D ist Wörterbuch

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

Kopiert von: https://www.geeksforgeeks.org/word-ladder-lgth-of-shortest-chain-to-reach-a-target-word/

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow