Algoritmi di Ricerca

Question 1

BFS - Ricerca in ampiezza
- che significa ampiezza
- quale logica viene usata
- quindi se abbiamo una stack quale pop si fa?

Answer 1

• orizzontale e poi verticale.
• logica della coda (First in First Out)
• popleft (prendo prima gli elementi più vecchi)

Question 2

DFS- Ricerca in profondità
- che significa profondità
- quale logica viene usata
- quindi se abbiamo una lista quale pop si fa?

Answer 2

• prima verticale e poi orizzontale
• logica della stack (Last In First Out)
• pop (prendo prima gli elementi più recenti)

Question 3

LDFS- Ricerca in profondità limitata
- simile a…
- quando si ferma?

Answer 3

Simile per tutto alla DFS ma termina quando i cammini raggiungono una profondità predefinita.

Question 4

UCS Uniform Cost Search
- che logica viene usata
- heap e heap pop
- quale è il procedimento?

Answer 4

• logica della coda prioritaria (priorità a chi ha un peso minore)
• heap è la coda prioritaria, pop leva elemento con peso minore.

Procedimento:
- nodo radice in coda
- rimuovo elemento dalla cosa:
-if è il destination allora FINE
- else if vedo se è gia nei visitati
- else metto in coda tutti i figli insieme al peso del path dal nodo radice. Metto il nodo nei visitati.

Question 5

Algo Greedy-
- Idea (+ esempio percorso più breve)
- Con quale struttura viene implementato?

Answer 5

• Con la speranza di raggiungere una soluzione globale, ad ogni step effettua scelta localmente ottimale.
• sempre coda prioritaria ma rispetto all’euristica.

Question 6

Algo A*
- Idea
- Come viene strutturato

Answer 6

• Unisce UCS e Greedy
• sempre coda prioritaria ma rispetto al Costo+Euristica