Ho un algoritmo A * con un'euristica per guidare al meglio il percorso migliore. Il problema è che ogni nodo può avere fino a 240 bambini e ogni bambino successivo anche ...
Quindi, fare un ampio approccio mi porterà da nessuna parte a meno che l'euristica sia molto accurata. Il problema è quando il costo e la stima di ogni nodo figlio è molto simile alla maggior parte dei nodi fratelli (quindi un buon 100/240 è circa lo stesso). In altre parole, ci sono davvero oltre 2000 modi per risolvere questo problema con circa lo stesso costo totale.
Non posso permettermi che l'algoritmo segua ogni opzione per trovare la soluzione "migliore" in quanto non vi è molto beneficio in quanto la differenza di costo tra tutte le buone opzioni è di 1-5 secondi che non vale il risparmio in questo progetto.
Quindi qual è il modo migliore per risolvere tali problemi in generale.
Alcune opzioni che ho provato / a sapere. (nessun altro?)
- Limitare il numero di bambini nell'elenco delle "frontiere" (non ideale)
- Raggruppando tutti i nodi figlio simili per restituire solo un nodo figlio (non l'ho ancora provato)