A* algorithm

[dinak]

Έχω μια σκακιέρα 8χ8 στην οποία θέλω να μετακινήσω το άλογο από μια συγκεκριμένη θέση σε μια άλλη με το ελάχιστο δυνατό αριθμό κινήσεων. Θέλω να χρησιμοποιήσω τον αλγόριθμο Α* αλλά δε μπορώ να βρω κατάλληλη h(n). Μπορεί να βοηθήσει κάποιος; (υποθέτουμε ότι δεν υπάρχουν άλλα πιόνια στην σκακιέρα)

[bnvdarklord]

Νομίζω η ευκλείδια απόσταση ποτέ δεν θα υπερεκτιμήσει οπότε σου κανει.

[dinak]

Νομίζω η ευκλείδια απόσταση ποτέ δεν θα υπερεκτιμήσει οπότε σου κανει.

 

το δοκίμασα...αλλά εάν από το 0,0 θέλω να πάω στο 7,7 ο αριθμός κινήσεων ειναι 6...και η ευκλείδια βγαίνει 9,κάτι

[bnvdarklord]

Mμμ οντως εφόσον μια κίνηση αλόγου = παραπάνω απο ενα κουτάκι.

 

Μια ιδέα που είχα:

Βρες την ευκλείδια απόσταση μεταξύ αρχικού και τελικού σημείου της μίας κίνησης του αλόγου εστω Εstep. Αν ΕDist η ευκλείδια μεταξύ δύο σημείων μπορεις να έχεις ως h(x) = EDist / Estep. Σαν να εχεις την απόσταση που κανει κατα ενα step ως μονάδα μέτρησης.

Αν υπολόγισα σωστά ΕStep = 2.2 οπότε στο παράδειγμα σου θα υπολόγιζε περίπου 4 κινησεις.

[smilefreeware]

Η αρχική θέση είναι 0

Τα 1 είναι με μια κίνηση, τα 2 με 2 κινήσεις κλπ.

Νομίζω μελετώντας το παράδειγμα θα βγάλεις άκρη.(Πιθανώς βάζοντας και άλλα νούμερα)

Λόγω νύστας, μέχρι εδώ έφτασα.

 

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . 2 3 2 . . .

. . . . 4 1 2 1 4 3 . . .

. . . . 1 2 3 2 1 . . . .

. . . . 2 3 0 3 2 . . . .

. . . . 1 2 3 2 1 . . . .

. . . . . 1 2 1 . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

[bnvdarklord]

^Ευρεστική για τον Α* ζήτησε βασικά.

[soulcon]

Δες εδώ http://www.policyalmanac.org/games/aStarTutorial.htm

[dinak]

@bnvdarklord καλό ακούγεται αυτό με την διαίρεση, θα το δοκιμάσω.

 

@soulcon το έχω διαβάσει το συγκεκριμένο tutorial και πολλά άλλα...αλλά τα περισσότερα μιλάνε για κίνηση κατά ένα κουτάκι!η κίνηση του αλόγου είναι που δυσκολεύει!

[dinak]

Mμμ οντως εφόσον μια κίνηση αλόγου = παραπάνω απο ενα κουτάκι.

 

Μια ιδέα που είχα:

Βρες την ευκλείδια απόσταση μεταξύ αρχικού και τελικού σημείου της μίας κίνησης του αλόγου εστω Εstep. Αν ΕDist η ευκλείδια μεταξύ δύο σημείων μπορεις να έχεις ως h(x) = EDist / Estep. Σαν να εχεις την απόσταση που κανει κατα ενα step ως μονάδα μέτρησης.

Αν υπολόγισα σωστά ΕStep = 2.2 οπότε στο παράδειγμα σου θα υπολόγιζε περίπου 4 κινησεις.

 

 

τελικά ούτε αυτό μπορεί να χρησιμοποιηθεί...αν θέλω να πάω από το 3,4 στο 2,3 ο ελάχιστος αριθμός είναι 2 κινήσεις (3,4 -> 1,5 -> 2,3)..αν χρησιμοποιήσω το πηλίκο αυτό για την h, στο 1,3 θα έχω 0,64 και στο 1,5 θα έχω 1,01...οπότε το επόμενο σημείο που θα επιλεχθεί θα είναι το 1,3 που δεν είναι σωστό :/

[bnvdarklord]

Το ψαξα λίγο και βρήκα για την λεγόμενη Warnsdorf's heuristic η οποία χρησιμοποιείται στο horse tour problem και λεει οτι επιλέγεις την θέση η οποία έχει τις λιγότερες κάθε φορά επόμενες κινήσεις. Δοκίμασε το, ή και ψάξε παραπάνω.

[Directx]

Το ψαξα λίγο και βρήκα για την λεγόμενη Warnsdorf's heuristic η οποία χρησιμοποιείται στο horse tour problem και λεει οτι επιλέγεις την θέση η οποία έχει τις λιγότερες κάθε φορά επόμενες κινήσεις. Δοκίμασε το, ή και ψάξε παραπάνω.

Χμ.. πριν καιρό είχα γράψει μια υλοποίηση Warnsdorff’s Knight’s tour σε C++ εξ' αφορμής μιας παλαιότερη συζήτησης όπου υπάρχουν δημοσιευμένες και άλλες υλοποιήσεις (σε C).

[dinak]

τον έχω δει κ αυτόν τον αλγόριθμο...αλλά και πάλι δε βολεύει...γιατι εάν είμαι στο κέντρο κάθε πιθανή θέση μετακίνησης έχει τον ίδιο βαθμό (οπότε και το ίδιο h(n))...άρα η επιλογή της επόμενης κίνησης θα μπορούσε εύκολα να είναι μια θέση που δεν μου δίνει τον ελάχιστο αριθμό κινήσεων από το τέλος

[bnvdarklord]

Ναι αλλα ο Α* θα το καταλάβει και θα γυρίσει πίσω αν χρειαστεί.

[soulcon]

Τελικά βρήκες την λύση;