Θα τον βρω το δρόμο

[αρψ2400]

Πόσες διαφορετικές διαδρομές μήκους από τον κόμβο στον κόμβο υπάρχουν;

(ένα όχι πρωτότυπο θέμα , με έναν εύκολο γραμμικό αλγόριθμο)

[abgd]

diadromes.png (23.07 KiB) Προβλήθηκε 143 φορές

Αν θα είναι

Για να πάμε από το στο ακολουθώντας μια διαδρομή μήκους θα πρέπει να κινηθούμε "δεξιά" και "πάνω"

Έτσι αποκλείουμε όλους τους κόμβους όπου είμαστε αναγκασμένοι να κινηθούμε "αριστερά" και "κάτω" , σημειώνοντάς τους με κόκκινο χρώμα και αρχίζοντας από τον κόμβο .

Εύκολα τώρα βλέπουμε τις διαδρομές που μπορούμε να ακολουθήσουμε. Σύνολο: 5 διαδρομές.

[αρψ2400]

diadromes.png

Αν θα είναι

Για να πάμε από το στο ακολουθώντας μια διαδρομή μήκους θα πρέπει να κινηθούμε "δεξιά" και "πάνω"

Έτσι αποκλείουμε όλους τους κόμβους όπου είμαστε αναγκασμένοι να κινηθούμε "αριστερά" και "κάτω" , σημειώνοντάς τους με κόκκινο χρώμα και αρχίζοντας από τον κόμβο .

Εύκολα τώρα βλέπουμε τις διαδρομές που μπορούμε να ακολουθήσουμε. Σύνολο: 5 διαδρομές.

Έχετετε παραλείψει μία ακμή από το αρχικό γράφημα .Η απάντησή σας για το τροποποιημένο γράφημα είναι σωστή και η λύση σας μας γλιτώνει αρκετούς κόμβους μειώνοντας την αναζήτηση διαδρομών. Γράφετε όμως 'Εύκολα τώρα βλέπουμε τις διαδρομές που μπορούμε να ακολουθήσουμε. Σύνολο: 5 διαδρομές.'
Οι διαδρομές όμως μπορεί να είναι πολλές και θέλουμε έναν αλγόριθμο υπολογισμού τους .Αυτός που έχω στο μυαλό μου (και είμαι σχεδόν σίγουρος ότι τον έχω δει κάπου όπως και το πρόβλημα) είναι:

Οι κινήσεις είναι υποχρεωτικά προς τα πάνω και προς τα δεξιά αφού ανεξαρτήτως σειράς θέλουμε 6 κινήσεις δεξιά και 4 κινήσεις προς τα πάνω , σύνολο 10 . Η τιμή σε κάθε κόμβο προκύπτει από το άθροισμα των διαδρομών του από κάτω και από αριστερά κόμβου, εφόσον υπάρχει η αντίστοιχη γραμμή σύνδεσης. Ξεκινάμε από κάτω αριστερά βάζοντας το 1 και κινούμαστε συμπληρώνοντας τους κόμβους από αριστερά προς τα δεξιά και από κάτω προς τα πάνω.

Δείτε το παρακάτω για παράδειγμα γράφημα που οι διαδρομές είναι πολλές

[abgd]

Είχα παραλείψει δύο ακμές με αποτέλεσμα να βρω λιγότερες κατά 3 τις διαδρομές.

Σύμφωνα με αυτά που περιγράφεις, εφόσον το κατάλαβα σωστά, ο αλγόριθμος έχει την εξής λογική:
Ξεκινώντας από το σημείο όπου αντιστοιχούμε τον αριθμό , σε κάθε επόμενο σημείο αντιστοιχούμε τον αριθμό που προκύπτει
προσθέτοντας τους αριθμούς των σημείων που βρίσκονται αριστερά και κάτω.
Ο αριθμός αυτός μας δείχνει το πλήθος των διαδρομών, με το μικρότερο μήκος, που πρέπει να ακολουθήσουμε για να βρεθούμε στο σημείο αυτό.

Καλό!

diadromes.png (30.48 KiB) Προβλήθηκε 51 φορές

Στο παραπάνω σχήμα ελπίζω να μην μου διέφυγε κάτι...

Σημείωση: Θα μπορούσε η εκφώνηση της άσκησης να είναι και η εξής: Ξεκινώντας από το σημείο με πόσους τρόπους μπορούμε να βρεθούμε σε κάποιο άλλο σημείο του σχήματος διανύοντας την μικρότερη απόσταση.