Dato il seguente spazio di ricerca, con archi bidirezionali, si considerino le seguenti affermazioni sul cammino soluzione restituito dai vari algoritmi e si selezionino tutte e sole le affermazioni vere.

S rappresenta lo stato iniziale, G rappresenta lo stato goal.

Si assuma che i nodi,  parità di livello o di euristica, vengano selezionati/espansi in ordine alfabetico.

Note:

• In Depth First Search, i nodi vengono inseriti nella frontiera in ordine alfabetico inverso;
• Per conseguire il massimo punteggio vanno indicate  tutte e sole  le opzioni corrette (ma quelle indicate corrette che non lo sono incidono in modo negativo sul punteggio dell’esercizio).

Dato il seguente spazio di ricerca, con archi bidirezionali, si considerino le seguenti affermazioni sul cammino soluzione restituito dai vari algoritmi e si selezionino tutte e sole le affermazioni vere.

S rappresenta lo stato iniziale, G rappresenta lo stato goal.

Si assuma che i nodi,  parità di livello o di euristica, vengano selezionati/espansi in ordine alfabetico.

Nota: per conseguire il massimo punteggio vanno indicate  tutte e sole  le opzioni corrette (ma quelle indicate corrette che non lo sono incidono in modo negativo sul punteggio dell’esercizio).

I requisiti di tempo e di memoria di IDA* possono essere migliorati usando A* come algoritmo di ricerca ad ogni iterazione.

Sia H1 una euristica ammissibile e sia H2 una euristica non ammissibile. Si selezionino le conseguenze vere.

Ogni risposta errata comporta una penalizzazione.

Si consideri il problema del labirinto (come in Teseo) con la variante che l'agente può muoversi liberamente, senza essere vincolato a spostamenti su caselle adiacenti della griglia. Ovviamente non può attraversare i muri.  Il costo di uno spostamento è proporzionale alla lunghezza del tratto percorso.

Quale delle seguenti euristiche è preferibile?