Caminho mais curto para transformar uma palavra em outra

Question

Para um projeto de Estruturas de Dados, devo encontrar o caminho mais curto entre duas palavras (como "cat" e "dog"), alterando apenas uma letra por vez.Recebemos uma lista de palavras do Scrabble para usar para encontrar nosso caminho.Por exemplo:

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

Resolvi o problema usando uma primeira pesquisa ampla, mas estou procurando algo melhor (representei o dicionário com uma tentativa).

Por favor, me dê algumas idéias para um método mais eficiente (em termos de velocidade e memória).Algo ridículo e/ou desafiador é preferido.

Perguntei a um dos meus amigos (ele é júnior) e ele disse que há não solução eficiente para este problema.Ele disse que eu aprenderia o porquê quando fizesse o curso de algoritmos.Algum comentário sobre isso?

Devemos passar de palavra em palavra.Não podemos ir cat -> dat -> dag -> dog.Também temos que imprimir a travessia.

Answer 1

Nova resposta

Dada a atualização recente, você pode tentar um* com a distância de Hamming como heurística. É uma heurística admissível, pois não vai superestimar a distância

Resposta antiga

Você pode modificar o programa dinâmico usado para calcular o Distância de Levenshtein Para obter a sequência de operações.

EDIT: Se houver um número constante de cordas, o problema será solucionável no tempo polinomial. Caso contrário, é NP-Hard (está tudo lá na Wikipedia). Supondo que seu amigo esteja falando sobre o problema ser NP-Hard.

Editar: Se suas cordas forem de igual tempo, você pode usar Distância de Hamming.

Answer 2

Com um dicionário, o BFS é ideal, mas o tempo de execução necessário é proporcional ao seu tamanho (V+E). Com n letras, o dicionário pode ter ~ a^n em que um é o tamanho do alfabeto. Se o dicionário contiver todas as palavras, exceto o que deve estar no final da corrente, você atravessará todas as palavras possíveis, mas não encontrará nada. Isso é travessia de gráfico, mas o tamanho pode ser exponencialmente grande.

Você pode se perguntar se é possível fazê -lo mais rápido - navegar na estrutura "inteligentemente" e fazê -lo no tempo polinomial. A resposta é, eu acho, não.

O problema:

Você recebe uma maneira rápida (linear) de verificar se uma palavra está no dicionário, duas palavras u, v e devem verificar se há uma sequência u -> a₁ -> a₂ -> ... -> a_n -> v.

é np-duro.

Prova: pegue uma instância 3SAT, como

(p ou q ou não r) e (p ou não q ou r)

Você começará com 0 000 00 e deve verificar se é possível ir para 2 222 22.

O primeiro caractere será "Aregaremos", três próximos bits controlarão p, q, r e dois próximos controlarão as cláusulas.

As palavras permitidas são:

• Qualquer coisa que comece com 0 e contém apenas 0 e 1
• Qualquer coisa que começa com 2 e é legal. Isso significa que ele consiste em 0 e 1 (exceto que o primeiro caractere é 2, todos os bits de cláusulas são justamente definidos de acordo com bits de variáveis, e eles são definidos como 1 (então isso mostra que a fórmula é satisfatória).
• Qualquer coisa que começa com pelo menos dois 2 e depois é composta por 0 e 1 (expressão regular: 222* (0+1)*, como 22221101, mas não 2212001

Para produzir 2 222 22 a partir de 0 000 00, você deve fazer isso da seguinte maneira:

(1) Faça os bits apropriados - por exemplo, 0 100 111 em quatro etapas. Isso requer encontrar uma solução 3SAT.

(2) Altere o primeiro bit para 2: 2 100 111. Aqui você será verificado. Esta é realmente uma solução 3SAT.

(3) Mudança 2 100 111 -> 2 200 111 -> 2 220 111 -> 2 222 111 -> 2 222 211 -> 2 222 221 -> 2 222 222.

Essas regras aplicam que você não pode trapacear (verifique). Ir para 2 222 22 22 é possível apenas se a fórmula for satisfatória, e a verificação é NP. Eu sinto que pode ser ainda mais difícil (#P ou FNP provavelmente), mas a ponta do NP é suficiente para esse fim, eu acho.

Editar: Você pode estar interessado em Estrutura de dados do conjunto disjunto. Isso levará seu dicionário e palavras em grupo que podem ser alcançadas uma da outra. Você também pode armazenar um caminho de todos os vértices para root ou algum outro vértice. Isso lhe dará um caminho, não o mais curto.

Answer 3

Existem métodos de eficiência variável para encontrando Links - você pode construir um gráfico completo para cada comprimento da palavra ou pode construir um BK-Tree, por exemplo, mas seu amigo está certo - o BFS é o algoritmo mais eficiente.

Há, no entanto, uma maneira de melhorar significativamente o seu tempo de execução: em vez de fazer um único BFS do nó de origem, faça duas primeiras pesquisas amplas, começando em cada extremidade do gráfico e terminando quando você encontrar um nó comum em seus conjuntos de fronteira . A quantidade de trabalho que você precisa fazer é aproximadamente metade do que é necessário se você pesquisar apenas de uma extremidade.

Answer 4

Você pode torná -lo um pouco mais rápido removendo as palavras que não são o comprimento certo, primeiro. Mais do dicionário limitado se encaixará no cache da CPU. Provavelmente tudo isso.

Além disso, todas as comparações STRNCMP (assumindo que você fizeram tudo em minúsculas) podem ser comparações do MEMCMP, ou mesmo comparações desenroladas, que podem ser uma aceleração.

Você pode usar alguma mágica pré-processadora e compilar na tarefa para esse comprimento de palavra ou rolar algumas variações otimizadas da tarefa para comprimentos comuns das palavras. Todas essas comparações extras podem "ir embora" por pura diversão sem enrolamento.

Answer 5

Este é um típico programaçao dinamica problema. Verifique o problema da distância de edição.

Answer 6

O que você está procurando é chamado de distância de edição. Existem muitos tipos diferentes.

A partir de (http://en.wikipedia.org/wiki/Edit_Distance): "Na teoria da informação e na ciência da computação, a distância de edição entre duas cordas de caracteres é o número de operações necessárias para transformar uma delas na outra".

Este artigo sobre Jazzy (A API de verificação ortográfica de Java) tem uma boa visão geral desses tipos de comparações (é um problema semelhante - fornecendo correções sugeridas) http://www.ibm.com/developerworks/java/library/j-jazzy/

Answer 7

Você pode encontrar a subsequência mais comum mais longa e, portanto, encontrar as letras que devem ser alteradas.

Answer 8

Meu pressentimento é que seu amigo está correto, pois não há uma solução mais eficiente, mas isso está assumindo que você está recarregando o dicionário sempre. Se você mantivesse um banco de dados em execução de transições comuns, certamente haveria um método mais eficiente para encontrar uma solução, mas você precisaria gerar as transições de antemão e descobrir quais transições seriam úteis (já que você não pode gerar Todos eles!) Provavelmente é uma arte própria.

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

// Um ​​item da fila para armazenar a palavra e o comprimento mínimo da cadeia // para alcançar a palavra.

struct QItem
{
  string word;
  int len;
};

// Retorna o comprimento da cadeia mais curta para atingir o 'alvo' de 'start' // usando o número mínimo de movimentos adjacentes.D é dicionário

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-chain-to-reach-a-target-word/