Problemă de căutare
În informatică teoretică, o problemă de căutare este o problemă în care se caută cea mai bună soluție posibilă pentru o intrare dată. Problema de căutare diferă de problema de optimizare asociată prin aceea că problema de optimizare nu caută soluția în sine, ci valoarea numerică atribuită acesteia.
În mod formal, o problemă de căutare este definită de o descriere a stării de început și țintă prezentată într-o reprezentare simbolică, un set de operatori și o funcție care determină dacă starea actuală este o stare țintă. Aplicarea tuturor operatorilor existenți la starea de pornire și la stările rezultate deschide spațiul de căutare, care poate fi adesea notat ca un arbore de căutare.
De exemplu, problema 8-regine este o problemă de căutare, în care spațiul de căutare este setul de tablouri de șah cu maximum 8 plasate pe ele Doamnelor . Condiția de pornire aici este o tablă de șah goală, funcția țintă acceptă tabla de șah cu 8 regine care nu se amenință reciproc. Operatorii mapează o tablă de șah S cu regine pe o tablă de șah cu k + 1 regine, unde k regine sunt pe aceleași pătrate ca pe S și regina suplimentară este pe un pătrat care era liber pe S.
