n-puzzle solver

Ο τομέας μας. ;)
Απάντηση
bour1992
Δημοσιεύσεις: 55
Εγγραφή: Πέμ Δεκ 18, 2008 1:50 pm

n-puzzle solver

Δημοσίευση από bour1992 » Δευ Αύγ 23, 2010 10:41 pm

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

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

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

Άβαταρ μέλους
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Τοποθεσία: Ρόδος
Επικοινωνία:

Re: n-puzzle solver

Δημοσίευση από thetrojan01 » Τρί Αύγ 24, 2010 3:21 am

I.M.O. Θα μπορούσες να αναπτύξεις μια συνάρτηση hash, η οποία θα κωδικοποιούσε το κάθε σου state πχ. σε έναν μοναδικό ακέραιο, τον οποίο θα μπορούσες να σημείωνες με τη βοήθεια ενός map λ.χ. ως visited κάθε φορά που το επισκεπτόσουν, κι έτσι να μην έκανες τον κόπο να το ξαναπερνούσες στην ουρά.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.

bour1992
Δημοσιεύσεις: 55
Εγγραφή: Πέμ Δεκ 18, 2008 1:50 pm

Re: n-puzzle solver

Δημοσίευση από bour1992 » Τρί Αύγ 24, 2010 11:16 am

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

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

sotiris
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: n-puzzle solver

Δημοσίευση από sotiris » Τρί Αύγ 24, 2010 1:15 pm

Εικόνα

Άβαταρ μέλους
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Τοποθεσία: Ρόδος
Επικοινωνία:

Re: n-puzzle solver

Δημοσίευση από thetrojan01 » Τρί Αύγ 24, 2010 2:38 pm

το set της STL είναι ουσιαστικά μια τάξη-πρότυπο, άρα μπορείς να ορίσεις ένα αντικείμενο ως

Κώδικας: Επιλογή όλων

set<mystruct_t> set; // set<puzzle> visited; for example.  
(αν και για την επιστροφή της hash σου αρκεί απλά ένα set<int>)

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

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

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

Κώδικας: Επιλογή όλων

int hash(square& x,int yk); 
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: n-puzzle solver

Δημοσίευση από kernelpanic » Τετ Σεπ 01, 2010 12:55 pm

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

Πώς να το λύσαν αυτό το 1991 σε ΙΟΙ, μη με ρωτάς, δεν έχω ιδέα. :P
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.

Απάντηση