Perl - "attraversare" matrice

[gabmac2]

Come si possono stampare tutti i "percorsi" dalla cella 0,0 alla cella n-1,n-1 possibili di una matrice?
Grazie in anticipo

[Daniels118]

Cosa significa "tutti i percorsi"?

[gabmac2]

cella per cella, dalla 0,0 alla n-1,n-1

[Daniels118]

Ho appena riparato la mia sfera magica, vediamo se funziona...
per percorso intendi un array in cui ogni elemento contiene le coordinate di una cella della matrice, e la sequenza di elementi deve rappresentare le celle adiacenti che congiungono la cella (0,0) alla cella (n-1,n-1).
Ho capito bene?
Quando due celle si possono considerare adiacenti? Solo se si trovano sulla stessa riga o colonna, oppure anche in diagonale?
Ti interessano proprio tutti i percorsi? Anche se fanno degli inutili zig-zag avanti e indietro?

[gabmac2]

1 un passo a dx
1 un passo a sx
1 un passo in diagonale
solo in ordine crescente (riga o colonna, o entrambe cambiano ad ogni passo),senza tornare indietro inutilmente
dalla 0,0 alla n-1,n-1

[Daniels118]

Per "tornare indietro" non intendo passare due volte sulla stessa cella, ma spostarsi in una direzione che si allontana dalla destinazione.
E' importante definire questi particolari perché determinano profonde differenze nell'algoritmo (che comunque è assolutamente indipendente dal linguaggio perl).

[gabmac2]

certamente,
appunto per questo intendo in ordine dall' alto verso il basso
Ad ogni passo quindi i=i+1 (riga), j=j+1(colonna) o entrambi a differenza di dove si trova l' elemento minore
Però si potrebbe arrivare all' ultima riga e ,doversi spostare di un determinato numero di celle verso destra per raggiungere l' estremità della matrice
Questi passi potrebbero avere un costo grande, quindi invalidare il miglior percorso scelto in modo greedy fino a questo punto
In teoria servono tutti i percorsi e decidere il migliore

[Daniels118]

Ma non avevi detto che nella matrice c'erano i valori delle distanze!
La soluzione migliore si può ottenere solo provando tutti i precorsi. Puoi realizzare l'algoritmo sia in maniera iterativa che ricorsiva, quale preferisci?

[-MiStO-]

non ho ben capito...a te servono tutti i percorsi o solo il migliore?
perche ad un certo punto dici:

Questi passi potrebbero avere un costo grande, quindi invalidare il miglior percorso scelto in modo greedy fino a questo punto
In teoria servono tutti i percorsi e decidere il migliore

e mi fa pensare che tu cerchi semplicemente il migliore...

cmq brutalmente puoi provare con una ricerca in profondita on in ampiezza, o per qualcosa di un pelino + sofisticato un bel A-star (link (http://en.wikipedia.org/wiki/A*_search_algorithm))

[gabmac2]

il migliore però però a livello greedy è improbabile
basandosi solo sulla matrice cosa vi viene in mente?

[Daniels118]

Non è che la soluzione ad uno dei problemi più studiati al mondo ti "viene in mente" così, un qualunque pomeriggio di marzo... ci sono svariati algoritmi con diversi pregi e difetti, ma nessuno di essi riesce a trovare la soluzione migliore in un tempo lineare.

[gabmac2]

certamente,
ad esempio?

[Daniels118]

L'utente -MiStO- te ne ha già segnalato uno, trovi un elenco più ampio qui:
http://en.wikipedia.org/wiki/Shortest_path_problem