Problema di ricerca

Nella teoria della complessità computazionale e nella teoria della computabilità, un problema di ricerca è un problema computazionale di ricerca di una risposta ammissibile per un dato valore di input, a condizione che tale risposta esista. Infatti, un problema di ricerca è specificato da una relazione binaria ${\displaystyle R}$ dove ${\displaystyle xRy}$ se e solo se "${\displaystyle y}$ è una risposta ammissibile dato ${\displaystyle x}$".

Si dice che un algoritmo risolve un problema di ricerca se, per ogni valore di input ${\displaystyle x}$, esso restituisce una risposta ammissibile ${\displaystyle y}$ per ${\displaystyle x}$ quando tale risposta esiste o, altrimenti, esso restituisce un output appropriato al caso, ad es. "non trovato", per gli ${\displaystyle x}$ senza risposta.

I problemi di ricerca sono tipici nella teoria dei grafi e nell'ottimizzazione combinatoria, ad esempio la ricerca di corrispondenze, cricche e insiemi stabili in un dato grafo non orientato.

Intuitivamente, il problema consiste nel trovare una struttura ${\displaystyle y}$ in un oggetto ${\displaystyle x}$. Si dice che un algoritmo risolve il problema se quando esiste almeno una struttura corrispondente, allora viene emessa un'occorrenza di tale struttura, altrimenti esso si interrompe con un output appropriato.

Una definizione formale è la seguente:^[1]

Date una relazione binaria ${\displaystyle R}$ con campo (elementi del dominio o codominio) ${\displaystyle \operatorname {field} (R)\subseteq \Gamma ^{+}}$ e una macchina di Turing ${\displaystyle T}$, si dice che ${\displaystyle T}$ calcola ${\displaystyle R}$ se:

• Se ${\displaystyle x}$ è tale che esiste un ${\displaystyle y}$ tale che ${\displaystyle R(x,y)}$ allora ${\displaystyle T}$ accetta ${\displaystyle x}$ con output ${\displaystyle z}$ tale che ${\displaystyle R(x,z)}$ (potrebbero esserci più ${\displaystyle y}$, basta che ${\displaystyle T}$ trovi solo uno di essi).
• Se ${\displaystyle x}$ è tale che non esiste ${\displaystyle y}$ tale che ${\displaystyle R(x,y)}$ allora ${\displaystyle T}$ rifiuta ${\displaystyle x}$.

Si noti che il grafico di una funzione parziale è una relazione binaria, e se ${\displaystyle T}$ calcola una funzione parziale, allora esiste al più un output possibile.

La relazione ${\displaystyle R}$ può essere considerata come un problema di ricerca e una macchina di Turing che calcola ${\displaystyle R}$ si dice anche che lo risolva. A ogni problema di ricerca corrisponde un problema decisionale, ossia ${\displaystyle L(R)=\{x\mid \exists yR(x,y)\}.}$

Tale definizione può essere generalizzata a relazioni n -arie mediante un'opportuna codifica che consenta di comprimere più stringhe in un'unica stringa (ad esempio elencandole consecutivamente usando un delimitatore).

Un problema di ricerca è definito da:^[2][3][4]

• Un insieme di stati
• Uno stato iniziale
• Uno stato obiettivo o test di obiettivo, ossia una funzione booleana che dice se un determinato stato sia uno stato obiettivo
• Una funzione successore, ossia una mappatura da uno stato a un insieme di nuovi stati

Obiettivo: trovare una soluzione quando non si disponga di un algoritmo per risolvere un tale problema, ma solo una specifica di come dovrebbe essere fatta una soluzione.

    Input: un grafo, un insieme di nodi iniziali,
        Boolean procedure goal(n) che testa se n sia un nodo obiettivo.
    frontiera := {s : s è un nodo iniziale};
    while frontiera non vuota:
        seleziona e rimuovi il percorso <n0, ..., nk> dalla frontiera;
        if goal(nk)
            return <n0, ..., nk>;
        for each n vicino di nk
            aggiungi <n0, ..., nk, n> alla frontiera;
    end while

• Operatore di ricerca illimitato
• Problema decisionale
• Problema di ottimizzazione
• Problema funzionale
• Problema di conteggio (complessità)
• Gioco di ricerca

• (EN) Eric W. Weisstein, Searching, su MathWorld, Wolfram Research.