Salve a tutti e buon Anno nuovo!
Mi viene posto un problema, del quale a me manca proprio l'idea "concettuale" di come si faccia:
è il problema dei Catenyms, che altro non significa che, data una serie di parole, devo restituire una "catena" di queste parole in modo da usarle tutte (e una sola volta), e tale per cui l'ultima lettera della prima sia la stessa iniziale della successiva: esempio (così è chiaro la stupidata che è):
Parole date:
aloha
arachnid
dog
gopher
rat
tiger
Risultato che devo dare: (non è detto che sia l'unico, basta sia uno giusto)
aloha.arachnid.dog.gopher.rat.tiger
[E dire, se caso, se una sequenza tale non esiste, cioè è impossibile formarla...]
La mia idea era di strutturare tutto con un grafico, così che i Nodi sono le lettere, e i lati (orientati ->) sono le parole che li hanno agli estremi: il problema si riduce a: esiste un percorso che tocca TUTTI I LATI e non ripassa mai due volte dallo stesso lato?
(Credo esistano già algoritmi per questo nella teoria dei Grafi, ma fra i tanti che ho visti, il trovare un percorso che tocchi ogni lato non l'ho ancora fatto, e cercando non sono riuscito a trovare nulla...).
(Per chi sapesse cos'è, ho già implementato l'Algoritmo di Kruskal in C++ e funziona bene, casomai servisse...)
Qualcuno mi da una (o anche due) mano?
Thx!
Rispondi quotando
