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

Στη θεωρία υπολογιστικής πολυπλοκότητας και τη θεωρία υπολογισιμότητας, ένα **πρόβλημα αναζήτησης** είναι ένα είδος υπολογιστικού προβλήματος που αναπαριστάται από μια δυαδική σχέση. Αν το *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 λέμε επίσης ότι μπορεί και να την επιλύσει. Κάθε πρόβλημα αναζήτησης αντιστοιχεί σε ένα πρόβλημα απόφασης, και συγκεκριμένα:
: L(R)=\{x\mid \exists y R(x,y)\}. \, 
Αυτός ο ορισμός μπορεί να γενικευθεί σε n-μερείς σχέσεις με τη χρήση οποιασδήποτε κατάλληλης κωδικοποίησης η οποία να επιτρέπει πολλαπλές συμβολοσειρές να συμπιεστούν σε μία (για παράδειγμα απαριθμώντας τες διαδοχικά με κάποιο διαχωριστικό).

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

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

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

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