El camino más corto para transformar una palabra en otra

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

Pregunta

Para un proyecto de estructuras de datos, debo encontrar la ruta más corta entre dos palabras (como "cat" y "dog"), cambiando solo una carta a la vez. Se nos da una lista de palabras de Scrabble para usar para encontrar nuestra ruta. Por ejemplo:

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

He resuelto el problema usando una primera búsqueda de amplitud, pero estoy buscando algo mejor (representé el diccionario con un trie).

Por favor, déme algunas ideas para un método más eficiente (en términos de velocidad y memoria). Se prefiere algo ridículo y/o desafiante.

Le pregunté a uno de mis amigos (él es un junior) y él dijo que hay no solución eficiente a este problema. Dijo que aprendería por qué cuando tomara el curso de algoritmos. ¿Algún comentario sobre eso?

Debemos movernos de una palabra a otra. No podemos ir cat -> dat -> dag -> dog. También tenemos que imprimir el recorrido.

¿Fue útil?

Solución

Nueva respuesta

Dada la actualización reciente, podría probar un* con la distancia de Hamming como heurística. Es una heurística admisible ya que no va a sobreestimar la distancia

Respuesta

Puede modificar el programa dinámico utilizado para calcular el Distancia de levenshtein Para obtener la secuencia de operaciones.

EDITAR: Si hay un número constante de cadenas, el problema se puede resolver en el tiempo polinomial. De lo contrario, es NP-Hard (todo está allí en Wikipedia) ... suponiendo que su amigo está hablando de que el problema es NP-Hard.

Editar: si sus cuerdas son de igual longitud, puede usar Distancia de hamming.

Otros consejos

Con un diccionario, BFS es óptimo, pero el tiempo de ejecución necesario es proporcional a su tamaño (V+E). Con n letras, el diccionario podría tener ~ a^n entires, donde un tamaño de alfabeto es. Si el diccionario contiene todas las palabras, pero la que debería estar al final de la cadena, entonces atravesará todas las palabras posibles pero no encontrará nada. Este es el recorrido gráfico, pero el tamaño podría ser exponencialmente grande.

Es posible que se pregunte si es posible hacerlo más rápido: navegar por la estructura "de manera inteligente" y hacerlo en tiempo polinómico. La respuesta es, creo, no.

El problema:

Se le da una forma rápida (lineal) de verificar si una palabra está en el diccionario, dos palabras u, v y debe verificar si hay una secuencia u -> a1 -> A2 -> ... -> Anorte -> v.

es np-hard.

Prueba: tome una instancia de 3SAT, como

(P o Q o no R) y (P o no Q o R)

Comenzará con 0 000 00 y verá si es posible ir a 2 222 22.

El primer personaje será "Are We We Terminado", tres bits siguientes controlarán P, Q, R y dos próximos controlarán las cláusulas.

Las palabras permitidas son:

  • Cualquier cosa que comience con 0 y contiene solo 0 y 1
  • Cualquier cosa que comience con 2 y sea legal. Esto significa que consiste en 0 y 1 (excepto que el primer carácter es 2, todos los bits de cláusulas se establecen legítimamente de acuerdo con los bits de variables, y se establecen en 1 (por lo que esto muestra que la fórmula es satisfactoria).
  • Cualquier cosa que comience con al menos dos 2 y luego se compone de 0 y 1 (expresión regular: 222* (0+1)*, como 22221101 pero no 2212001

Para producir 2 222 22 de 0 000 00, debe hacerlo de esta manera:

(1) Voltee bits apropiados - por ejemplo, 0 100 111 en cuatro pasos. Esto requiere encontrar una solución 3SAT.

(2) Cambie el primer bit a 2: 2 100 111. Aquí será verificado que esta es de hecho una solución 3SAT.

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

Estas reglas hacen cumplir que no puedes hacer trampa (verificar). Ir a 2 222 22 solo es posible si la fórmula es satisfactoria, y la verificación de eso es NP-Hard. Creo que podría ser aún más difícil (#P o FNP probablemente), pero creo que NP-Hardness es suficiente para ese propósito.

Editar: Te podría interesar Estructura de datos establecida de disjunto. Esto tomará su diccionario y palabras grupales que se pueden alcanzar entre sí. También puede almacenar una ruta desde cada vértice hasta root o algún otro vértice. Esto le dará un camino, no necesariamente el más corto.

Existen métodos de eficiencia variable para hallazgo enlaces: puede construir un gráfico completo para cada longitud de palabra, o puede construir un Bk-árbol, por ejemplo, pero tu amigo tiene razón: BFS es el algoritmo más eficiente.

Sin embargo, hay una forma de mejorar significativamente su tiempo de ejecución: en lugar de hacer un solo BFS desde el nodo fuente, hacer dos primeras búsquedas de amplitud, comenzando en cada extremo del gráfico y terminando cuando encuentre un nodo común en sus conjuntos de fronteras . La cantidad de trabajo que debe hacer es aproximadamente la mitad de lo que se requiere si busca solo un extremo.

Puede hacerlo un poco más rápido eliminando las palabras que no son la longitud correcta, primero. Más del diccionario limitado encajará en el caché de la CPU. Probablemente todo.

Además, todas las comparaciones STRNCMP (suponiendo que haya hecho todo en minúsculas) pueden ser comparaciones MEMCMP, o incluso comparaciones desactivadas, lo que puede ser una aceleración.

Puede usar algo de magia del preprocesador y compilar la tarea para esa longitud de palabras, o rodar algunas variaciones optimizadas de la tarea para longitudes de palabras comunes. Todas esas comparaciones adicionales pueden 'desaparecer' para la diversión pura desenrollada.

Este es un típico programación dinámica problema. Verifique el problema de la distancia de edición.

Lo que estás buscando se llama Distancia de edición. Hay muchos tipos diferentes.

De (http://en.wikipedia.org/wiki/edit_distance): "En la teoría de la información y la informática, la distancia de edición entre dos cadenas de caracteres es el número de operaciones requeridas para transformar una de ellas en la otra".

Este artículo sobre Jazzy (la API del corrector ortográfico de Java) tiene una buena visión general de este tipo de comparaciones (es un problema similar, proporcionando correcciones sugeridas) http://www.ibm.com/developerworks/java/library/j-jazzy/

Puede encontrar la posterior subsecuencia común más larga y, por lo tanto, encontrar las letras que deben cambiarse.

Mi instinto es que tu amigo tiene razón, ya que no hay una solución más eficiente, pero eso es asumiendo que estás recargando el diccionario cada vez. Si tuviera que mantener una base de datos en ejecución de transiciones comunes, seguramente habría un método más eficiente para encontrar una solución, pero necesitaría generar las transiciones de antemano y descubrir qué transiciones serían útiles (ya que no puede generar ¡Todos!) Es probablemente un arte propio.

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 de cola para almacenar palabras y longitud mínima de la cadena // para alcanzar la palabra.

struct QItem
{
  string word;
  int len;
};

// Devuelve la longitud de la cadena más corta para alcanzar 'objetivo' desde 'inicio' // utilizando un número mínimo de movimientos adyacentes. D es el diccionario

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

Copiado de: https://www.geeksforgeeks.org/word-ladder-length-of-shortest-hain-to-reach-a-target-word/

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top