lista mais longa de palavras com as letras inicial e final correspondentes

Meu amigo me deu um problema que ele diz ser fácil, mas não consigo descobrir um bom algoritmo para fazer isso.

Você recebe 100 palavras em inglês aleatórias. Você precisa encontrar a maior seqüência de palavras em que a última letra de uma palavra corresponde à primeira letra da palavra seguinte. Você pode usar cada palavra apenas uma vez.

Por exemplo, se você recebesse as palavras "gato", "cachorro", "isso", a corda mais longa que você poderia criar seria "gato -> isso". Se você recebesse as palavras "mouse", "alce", "unicórnio", a corda mais longa que você poderia criar seria apenas uma palavra (já que nenhuma dessas palavras está vinculada). Se você recebeu as palavras "pássaro", "prato", "harb", a corda mais longa que você poderia criar seria "harb -> pássaro -> prato" (ou "prato -> harb -> pássaro" ou "pássaro - > prato -> harb ").

Eu tive a idéia de modelar isso como um gráfico cíclico direcionado. Cada nó seria apenas uma palavra, com vértices indo para cada palavra / nó que começou com a letra em que essa palavra terminava.

+-------+         \ +------+
|  cat  |-----------| that |
+-------+         / +------+
    |                  |
   \|/                 |
+-------+ /            |
|  the  |--------------+
+-------+ \

Esse problema parece ser uma pesquisa de caminho mais longa , que é NP-Hard.

Há uma melhor forma de fazê-lo? Ou mesmo algum tipo de algoritmo de aproximação que poderia ser usado? Ou alguma maneira de explorar as qualidades do inglês para reduzir o espaço de pesquisa?

Eu acho que isso está relacionado ao problema do caminho mais longo (LP) que você mencionou, mas é um pouco diferente. A principal diferença é que o problema do LP tem um grau de conectividade mais alto do que o problema sugerido. Ao restringir suas conexões às últimas e primeiras letras, você remove um grande número de combinações em potencial.

Aqui está como eu recomendaria enfrentar este:

1. Para cada palavra da lista, conte as possíveis conexões de entrada e saída.
2. Descarte qualquer palavra que tenha 0 ins e 0 outs.
3. Identifique um conjunto inicial de "palavras iniciais" com o menor número de entradas e saídas, e as saídas devem ser maiores que 0.
4. Cada palavra inicial recebe sua própria cópia de trabalho da contagem de conexões de entrada / saída. Isso forma a cabeça da cadeia.
5. Para cada cadeia, identifique uma lista de "próximas palavras" com base em:
   
   • última letra inicial ou palavra anterior
   • menor número de conexões de entrada e saída (novamente, as saídas devem ser maiores que 0)
6. Para cada um next word, repita a etapa 5 até a cadeia terminar.

Tenha em mente que:

• Você precisará acompanhar o comprimento das cadeias e ter algum mecanismo global para identificar a cadeia mais longa.

• Você também precisará remover cada palavra da cópia de trabalho das contagens de conexão para evitar um loop recursivo.

• Em algum momento, sua cadeia será encerrada e você precisará selecionar uma palavra com uma contagem de 0 conexões de saída.

• Pode ser necessário recalcular entradas / saídas à medida que as palavras são removidas das listas de trabalho. À primeira vista, não acho que isso seja necessário, pois os conjuntos gerais serão relativamente pequenos. Se você tiver escalado para 1.000 palavras, ter contagens estáticas pode atrasar a convergência do algoritmo.

Eu meio que vi isso como um problema de embalagem. Para mim, as conexões dentro e fora identificam a forma a ser compactada. Quanto mais baixas as conexões, mais estranha é a forma. Quanto mais estranha a forma, mais cedo eu quero empacotá-la, pois percebi que há chances cada vez menores de conseguir uma forma estranha, mais tarde entrei na cadeia.

Como um exemplo:

{dog, gopher, alpha, cube, elegant, this, that, bart}

dog     0, 1
gopher  1, 0
alpha   0, 0
cube    0, 1
elegant 1, 2
this    3, 0
that    2, 1
bart    0, 2

//alpha is dropped with 0 in and 0 out.
//two candidates found: dog, cube

//chain 1
dog => gopher
//chain 2
cube => elegant => that => this

//Note 1: the following chain won't occur due to selection rules
//that takes priority over this because of output count
cube => elegant => this

//Note 2: this chain won't occur either due to selection rules
bart => that => this

Se você criar uma matriz 26X26 para representar um gráfico direcionado de vértice como cada alfabeto e palavras como aresta. Por exemplo, palavra - APPLE conecte o vértice A e E com a borda direcionada de A para E. Agora o problema se reduz à localização da maior trilha euleriana (caminho que inclui o número máximo de arestas, visitando cada aresta uma vez com a possível repetição de vértices) no gráfico. Um dos algoritmos O (E) seria iniciar aleatoriamente a partir de um par de vértices. Encontre um caminho entre eles. Do que continuar relaxando o caminho até que seja possível.

update @ GlenH7 Resolvi uma pergunta semelhante em www.hackerearth / jda recentemente, houve notas relativas à melhor solução e pontuei as notas mais altas com as seguintes

Dada lista de palavras. Encontre a cadeia mais longa que pode ser formada por eles. Uma cadeia é válida se cada palavra começar com uma letra * que termina no final da última palavra.

Approch =

1) faça o gráfico de alfabetos como vértices e palavras como arestas. No lugar de usar várias arestas, use uma com peso igual ao número de arestas.

2) encontre o componente fortemente conectado do gráfico com arestas máximas. Descarte temporariamente outras arestas.

3) Para cada vértice, faça seu indegree igual ao seu outdegree.

4) Agora existe um circuito euleriano no gráfico. Encontre.

5) Agora, no gráfico restante (o gráfico original wrt encontra a trilha mais longa com o primeiro vértice no componente fortemente conectado escolhido. Eu acho que isso é NP difícil.

6) Inclua a trilha acima no circuito eleriano, convertendo o circuito euleriano em trilha.

Por que - eu aceito que essa pergunta provavelmente é NP difícil (acho, não matematicamente falando). Mas a abordagem acima funciona melhor quando existe uma lista longa (mais de 1000) de palavras distribuídas uniformemente (ou seja, não se destina a ser wc para a abordagem acima). Vamos supor que, depois de converter a lista fornecida no gráfico mencionado acima, felizmente se torne um gráfico euleriano (consulte http://en.wikipedia.org/wiki/Eulerian_path para obter condições), sem dúvida, podemos dizer essa resposta a pergunta acima é P e, na verdade, é o caminho euleriano no gráfico (consulte http://www.graph-magics.com/articles/euler.php para obter uma abordagem muito simples de fazê-lo e verifique isso para verificar se o seu gráfico tem único http://www.geeksforgeeks.org/strongly-connected-components/e se não estiver temporariamente limpo outro scc pequeno, pois existe um caminho euleriano para scc único). Assim, para casos sem sorte (que são quase todos os casos), tento convertê-los em casos com sorte (ou seja, a condição de trilha euleriana é cumprida). Como fazer isso? Tentei fazer uma pesquisa de profundidade crescente por arestas irrelevantes (o conjunto de arestas em um caminho que começa no vértice com grau de grau maior que indegree e termina no vértice com grau de grau indiferente). Aumentar a pesquisa em profundidade significa que primeiro eu procurei por todo esse conjunto de uma aresta no caminho do que duas arestas no caminho e assim por diante. Pode parecer, à primeira vista, que a pesquisa com profundidade levaria O (nós ^ i), portanto, a complexidade total do tempo de O (nós + nós ^ 2 + nós ^ 3 + ....) até que seja um caso de sorte. Mas a análise amortizada revelará que é O (arestas). Uma vez que é reduzido caso sorte encontrar circuito euleriano.

Até aqui era tempo polinomial. Isso daria quase a melhor solução. Mas, para aumentar ainda mais sua solução (a solução perfeita é difícil para o NP), tente uma abordagem gananciosa no gráfico restante para encontrar uma longa trilha olhando com um dos vértices no scc escolhido. Agora adicione isso à trilha euleriana acima encontrada para aumentá-la ainda mais.

Idéia:

Primeiro, crie dois mapas (hashes), digamos S e E, das letras do alfabeto às palavras; o primeiro, S, mapeia as letras iniciais das palavras, o segundo, E, faz o mesmo com as letras finais.

Por exemplo, se o dicionário for feito de:

pássaro, prato, cachorro, harb

temos:

S:

a -> [ ]
b -> [ bird ]
c -> [ ]
d -> [ dish, dog ]
...
h -> [ harb ]
...

e,

E:

a -> [ ]
b -> [ harb ]
c -> [ ]
d -> [ bird ]
...
g -> [ dog ]
h -> [ dish ]
...

Em seguida, usando S e E para pesquisas rápidas, crie uma floresta (conjunto de árvores), do mesmo tamanho do dicionário, com raízes em cada palavra e não permitindo que uma palavra apareça mais de uma vez em uma árvore - armazene em cache o profundidades das árvores conforme você as constrói:

bird (depth: 2)
   dish
      harb
   dog

dish (depth: 3)
   harb
      bird
         dog

dog (depth: 0)

harb (depth: 2)
   bird
      dish
      dog

Por fim, percorra a floresta e encontre as árvores com maior profundidade.

As soluções estarão no eixo descendente dessas árvores.

Por exemplo,

dish / harb / bird / dog

acima.