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

Στη θεωρία υπολογιστικής πολυπλοκότητας και τη θεωρία υπολογισιμότητας, ένα πρόβλημα αναζήτησης είναι ένα είδος υπολογιστικού προβλήματος που αναπαριστάται από μια δυαδική σχέση. Αν το 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 yR(x,y)\}.\,$

Αυτός ο ορισμός μπορεί να γενικευθεί σε 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.