pdp forum

Προσπαθώ να φτιάξω ένα πρόγραμμα που να λύνει το γνωστό n-puzzle(http://en.wikipedia.org/wiki/Fifteen_puzzle)
Ο κώδικας μου ειναι ο εξής:
[pastebin]http://pastebin.com/pU2j9hGK[/pastebin]
Στην αρχή ζητάει από τον χρηστη την πλευρά του τετραγωνου και το puzzle μπερδεμένο και του εμφανίζει μετά από πόσες κινησεις είναι δυνατό να λυθεί και ποιες κινήσεις πρέπει να γίνουν. Χρησιμοποιώ τον αλγοριθμο BFS.

Το πρώβλημα ειναι πως πολύ συχνα κατα την επήλυση του puzzle αυτό ξαναπέρνει μια μορφή που την είχε παρει και νωριτερα και ετσι γεμίζει η ουρά με στοιχεία που δεν χρειάζονται.

Σκέφτηκα να χρησιμοποιήσω ένα set στο οποίο θα κρατώ κάθε μοναδική κατασταση από την οποία πέρασα για να μήν ξαναπάω στη ίδια. Δεν ξέρω όμως πως μπορώ να υλοποιήσω κάτι τέτοιο.
Μήπως μπορεί να με βοηθίσει κάποιος?

I.M.O. Θα μπορούσες να αναπτύξεις μια συνάρτηση hash, η οποία θα κωδικοποιούσε το κάθε σου state πχ. σε έναν μοναδικό ακέραιο, τον οποίο θα μπορούσες να σημείωνες με τη βοήθεια ενός map λ.χ. ως visited κάθε φορά που το επισκεπτόσουν, κι έτσι να μην έκανες τον κόπο να το ξαναπερνούσες στην ουρά.

thetrojan01 έγραψε:I.M.O. Θα μπορούσες να αναπτύξεις μια συνάρτηση hash, η οποία θα κωδικοποιούσε το κάθε σου state πχ. σε έναν μοναδικό ακέραιο, τον οποίο θα μπορούσες να σημείωνες με τη βοήθεια ενός map λ.χ. ως visited κάθε φορά που το επισκεπτόσουν, κι έτσι να μην έκανες τον κόπο να το ξαναπερνούσες στην ουρά.

Σε ευχαριστώ trojan. Πολύ καλή η ιδέα σου.
Στον κώδικα μου πρόσθεσα αυτη τη συναστιση hash και τώρα φαίνεται να δουλεύει καλά.
[pastebin]http://pastebin.com/B3uZFngx[/pastebin]
Δεν χρησιμοποίησα όμως map. Σκέφτηκα κάθε μοναδική τιμή που πέρνω από αυτή να την έχω σε ένα set και έτσι κάθε φορα ελέγχω αν υπάρχει ήδη στο set αλλιώς την εισάγω.

Μήπως ξέρει κανείς πως μπορώ σε ένα set να κρατώ έναν δικό μου τυπο δεδωμένων που δημιούργισα από struct?

Δες εδώ
http://cboard.cprogramming.com/cplusplu ... ructs.html

το set της STL είναι ουσιαστικά μια τάξη-πρότυπο, άρα μπορείς να ορίσεις ένα αντικείμενο ως (αν και για την επιστροφή της hash σου αρκεί απλά ένα set<int>)

Αλλά θα πρέπει επίσης ή να υπερφορτώσεις τον τελεστή < , ή να κάνεις κάτι ώστε να δείξεις στο set πώς να συγκρίνει τις τιμές για να δει ποια είναι μικρότερη. Όπως λέει και στη σελίδα που σου υπέδειξε ο sotiris.

Αν θυμάμαι καλά τις πολυπλοκότητες, το map είναι γρηγορότερο απ' ό,τι το set.

ΥΓ. Επίσης, πιστεύω θα ήταν καλύτερα την hash να την όριζες ως:

Κάν'το με στυλ και υλοποίησε κατακερματισμό 1:1 βάζοντας ως διακριτική τιμή των στοιχείων του set τον αύξοντα αριθμό της διάταξης. Μετά πρόσθεσε στην κλάση κατάστασης τον αύξοντα αριθμό της διάταξης της προηγούμενης, και είσαι άρχοντας.

Πώς να το λύσαν αυτό το 1991 σε ΙΟΙ, μη με ρωτάς, δεν έχω ιδέα.