Shortest path finding algorithms.

[kaliakman]

Καλησπέρα, αρχικά να πω πως ο σκοπός είναι να βρεθεί ο πιο γρήγορος τρόπος γιατί θα τρέξει Πολλές φορες.

Έχουμε έναν πίνακα 9χ9 και ξεκινάμε από την 1 γραμμή. Θέλουμε να δούμε αν μπορεί να φτάσει απέναντι ο παίχτης (σε κάποια τετράγωνα δεν μπορεί να πάει για αυτό και ο ελεγχος).

 

Αφού το εψαξα αρκετά έχω βρει τον djikstra και την bfs. Με αυτά που διάβασα προτίμησα το δεύτερο λόγω της πολυπλοκοτητας χρόνου Ο(E + V). Το θέμα είναι ότι δεν μπόρεσα να βρω χρόνο για τον πρώτο εκτός από το worst case performance της Wikipedia το οποίο όμως δεν είναι καθαρά για θέμα χρόνου.

Η ερώτηση: Είναι η επιλογή μου η βελτιστη ή χάνω κάτι?

 

Υ.Γ. Σε C ειναι και δεν μπορώ να δώσω κώδικα εδώ αν κάποιος θέλει, πμ.

Ευχαριστώ!!

[gon1332]

Όταν λες BFS εννοείς τη Breadth First Search (αναζήτηση κατά πλάτος); Αν ναι, τότε αυτό είναι απλά ένας τρόπος διαπέρασης ενός  γράφου. Ένας άλλος είναι ο Depth First Search (αναζήτηση κατά βάθος).

 

Τι γράφο έχεις; Κατευθυνόμενος, μη; Με βάρη, χωρίς; Δεν κατάλαβα τι ακριβώς ζητάς. Τι σημαίνει το "απέναντι";

Τον BFS θα τον χρησιμοποιήσεις μόνο αν ο γράφος σου δεν έχει βάρη στις ακμές. Όταν φτάσεις στον προορισμό σου, το μονοπάτι που έφτασε πρώτο είναι και το συντομότερο (όχι ότι δε θα υπάρχουν κι άλλα το ιδιο σύντομα).

 

Πάντως, αναλόγως με το πρόβλημά σου, επιλέγεις έναν από αυτούς:

https://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms

[AlexHello]

Ότι καλύτερο για games (A*)

[kaliakman]

Γράφους δεν έχω κάνει οπότε δεν μπορώ να σου απαντήσω.. Ότι βρήκα το βρήκα ψάχνοντας αυτό που ήθελα. Οι κινήσεις είναι να πάμε μπροστά πίσω δεξιά αριστερά σε κελί που επιτρέπεται οπότε η κάθε κίνηση έχει βάρος 1.από ότι διάβασα η bfs (breadth first search) είναι καλή όταν το node που θέλουμε είναι μακριά οπότε είναι και η καταλληλότερη όπως το βλέπω. Δεν με νοιάζει ποιο είναι το μονοπατι μου αρκεί αρχικά να μπορεί να φτάσει στο προορισμό του (άμα ξεκινάμε στο row 1 προορισμός είναι οποιοδήποτε κελί του rows -1)και μετά η απόσταση του από το αρχικό κελί που θα χρησιμοποιηθει για evaluation αλλού.

[groot]

Εάν έχεις συγκεκριμένες μεταβάσεις από ένα κελί σε ένα άλλο, τότε έχεις έναν κατευθυνόμενο γράφο (directed graph).

 

Καλύτερα να ψάξεις για αλγόριθμους διάσχησης γράφων.

[gon1332]

Για να καταλάβω, αυτός ο πίνακας, δεν είναι πίνακας γειτνίασης, ε;

 

Αν όχι τότε έχεις κάτι σαν ένα χάρτη, που σε κάθε κελί περιέχεται πληροφορία για το αν μπορείς να πατήσεις πάνω στο κελί ή όχι. Σωστά;