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 dove se e solo se " è una risposta ammissibile dato ".
Si dice che un algoritmo risolve un problema di ricerca se, per ogni valore di input , esso restituisce una risposta ammissibile per quando tale risposta esiste o, altrimenti, esso restituisce un output appropriato al caso, ad es. "non trovato", per gli 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 in un oggetto . 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.
Definizione Una definizione formale è la seguente:
Date una relazione binaria con campo (elementi del dominio o codominio) e una macchina di Turing , si dice che calcola se:
Se è tale che esiste un tale che allora accetta con output tale che (potrebbero esserci più , basta che trovi solo uno di essi). Se è tale che non esiste tale che allora rifiuta .
Si noti che il grafico di una funzione parziale è una relazione binaria, e se calcola una funzione parziale, allora esiste al più un output possibile.
La relazione può essere considerata come un problema di ricerca e una macchina di Turing che calcola si dice anche che lo risolva. A ogni problema di ricerca corrisponde un problema decisionale, ossia
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).
Ricerca su grafo Un problema di ricerca è definito da:
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.
Metodo di ricerca
algoritmo di ricerca generico: dato un grafo, un insieme di nodi di partenza e nodi di arrivo, si esplorano in modo incrementale i percorsi del grafo a partire dai nodi di partenza. Si gestisce un elenco di percorsi “di confine” dai nodi di partenza che sono già stati esplorati. Man mano che si procede, il confine si estende verso i nodi non esplorati fino a quando non viene trovato uno stato-obiettivo. Il modo in cui si estende il confine dipende dalla scelta della strategia di ricerca. 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
Note
Voci correlate Operatore di ricerca illimitato Problema decisionale Problema di ottimizzazione Problema funzionale Problema di conteggio (complessità) Gioco di ricerca
Collegamenti esterni
Categoria:Problemi computazionali