[Java] Aiuto su un algoritmo

[mistergks]

Ciao a tutti!
sto studiando per un esame di algoritmi e strutture dati.
Avrei bisogno di un consiglio su come approcciarmi a un esercizio.
Il linguaggio da utilizzare è il Java e si possono utilizzare tutte le librerie che si vuole, purchè funzioni bene con tutti i casi di input oltre a quelli dell'esempio. Voi come lo risolvereste?
Ovviamente non chiedo la soluzione, ma vorrei capire qual'è il metodo più corretto per risolverlo nel migliore dei modi.


http://i65.tinypic.com/2e4bvxk.png

[sottovento]

Io costruirei un grafo in cui ogni nodo contiene una parola. Il nodo adiacente al nodo attuale ha una sola lettera che varia.
Non dovrebbe essere difficile costruire un simile grafo.
Si tratta poi di percorrere il grafo dalla parola di partenza a quella di arrivo

[Kaya]

Concordo sull'idea del grafo, si tratta di un grafo orientato non pesato.
Si tratta di trovare un cammino minimo tra i due nodi (Djstrka?)

[sottovento]

Concordo sull'idea del grafo, si tratta di un grafo orientato non pesato.
Si tratta di trovare un cammino minimo tra i due nodi (Djstrka?)

Esatto. Ci sono anche altri algoritmi:
https://it.wikipedia.org/wiki/Cammino_minimo

In alternativa, si puo' rappresentare il grafo in maniera tabellare (tabella di interi), mettendo i noti di partenza in riga e di arrivo in colonna (o viceversa se si preferisce); poi si mettera' un 1 in questo caso se si puo' andare dal nodo di partenza a quello di arrivo. In questo caso il percorso non e' a senso unico visto che si puo' andare anche a ritroso (i.e. da CASA posso andare a CARA e viceversa), quindi la matrice sara' simmetrica rispetto alla diagonale principale.
Questione di gusti

[Kaya]

Esatto. Ci sono anche altri algoritmi:
https://it.wikipedia.org/wiki/Cammino_minimo

In alternativa, si puo' rappresentare il grafo in maniera tabellare (tabella di interi), mettendo i noti di partenza in riga e di arrivo in colonna (o viceversa se si preferisce); poi si mettera' un 1 in questo caso se si puo' andare dal nodo di partenza a quello di arrivo. In questo caso il percorso non e' a senso unico visto che si puo' andare anche a ritroso (i.e. da CASA posso andare a CARA e viceversa), quindi la matrice sara' simmetrica rispetto alla diagonale principale.
Questione di gusti

Credo che invece sia più opportuno considerare un cammino orientato.

Facciamo ipotesi che devo andare da CARA a CASO: CARA->CASA->CASO
Nel mio grafo non avrò mai necessità di tornare indietro e quindi mettere un orientamento (vado a memoria) dovrebbe ridurre la complessità computazionale (diciamo che dovremmo stare al di sotto del caso peggiore O(n^2) ) [ripeto vado un po a memoria e non ho fatto conti]

[eliano]

Costruisci un albero n-ario nel quale ad ogni livello corrisponde la successiva lettera della parola:
liv.1 - 1a lettera
liv.2 - 2a lettera
...
liv.n - ultima lettera della/e parola/e più lunga/he
La radice dell'albero sarà un nodo fittizio.
Ogni nodo contiene puntatori ad altri contenenti la possibile lettera successiva o un puntatore nullo se il dizionario non contiene una parola che contenga quella lettera.
Discendendo l'albero fino a trovare la parola p2, dovresti percorrere il cammino minimo.
Se n è il numero di livelli, dovrebbe avere complessità spaziale 26^n e O(n) nel caso limite che il dizionario contenga tutte le possibili sequenze di n caratteri.