tag que palabras nube name keywords description caracteres algorithm shortest-path edit-distance hamming-distance

algorithm - que - meta name keywords



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

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

Además, todas las comparaciones de strncmp (suponiendo que haya hecho todo en minúscula) pueden ser comparaciones de memcmp, o incluso comparaciones desenrolladas, lo que puede ser una aceleración.

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

Para un proyecto de Data Structures, debo encontrar la ruta más corta entre dos palabras (como "cat" y "dog" ), cambiando solo una letra a la vez. Nos dan una lista de palabras de Scrabble para usar en encontrar nuestro camino. Por ejemplo:

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

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

Por favor, dame 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 (es un junior) y me dijo que no hay una solución eficiente para este problema. Dijo que aprendería por qué cuando tomé el curso de algoritmos. ¿Algún comentario sobre eso?

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

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 puede tener ~ a ^ n entires, donde a es el tamaño del alfabeto. Si el diccionario contiene todas las palabras, pero la que debería estar al final de la cadena, atravesará todas las palabras posibles pero no encontrará nada. Esto es gráfico transversal, pero el tamaño puede ser exponencialmente grande.

Puede preguntarse si es posible hacerlo más rápido: explorar la estructura de forma "inteligente" y hacerlo en tiempo polinomial. La respuesta es, creo, no.

El problema:

Se le proporciona una forma rápida (lineal) para verificar si una palabra está en el diccionario, dos palabras u, v y debe verificar si hay una secuencia u -> a 1 -> a 2 -> ... -> a n -> v.

es NP-difícil.

Prueba: tomar algunas instancias 3SAT, como

(p o q o no r) y (p o no q o r)

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

El primer carácter será "hemos terminado", tres próximos bits controlarán p, q, r y dos siguientes controlarán las cláusulas.

Las palabras permitidas son:

  • Todo lo que comienza con 0 y contiene solo 0 y 1
  • Cualquier cosa que comience con 2 y es legal. Esto significa que consta de 0 y 1 (excepto que el primer carácter es 2, todos los bits de las cláusulas se establecen correctamente según los bits de variables, y se establecen en 1 (por lo que esto muestra que la fórmula es satisfactoria).
  • Todo lo que comienza con al menos dos 2 y luego está compuesto por 0 y 1 (expresión regular: 222 * (0 + 1) *, como 22221101 pero no 2212001

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

(1) Voltee los 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í se verificará que se trata de 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 trampas (verificar). Pasar a 2 222 22 es posible solo si la fórmula es satisfactoria y verifica que sea NP-hard. Siento que podría ser incluso más difícil (probablemente sea #P o FNP), pero la dureza NP es suficiente para ese propósito, creo.

Editar : es posible que le interese la estructura de datos de conjuntos disjuntos . Esto tomará sus palabras de diccionario y grupo que se pueden alcanzar entre sí. También puede almacenar una ruta desde cada vértice hasta la raíz o algún otro vértice. Esto te dará un camino, no necesariamente el más corto.

Existen métodos para variar la eficiencia para encontrar enlaces: puede construir un gráfico completo para cada longitud de palabra, o puede construir un BK-Tree , por ejemplo, pero su 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, realice dos primeras búsquedas de amplitud, comenzando en cualquier extremo del gráfico y terminando cuando encuentre un nodo común en sus conjuntos fronterizos . La cantidad de trabajo que tiene que hacer es aproximadamente la mitad de lo que se requiere si busca solo desde un extremo.

Mi intuición es que su amigo está en lo cierto, en que no hay una solución más eficiente, pero eso supone que está recargando el diccionario todo el tiempo. 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 ellos!) es probablemente un arte propio.

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

NUEVA RESPUESTA

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

ANTIGUA RESPUESTA

Puede modificar el programa dinámico utilizado para calcular la distancia Levenshtein para obtener la secuencia de operaciones.

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

EDITAR: si tus cadenas tienen la misma longitud, puedes usar la distancia de Hamming .

Lo que estás buscando se llama Editar Distancia. 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 la cantidad de operaciones necesarias para transformar una de ellas en la otra".

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