la più lunga lista di parole con lettere iniziali e finali corrispondenti

Penso che questo sia collegato al problema del percorso più lungo (LP) che hai menzionato, ma è un po 'diverso. La differenza principale è che il problema dell'LP ha un grado di connettività superiore a quello che fa il problema suggerito. Limitando le tue connessioni all'ultima e alla prima lettera, rimuovi un gran numero di potenziali combinazioni.

Ecco come suggerirei di affrontare questo:

1. Per ogni parola nell'elenco, conta le connessioni possibili e le connessioni.
2. Elimina le parole che contengono 0 in e 0 in uscita.
3. Identifica un set iniziale di "parole di partenza" con i numeri più bassi di angoli di campo e i valori più bassi devono essere maggiori di 0.
4. Ogni parola di avviamento riceve la propria copia di lavoro del numero di connessioni in entrata / uscita. Questo forma la testa della catena.
5. Per ogni catena, identifica un elenco di "parole successive" basato su:
   
   • ultima lettera di avvio o parola precedente
   • numero più basso di connessioni in entrata e in uscita (anche in questo caso i outs devono essere maggiori di 0)
6. Per ogni next word , ripeti il passaggio 5 finché la catena non termina.

Ricorda che:

• Dovrai tenere traccia della lunghezza delle catene e disporre di un meccanismo globale per identificare la catena più lunga.

• Dovrai inoltre rimuovere ogni parola dalla copia di lavoro dei conteggi delle connessioni per evitare un ciclo ricorsivo.

• Ad un certo punto, la catena si interromperà e dovrai selezionare una parola con un conteggio di 0 out.

• Potrebbe essere necessario ricalcolare gli elementi esterni quando le parole vengono rimosse dagli elenchi di lavoro. A prima vista, non penso che questo sarà necessario in quanto i set complessivi saranno relativamente piccoli. Se riduci a 1000 parole, il conteggio statico potrebbe rallentare la convergenza dell'algoritmo.

Ho visto questo come un problema di imballaggio. Per me, le connessioni in entrata e in uscita identificano la forma da imballare. Più basse sono le connessioni, più dispari è la forma. Più la forma è dispari, prima voglio comprimerla perché ho percepito una diminuzione delle probabilità di riuscire a impacchettare una forma strana più tardi sono entrato nella catena.

Ad esempio:

{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 crei una matrice 26X26 per rappresentare il grafico diretto del vertice come ogni alfabeto e parole come bordo. Ad esempio word - APPLE connette il vertice A ed E con lo spigolo diretto da A a E. Ora il problema si riduce alla ricerca della più grande traiettoria Euleriana (percorso che include il numero massimo di bordi, visitando ogni spigolo una volta che è possibile la ripetizione dei vertici) nel grafico. Uno degli algoritmi O (E) sarebbe quello di iniziare in modo casuale da una coppia di vertici. Trova un percorso tra di loro. Quindi continua a rilassare il percorso finché è possibile.

Aggiorna @ GlenH7 Ho risolto una domanda simile su www.hackerearth / jda di recente, c'erano dei voti relativi rispetto alla soluzione migliore e ho ottenuto il punteggio più alto con il seguente approccio -

Fornito un elenco di parole. Trova la catena più lunga che può essere formata da loro. Una catena è valida se ogni parola inizia con una lettera * che termina alla fine dell'ultima parola.

Approch =

1) crea il grafico degli alfabeti come vertici e parole come bordi.   Al posto di utilizzare più spigoli, utilizzare uno con un peso uguale a   numero di bordi.

2) trova la componente strongmente connessa del grafico con   bordi massimi. Scarta temporaneamente altri bordi.

3) Per ogni vertice rendi il suo indice uguale al suo outdegree.

4) Ora il loro circuito euleriano esiste nel grafico. Trovalo.

5) Ora nel grafico rimanente (il grafico originale w.r.t trova il più lungo   sentiero con primo vertice in scelto strongmente connesso   componente. Penso che questo sia NP difficile.

6) Includere la traccia di cui sopra nel circuito eleriano che converte l'euleriano   circuito in pista.

Perché - Accetto che questa domanda sia molto probabilmente NP (suppongo, non matematicamente parlando). Ma l'approccio di cui sopra funziona meglio quando c'è una lunga lista (1000+) di parole uniformemente distribuite (cioè non inteso per essere w.c. per l'approccio sopra). Supponiamo che dopo aver convertito una lista data in un grafico sopra menzionato, per fortuna si rivelerà un grafico euleriano (vedi link per condizioni), quindi senza alcun dubbio possiamo dire che la risposta alla domanda precedente è P ed è in realtà il percorso euleriano nel grafico (vedi link per un approccio molto semplice e vedi questo per verificare che il tuo grafico abbia un singolo link e se non pulisce temporaneamente altri piccoli scc perché esiste un percorso euleriano per single scc). Quindi per i casi non fortunati (che sono quasi tutti i casi) cerco di convertirli in casi fortunati (vale a dire che le condizioni del sentiero euleriano sono soddisfatte). Come fare questo? Ho provato ad aumentare la profondità di ricerca per i bordi irrilevanti (l'insieme di spigoli in un percorso che guarda dal vertice con outdegree maggiore di un indegree e termina al vertice con un indice maggiore rispetto ad un altro). Aumentare la profondità di ricerca significa che per prima cosa ho cercato tutti questi set di un bordo in un percorso rispetto a due bordi nel percorso e così via. Può sembrare a prima vista che con la ricerca di profondità occorrerebbe O (nodi ^ i) quindi la complessità temporale totale di O (nodi + nodi ^ 2 + nodi ^ 3 + ....) finché non si tratta di un caso fortunato. Ma l'analisi ammortizzata rivelerà che è O (bordi). Una volta ridotto il caso fortunato, trova il circuito euleriano.

Fino a qui era tutto il tempo polinomiale. Questo darebbe quasi la soluzione migliore. Ma per aumentare ulteriormente la tua soluzione (la soluzione perfetta è NP difficile) prova un approccio avido nel grafico rimanente per trovare una lunga traccia che fissa con uno dei vertici nello scc scelto. Ora aggiungilo al tracciato euleriano sopra riportato per aumentarlo ulteriormente.

Idea:

Per prima cosa, crea due mappe (hash), ad esempio S ed E, dalle lettere dell'alfabeto alle parole; il primo, S, le mappe che iniziano le lettere alle parole, il secondo, E, fa lo stesso con le lettere finali.

Ad esempio, se il dizionario è composto da:

uccello, piatto, cane, harb

abbiamo:

S:

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

e

E:

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

Quindi, usando S ed E per ricerche veloci, crea una foresta (set di alberi), delle stesse dimensioni del dizionario, con radici su ogni parola e non permettendo che una parola appaia più di una volta in un albero - - Memorizza nella cache le profondità degli alberi mentre le costruisci:

bird (depth: 2)
   dish
      harb
   dog

dish (depth: 3)
   harb
      bird
         dog

dog (depth: 0)

harb (depth: 2)
   bird
      dish
      dog

Infine, esegui un'iterazione sulla foresta e trova gli alberi di maggiore profondità.

Le soluzioni saranno sull'asse discendente di quegli alberi.

per es.,

dish / harb / bird / dog

sopra.