El Algoritmo Fringe Search propuesto en http://webdocs.cs.ualberta.ca/~holte/Publications/fringe.pdf por Yngvi Bjornsson Markus Enzenberger, Robert C. Holte y Jonathan Schaeffer produce caminos que tienden a ser óptimos, pero mejoran la velocidad de ejecución de A* de una manera significativa. Pongo a disposición de todos el código fuente usado en mi tesis titulada: "El Algoritmo Fringe Search como solución superior a A* en la búsqueda de caminos sobre gráficos de malla" presentada en la UNAM, en el cual implemento este algoritmo en lenguaje C. Espero sea útil.