Euristica per il problema del cavallo

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

Il problema si trova [url=http://www.di.unipi.it/~micheli/DID/IIA-2016/part1/es2-2016.pdf]qua[/url].
Ora mi riferisco al punto "si trovi una euristica ammissibile, il più possibile informata, per il problema".
Quale può essere una che sia il più possibile informata, ma ancora ammissibile quindi?

Io ho pensato questo:
Dati [math], uno stato corrente, e [math], lo stato goal,
[math]
Dovrebbe essere minore o uguale al numero di mosse nella soluzione ottima. La distanza tra una casella e una casella raggiungibile con una mossa è circa 2, per questo ho diviso la distanza effettiva per due...
... mi confermate cha ha senso?

Voi a cosa avete pensato? una più informata?

MindFlyer
Non ricordo le definizioni, ma sicuramente la tua [math] è quasi sempre maggiore del numero minimo di mosse. Mettici [math] invece di 2, così funziona.

Ymir
Ah, mi sono dimenticata di mettere tutto come parte intera inferiore, sennò, sì, viene maggiore, scusate.
... però non va bene lo stesso perché così fa 0 anche quando non è lo stato goal.
Mmhhh... che euristica si può inventare allora? oggi vedo se mi viene altro.

MindFlyer
Non è questione di parti intere, è che la mossa del cavallo ha lunghezza [math] e non 2. Se metti 2, e la distanza totale è abbastanza lunga e orientata opportunamente, stai sempre sopra come stima. Per rispondere all'altra domanda devi rinfrescarmi la memoria su che cosa è un'euristica ammissibile e informata.

MindFlyer
Ok, ho guardato le definizioni. Vuole chiaramente farti fare quello che hai fatto tu, con [math] al posto di 2. Alternativamente usa la distanza "Manhattan", e metti
[math].

Nessuna di queste due euristiche è più informata dell'altra (perché?), ma la seconda è più facile da calcolare.
Ultima modifica di andrea.tosti il 08/07/2019, 23:27, modificato 1 volta in totale.
Motivazione: aggiornamento
Rispondi

Torna a “[IIA] Introduzione all'intelligenza artificiale”