Αλγόριθμοι απληροφόρητης (ή τυφλής) αναζήτησης

[voulaji]

Θα ήθελα την βοήθειά σας, στο εξής πρόβλημα:

Θέλω ένα πρόγραμμα που να λύνει προβλήματα (Ν2-1)παζλ με τους αλγορίθμους πρώτα σε πλάτος (breadth-first search) και πρώτα σε βάθος (depth-first search). Το πρόγραμμα θα δέχεται ως παραμέτρους τη μέθοδο επίλυσης, το όνομα του αρχείου περιγραφής του προβλήματος και το όνομα του αρχείου στο οποίο θα γραφεί η λύση. Για παράδειγμα, εάν το όνομα του προγράμματός σας είναι puzzle.exe (μπορείτε φυσικά να το ονομάσετε όπως αλλιώς θέλετε), θέλετε να χρησιμοποιήσετε αναζήτηση κατά πλάτος, το αρχείο εισόδου είναι το input.txt και θέλετε η λύση να γραφεί στο αρχείο solution.txt, θα πρέπει να καλέσετε το πρόγραμμά σας με την εντολή:

puzzle.exe breadth input.txt solution.txt

Εάν αντίθετα θέλετε να χρησιμοποιήσετε τον αλγόριθμο πρώτα σε βάθος, χρησιμοποιείστε τη λέξη depth αντί της λέξης breadth στην παραπάνω κλήση.

Σε σχέση με το αρχείο εισόδου input.txt, έστω ότι Ν=3 και ότι θέλουμε να λύσουμε το πρόβλημα του αρχικού παραδείγματος. Τα περιεχόμενα του αρχείου εισόδου πρέπει να είναι τα εξής:

4 1 3

2 0 6

7 5 8

Σημειώστε ότι στην παραπάνω γραμμογράφηση οι αριθμοί της ίδιας σειράς διαχωρίζονται με tab.

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

6

left

up

right

down

down

right

όπου στην πρώτη γραμμή αναγράφεται το πλήθος των κινήσεων, ενώ οι λέξεις up, down, left και right προσδιορίζουν την εκάστοτε μετακίνηση της κενής θέσης.

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

[gagvas]

Ακόμα δουλεύει ο κόσμος blind-search αλγορίθμους;

Ρίξε μια ματιά σε αυτό, έχει και κώδικες.

http://en.wikipedia.org/wiki/Breadth-first_search

 

Πρόσεξε επίσης ο αλγόριθμος σου (αν γίνεται) να μην είναι recursive γιατί θα φας ένα ωραίο "stack overflow".

Επίσης, νομίζω ότι χρειάζεσαι τις iterative εκδόσεις αυτών των αλγορίθμων γιατί δεν γνωρίζεις εκ των προτέρων το βάθος του graph (δηλαδή τον αριθμό κινήσεων), βλέπε http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search

[voulaji]

Το είδα αυτό που μου έστειλες αλλά δεν βοηθά την περίπτωσή μου.

Η δική μου άσκηση είναι πιο πολύπλοκη και με συγκεκριμένα ζητούμενα.

Σε ευχαριστώ πάντως.