Euristica per il problema del cavallo

Il problema si trova qua.
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 [tex](i,j)[/tex], uno stato corrente, e [tex](k,m)[/tex], lo stato goal,
[tex]h(n)= \frac{\sqrt{(k-i)^{2} + (m-j)^{2}}}{2}[/tex]
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?

Comments

  • MindFlyerMindFlyer Posts: 436
    Non ricordo le definizioni, ma sicuramente la tua [tex]h(n)[/tex] è quasi sempre maggiore del numero minimo di mosse. Mettici [tex]\sqrt 5[/tex] invece di 2, così funziona.
  • YmirYmir Posts: 183
    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.
  • MindFlyerMindFlyer Posts: 436
    edited March 2016
    Non è questione di parti intere, è che la mossa del cavallo ha lunghezza [tex]\sqrt 5[/tex] 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.
  • MindFlyerMindFlyer Posts: 436
    edited March 2016
    Ok, ho guardato le definizioni. Vuole chiaramente farti fare quello che hai fatto tu, con [tex]\sqrt 5[/tex] al posto di 2. Alternativamente usa la distanza "Manhattan", e metti
    [tex]h(n)=\frac{|k-i|+|m-j|}{3}[/tex].

    Nessuna di queste due euristiche è più informata dell'altra (perché?), ma la seconda è più facile da calcolare.
Sign In or Register to comment.