Πρόβλημα αναζήτησης

Στη θεωρία υπολογιστικής πολυπλοκότητας και τη θεωρία υπολογισιμότητας, ένα πρόβλημα αναζήτησης είναι ένα είδος υπολογιστικού προβλήματος που αναπαριστάται από μια δυαδική σχέση. Αν το R είναι μια δυαδική σχέση τέτοια ώστε field(R) ⊆ Γ+ και το T είναι μια μηχανή Turing, τότε το T υπολογίζει το R εάν:
 Έστω ότι το x είναι τέτοιο ώστε να υπάρχει κάποιο y όπου R(x,y). Τότε το Τ αποδέχεται x με έξοδο z τέτοια ώστε R(x,z) (μπορεί να υπάρχουν πολλαπλά y, αλλά το Τ χρειάζεται να βρει μόνο ένα από αυτά)
 Έστω ότι το x είναι τέτοιο ώστε δεν υπάρχει κανένα y όπου R(x,y). Τότε το Τ απορρίπτει το x
Διαισθητικά, το πρόβλημα έγκειται στην εξεύρεση κάποιας δομής "y" στο αντικείμενο "x". Λέμε ότι ένας αλγόριθμος επιλύει το πρόβλημα αν υπάρχει τουλάχιστον μια τέτοια δομή και ο αλγόριθμος μπορεί τελικά να μας δώσει στην έξοδό του μια από αυτές. Διαφορετικά ο αλγόριθμος σταματά με κατάλληλο μήνυμα ("Το αντικείμενο δε βρέθηκε" ή κάτι παρόμοιο).

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

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

Μια σχέση R μπορεί να θεωρηθεί ως ένα πρόβλημα αναζήτησης και μια μηχανή Turing που υπολογίζει την R λέμε επίσης ότι μπορεί και να την επιλύσει. Κάθε πρόβλημα αναζήτησης αντιστοιχεί σε ένα πρόβλημα απόφασης, και συγκεκριμένα:

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

 Ορισμός 
Ένα πρόβλημα αναζήτησης ορίζεται από:
 Ένα σύνολο καταστάσεων
 Μια κατάσταση εκκίνησης
 Μια κατάσταση στόχο ή δοκιμή στόχο
 μια boolean συνάρτηση που μας λέει αν μια δεδομένη κατάσταση είναι μια κατάσταση στόχου
 Μια συνάρτηση απαρίθμησης
 μια αντιστοίχιση από κάποια κατάσταση σε ένα σύνολο επόμενων καταστάσεων

 Μέθοδος αναζήτησης 
 Γενικός αλγόριθμος αναζήτησης: δίνονται ένας γράφος, κόμβοι εκκίνησης και κόμβοι στόχου. Να ερευνηθούν σταδιακά τα μονοπάτια από τους κόμβους εκκίνησης.
 Διατήρησε ένα σύνορο με τα μονοπάτια από τον κόμβο εκκίνησης που έχουν ερευνηθεί.
 Καθώς προχωρά η αναζήτηση, το σύνορο επεκτείνεται σε μη εξερευνημένους κόμβους μέχρι να συναντηθεί ένας κόμβος στόχου.
 Ο τρόπος με τον οποίο επεκτείνεται το σύνορο ορίζει τη στρατηγική αναζήτησης. 
    Είσοδος: ένας γράφος,
        ένα σύνολο κόμβων εκκίνησης,
        Boolean διαδικασία goal(n) που ελέγχει αν το n είναι κόμβος στόχου.
    σύνορο:= {s : s είναι κόμβος εκκίνησης};
    Όσο το σύνορο δεν είναι κενό:
        επίλεξε και αφαίρεσε μονοπάτι <n0, ..., nk> από το σύνορο
        Αν goal(nk)
            επίστρεψε <n0, ..., nk>
        Για κάθε γείτονα n του nk
            πρόσθεσε το <n0, ..., nk, n> στο σύνορο
    τέλος επανάληψης

 Αναφορές 
Το άρθρο αυτό ενσωματώνει υλικό από το λήμμα search problem του PlanetMath, το οποίο υπόκειται στην άδεια Creative Commons Attribution/Share-Alike License.

Κατηγορία:Μαθηματικά προβλήματα
Κατηγορία:Θεωρία υπολογισμού