En ocasiones puede ocurrir que el nodo que aparentemente está más cerca del destino te lleve por un camino enrevesado que al final acaba dando un montón de vueltas, en cambio un nodo que parece que se aleja y que se piensa que es el peor acaba siendo el camino más corto.
¿Como se soluciona esto?, se supone que el A* busca siempre primero los nodos que se consideran mejores. En una cuadrícula de nodos tiene más sentido, pero en un grafo no tienen porque ser los mejores los que así lo parezca ¿no?.
¿como me puedo fiar de la heurística por la distancia? ¿si la quito dejaría de ser llamarse A*?
Todo esto lo digo porque he tenido que prescindir de ordenar la lista para elegir al "mejor" candidato a ser calculado, porque no me compensa perder el tiempo de saber cual está más cerca del destino, para la poca mejora que obtengo, al menos en grafos no muy grandes, y más aún si luego creo que puede ser un "fraude" el sistema.
Lo único que hago es descartar aquellos nodos que superan el coste del mejor camino encontrado hasta el momento, por lo demás es una simple búsqueda en anchura.
Pues eso, a ver que opináis.
Otra duda sobre su eficiencia es que no siempre el coste es igual a la distancia.
Por ejemplo, sabemos que por el ascensor llegaremos antes a la planta 20 que por la escalera, aunque estemos al lado de la escalera y haya que andar 100 metros hasta llegar al ascensor desde el lugar que nos encontramos.
Desde este planteamiento el algoritmo se perdería por las escaleras y pasillos buscando el destino, cuando el mejor posible es ir al ascensor.
Vamos que si el A* es así en el sentido de fiarse por las distancias no me sirve para grafos, paso de él, pero quizás estoy equivocado por eso quiero escuchar opiniones.
pd: he editado y añadido unas frases a este mensaje para ser más explícito.
¿Has probado el algoritmo de dijkstra?
Pues la verdad no se como es, el caso es que toda heurística basada en el ordenamiento de la lista de nodos a buscar perjudica considerablemente el rendimiento (reitero que es para un grafo de como mucho unos cientos de nodos).
Me sale más a cuenta el expandir el árbol de búsqueda por igual cogiendo el primer elemento hasta que una rama encuentra el nodo destino, a partir de ahí se descarta cualquier rama que le supera en coste por lo que se finaliza pronto el proceso de búsqueda.
De esta forma en el ejemplo anterior del ascensor, se expandiría por igual el grafo hacia el ascensor y hacia la escalera (y hacia otros puntos), y como el coste del camino es mayor por la escalera a partir de la planta 5 (por ejemplo) que yendo por el ascensor, el proceso de búsqueda se cortaría en ese punto, y no recorrería todo el edificio buscando la habitación de la planta 20 (para luego encima no ser el mejor camino)
¿Podrías explicar un poco por encima en que consiste el dijkstra?
Djijkstra es un A* donde la heurística es siempre 0.
Edit: estás seguro que te es más rentable expandir tooodos los nodos de cada nivel que ordenar los que necesita A*? Ten en cuenta que A* expande los mínimos nodos posibles por definición, con lo cual tampoco tienes tanto que ordenar...
Un saludo!
Vicente
Otro edit :P -> Creo que tu problema es la heurística: una heurística euclidea no puede tener en cuenta el ascensores, teletransportadores y demás, deberías elegir otra.
Un A* es una combinacion de busqueda por profundidad y anchura, y es un alqoritmo optimo (encuentra la mejor solucion) y completo (si hay solucion siempre te la dara), siempre y cuando se cumplan ciertos requisitos para la funcion heuristica, y es que esta sea admisible, es decir que su estimación de lo que queda para llegar al destino a partir de un nodo determinado sea menor que el coste real de llegar al destino desde ese nodo.
Si no te esta dando el resultado que tu esperas (tanto si es en eficiencia o en el camino que buscas), es por que tu funcion de coste y/o funcion heuristica no son adecuadas al problema que te le planteas.
Un saludo.
Entonces le darías al "camino" ascensor un valor inversamente proporcional a la distancia a la que te encuentres de él, y directamente proporcional al piso al que vayas.
No es que sea más lento, en muchas circunstancias es más rápido sobre todo para nodos lejanos, aunque en otras es más lento. Por eso digo que no me compensa el esfuerzo si luego no es totalmente efectivo y el principal problema que veo es que no siempre el coste está asociado a la distancia.
Y ya digo que es para cientos de nodos, si es para muchos miles o millones, si que sería una locura no usar ningún tipo de heuristica.
Por ejemplo, otro "fallo" que he detectado en el A* (o que quizás es mío), es que no siempre encuentra el mejor camino si supuestamente la búsqueda se finaliza una vez que se ha encontrado el destino, intentaré poner un ejemplo.
Citar
-> ----(1)-----------(2)------------(3)
\ /
\ /
(4)--------(5)------ (x) destino
A* se encuentra en el nodo (1) y entiende que el mejor nodo es el (2) porque está mas cerca del destino que el 4 (x), el siguiente nodo que creerá que el mejor es el (3) porque también está más cerca que el (4), finalmente encuentra la (x) y el camino elegido es 1,2,3,4, cuando el correcto era el 1,4,5.
Por favor sacadme de dudas porque hay algo que no hago bien seguro, y si la cosa es más compleja a nivel de cálculos si que empeoraría el tema de velocidad.
Citar
Mars:
Entonces le darías al "camino" ascensor un valor inversamente proporcional a la distancia a la que te encuentres de él, y directamente proporcional al piso al que vayas.
¿Pero como puede saber que el camino por el ascensor va ser mejor que por la escalera si todavía no ha sido recorrido?, el A* tiraría para arriba por la escalera, el ascensor ni se lo plantearía ya que queda aparentemente lejos (seguro que el A* no sabe lo que jode subir 20 pisos).
Realmente ¿a quién no le ha pasado?, sobre todo yendo por el campo que quieres atajar por un sitio y la cagas porque era un asco de camino. Pues es lo que me parece que le ocurre al A*.
Citar
Daemon:
Si no te esta dando el resultado que tu esperas (tanto si es en eficiencia o en el camino que buscas), es por que tu funcion de coste y/o funcion heuristica no son adecuadas al problema que te le planteas.
¿Y cual sería la heurística adecuada a este problema desde tu punto de vista?, es que por lo que he podido comprobar para un número no muy elevado de nodos apenas compensa liarse en cálculos, y te hablo de grafos en 3D, con nodos esparcidos a cualquier distancia y sin más lógica que la del propio mundo en la que está inmerso.
Citar
Daemon:
...que sea admisible, es decir que su estimación de lo que queda para llegar al destino a partir de un nodo determinado sea menor que el coste real de llegar al destino desde ese nodo.
Coño!, releyendo esto veo que es lo que hago yo :) . Solo que para saber la distancia al destino primero tengo que expandirlo en anchura. Después descarto aquellos nodos que nunca serán mejores por haber superado su coste más el mínimo que les queda.
Pero en ningún momento uso expansión en profundidad.
Hola,
tienes un par de lios:
-> ----(1)-----------(2)------------(3)
\ /
\ /
(4)--------(5)------ (x) destino
A* expandiría: 1, 2, 3, 4, 5, X y devolvería el camino 1-4-5-X (ni siquiera estoy seguro si expandiría 3, yo creo que despues de 2 expandiría 4 y 5).
No expandiria 3-X porque la suma de la distancia de llegar hasta 3 más la de llegar a X es mayor que la de llegar a 4 más la distancia estimada de 4 a X.
A* es la distancia hasta ahora más una estimación de lo que me queda. Estimación no es lo que te queda por que lo dice el grafo, es eso, estimación. Por ejemplo, en tu dibujito usa como estimación la distancia en linea recta desde el nodo a la X, verás como nunca elige el camino que has dicho.
Relee lo que te ha comentado Daemon: la heurística es una aproximación, no nada real, simplemente es lo que cree el algoritmo que le va a costar llegar desde un punto a la meta. Normalmente se usa la heurística euclídea (la distancia en linea recta de un punto al otro). Dijsktra por ejemplo es con heurística 0: esto es, no estima nada y lo que hace es explorar tooodos los nodos como un algoritmo avaricioso. Otra heurística es la de Manhattan (se usa en juegos por casillitas), etc etc...
Tu en cambio como dices estás calculando la distancia, ese es tu problema, A* no calcula, se imagina cual será la distancia. Esa imaginación de la distancia (la heurística), si cumple ciertas propiedades (las que ha dicho Daemon), te garantiza que A* encontrará la mejor solución si es que existe y expandirá menos nodos que cualquier otro algoritmo que te puedas inventar tu. En teoría nada puede ser mejor que A* (esto está demostrado ;)).
Luego en la práctica las cosas son más graciosas claro :P Un saludo!
Vicente
Citar
No expandiria 3-X porque la suma de la distancia de llegar hasta 3 más la de llegar a X es mayor que la de llegar a 4 más la distancia estimada de 4 a X.
De acuerdo, no lo entiendo bien pero olvida el lío uno, recuerdo que el fallo solo me daba en el último nodo, como ya dije quizás era fallo mío, aún así intentaré poner el problema que recuerdo que tenía, más concretamente en un futuro.
Por lo demás sigo sin saber que tipo de heurística debo usar para acelerar el algoritmo, el de la distancia euclídea no sirve porque a veces se pierde en estimaciones falsas y no soluciona el problema de distancias cortas con costes altos y viceversa, el de manhattan tampoco, no es el caso.
Otra cosa que me gustaría saber es que coño de algoritmo estoy usando yo, en principio es el de Dijsktra porque expande avariciosamente a todos los nodos, pero con un añadido que hace que una vez encontrado el nodo destino, dejen de expandirse aquellos nodos cuyo coste sea superior al del menor coste encontrado hasta el momento. Esto garantiza que siempre encuentra exactamente el camino de menor coste, que no siempre tiene que ser igual el camino de menor distancia, en un tiempo razonable.
Intenté optimizar el algoritmo para que encontrase lo más rápido posible el nodo destino a partir de la distancia euclídea, pero el cálculo de hallar la distancia euclídea en cada nodo y tener que ordenar la lista para escoger la mejor estimación lo enlentecía.
Por lo tanto no tengo ningún problema (si acaso lo tiene A* conmigo (twist)), porque va de maravilla, y el cálculo más dificil que hace en cada paso es el de sumar costes a cada nodo y compararlos, y me gustaría saber si puedo encontrar un algoritmo o algún tipo de heurística más eficaz que me sirva para acelerar el cálculo.
Otra pregunta, ¿como podría comparar la velocidad de mi algoritmo con la velocidad de otros algoritmos?, a partir de alguna tabla de referencia que compare la velocidad en un grafo dado o algo parecido. Bueno, la verdad es que esto ya es casi misión imposible.
Perdón, era yo el anterior, pensaba que requería identificarse para escribir en este foro.
Hola,
no es el de Djisktra porque Djisktra asegura que una vez que has encontrado un camino para llegar a un nodo, ese es el camino más corto (es como A*, pero Djisktra expande muuuucho más nodos).
Si te lias en el último nodo, quizás es porque lo estás tratando de manera especial. A* lo que hace es lo siguiente: tiene una lista de nodos a los que puede ir, y decide ir al nodo que minimiza la suma de
- Distancia actual (usease los arcos del grafo para llegar del inicio a él)
- Distancia estimada hasta el final (la heurística)
El nodo que tiene ese valor mínimo es el que se expande. Si luego además resulta que es el destino pues premio, has terminado ;)
Me lío con lo que dices de coste y distancia: si es un grafo para moverse por un mapa, esos dos valores son iguales, no tiene sentido que sean diferentes... (o no se lo encuentro). Respecto a velocidades, implementa A* y Djisktra y ponlos en mapas junto con tu algoritmo a ver que sale. Compara velocidad, uso de memoria y nodos expandidos. A* debería ser el mejor por goleada ;)
Podrías poner un pseudocódigo de tu algoritmo para ver si me entero mejor? :) Un saludo!
Vicente
Cita de: "Vicente"Me lío con lo que dices de coste y distancia: si es un grafo para moverse por un mapa, esos dos valores son iguales, no tiene sentido que sean diferentes... (o no se lo encuentro).
No es lo mismo llegar al destino por carretera que cruzando un barrizal, atravesando un campo de minas, por carretera pública o de peaje, por las calles con más riesgo de que te atraquen en lugar de por las más seguras...
Según la implementación tanto coste como distancia entre dos nodos cualquiera pueden ser fijas o variables a lo largo del tiempo, conjunta o separadamente. De ahí que hay quien los combine y quien los trate por separado.
Hay quien llama distancia al producto final distancia*coste (lo deseable que es un tramo) y quien llama distancia solamente a la separación espacial y considera el coste como variable aparte. Suponiendo que hablamos de grafos espaciales, claro. Diferentes nombres para la misma cosa: valor del arco que une los nodos. Mismo perro con distinto collar, como dicen por ahí.
Si no es a eso a lo que os referís haced como que no he dicho nada :P
Mmmmm, en lo que dices por ejemplo no estás buscando el camino más corto tradicional :P Es como el thief que se movía por las zonas donde menos ruido hacía (o eso creo). Tu estás buscando el camino más corto (en distancia) teniendo en cuenta otra cosa (la seguridad en el ejemplo de los atracos). En eso si que tiene sentido distancia y coste. Pero en lo de las escaleras y el ascensor que solo busca el camino más corto (usease una suma de arcos de un grafo) sin ninguna otra consideración (creo). Así que la distancia y el coste deberían ser el mismo valor. Otra cosa es la distancia "física", pero es que eso no debería ser lo que hay en los arcos del grafo (si no te tendrás que buscar otra manera de que se de cuenta que existe el ascensor).
Un saludo!
Vicente
Aquí está el seudocódigo (supongo que lo habré puesto bien)
Tenemos una lista abierta donde introduciremos los nodos, al comienzo contiene un único elemento, el nodo origen.
while (hasta vaciar la lista)
{
se extrae el primer elemento de la lista al que llamaremos N.
if (N es el destino)
se almacena el coste del trayecto en C como el mejor camino.
if (el coste de N supera al de C)
(continue;) se salta, ya que yendo por N nunca se encontrará un camino mejor.
for (cada uno de los nodos sucesores de N que llamaremos S)
{
if (S es padre de N)
(continue;) no se le expande por lo que se pasa al siguiente S
if (S ya ha sido visitado)
{
if (el coste de N + el coste de N a S es menor del coste actual de S)
{
// el nodo S tiene un camino mejor pasando por N
if (S no está en la lista)
{
se le añade al final de la lista.
}
se asigna el nuevo coste a S, y se le asigna el nuevo padre N.
}
}
else (S nunca ha sido visitado)
{
se le añade al final de la lista
se asigna el nuevo coste a S, y se le asigna el nuevo padre N.
}
}
}
si el destino tiene padre se encontró el camino, por lo que se recorre toda la lista de antecesores para guardar el camino encontrado.
He revisado la implementación de la heurística según la distancia euclídea y ha mejorado el tiempo de cálculo aunque tampoco excesivamente.
El problema es que el calcular la distancia y posterior comparación para elegir la posible mejor ruta resta velocidad al algoritmo, y lo que se gana por un lado se pierde por otro aunque ahora sí, siempre es mejor con heurística que sin ella.
Aquí está el pseudocódigo
while (hasta vaciar la lista)
{
se extrae el nodo de la lista cuyo coste actual mas la distancia euclídea con el nodo destino sea menor
se desplazan los nodos posteriores hacia atrás en la lista
if (se alcanza el destino)
(break); se termino la búsqueda
for (cada uno de los nodos sucesores de N que llamaremos S)
{
if (S es padre de N)
(continue;) no se le expande por lo que se pasa al siguiente S
if (S ya ha sido visitado)
{
if (el coste de N + el coste de N a S es menor del coste actual de S)
{
//el nodo S tiene un camino mejor pasando por N
if (S no está en la lista)
{
se le añade al final de la lista.
}
se asigna el nuevo coste a S, y se le asigna el nuevo padre N.
}
}
else (S nunca ha sido visitado)
{
se le añade al final de la lista
se asigna el nuevo coste a S, y se le asigna el nuevo padre N.
se obtiene y se guarda la distancia euclídea al nodo destino para posteriores comprobaciones
}
}
}
Lo de los costes y distancias que me refería anteriormente es lo que dice Senior, no siempre el camino de menor distancia aparente es el camino más corto.
Vicente, ¿podrías poner el pseudocódigo de como lo has hecho tu para compararlo?.
Hola,
mi A* (del libro de Mat Buckland, normalmente la nomenclatura es con lo de lista cerrada y abierta, no así):
while(lista no esta vacia)
{
N = primer nodo del heap
camino_mas_corto[N] = frontera[N] //la forma más corta de llegar a N es la frontera de N (el arco del grafo que nos lleva a N con menor coste)
si N == destino
return;
for (sucesores de N llamados S)
{
h = heuristica(S, destino)
g = costesG[N] + arco(N, S)
if (arco(N, S) no está en la frontera) //frontera[arco(N,S)] == null
{
costesF[S] = h+g
costesG[S] = g
añadimos S al heap
frontera[S] = arco(N, S)
}
else
{
if (g < costesG[S] && camino_mas_corto[N] == null)
{
costesF[S] = h+g
costesG[S] = g
modificamos la prioridad de S en el heap
frontera[S] = arco(N, S)
}
}
}
}
El heap es una cola de prioridad indexada por costesF (g+h). Todas las operaciones en el heap son O(lg d).
Espero que ayude! Un saludo,
Vicente
P.D.: si no ta mu claro lo explico paso por paso
Aparte del algoritmo, dices que la heuristica de la distancia no es la más adecuada a tu problema, ¿no? Y por lo que creo entender tambien tienes una funcion de coste (llamada como arco(N, S) en el algoritmo de Vicente) que no trata únicamente la distancia entre nodos, si no que tiene en cuenta mas cosas. Realmente es dificil ayudarte en esto, si no nos dices en base a qué criterios estas intentando optimizar el camino.
Te doy una directriz de busqueda via Google: algoritmos multiobjetivo, como Senior wapo dijo, se usan para encontrar aquella solucion que encuentra los valores optimos de varios criterios de busqueda. Son útiles sobre todo cuando estos criterios no son uniformes, es decir unos son criterios a maximizar y otros a minimizar (distancia, claramente a minimizar, confort o seguridad del camino a maximizar). A veces combinar estos criterios en una sola función heuristica para el A* no es lo mejor que se puede hacer.
En cualquier caso a veces las buenas heuristicas pueden ser dificiles de obtener.
Un saludo.
P.D.: tampoco soy un experto en este tipo de algoritmos, pero si crees que te pueden servir, puedo preguntar a ver que me cuentan sobre ellos.
Parece que es igual, pero, ¿cómo ordenas la lista?, es decir, ¿donde y cómo decides que N es mejor?.
Hola,
supongo que eres marcode ;) El heap (la cola de prioridad) se ordena al insertar, sacar o modificar un elemento , siempre está primero el nodo cuyo costesF es menor (g+h) (el resto de los elementos excepto el primero no están del todo ordenados).
Un saludo!
Vicente
Creo que ya lo ha dicho, el heap es una cola ordenada por prioriad en base al valor de f (g+h)
[EDIT]
Upps... Perdon, olvidad lo que he dicho, Vicente y yo estabamos escribiendo al mismo tiempo y el respondio antes... :P
[/EDIT]
Jejeje ;)
Semi-OT: En la implementación de Mat usa cola indexada de prioridad, esto es, la cola no tiene valores, tiene índices a una tabla que es donde están los valores. Para implementarla se usan 2-way heaps (o d-way heaps). En la STL los tienes implementados ya (a mi en C# me toco buscar un heap en codeproject y cacharrear con él...). El heap usa dos listas: una con los valores que usa para ordenar y otra que indica la posición de cada índice en la cola (esto es, donde está ahora mismo el índice 5 en el heap? Se usa para poder modificar elementos).
Un saludo!
Vicente
Gracias Daemon. Pero creo que he salido de mi principal duda, que era que el *A podía no darme el resultado correcto si entendía que el mejor camino era el de menor distancia.
Pero me he dado cuenta de que si los trayectos tienen unos costes asociados y estos son los que se comprueban, nunca puede fallar, como bien dijiste antes tú o alguien *A solo busca la estimación, no te encuentra el camino que él cree.
Entonces creo que en el peor de los casos (poniéndoselo difícil con ascensores y historias raras) lo único que haría sería tardar un poco más en encontrar el mejor camino, pero por las pruebas que he hecho nunca es mayor el tiempo que tardaría, que en una búsqueda en anchura común. Aunque a veces se aproxima.
Entonces creo que lo que debería hacer es algún tipo de optimización para seleccionar el nodo a expandir lo más rápido posible y creo que el meter alguna heurística especial perjudicaría más que beneficiaría. Ya que por lo general las distancias suelen estar asociadas a su coste.
Actualmente compruebo de toda la lista cual es el más probable para extraerlo, y seguidamente desplazo el resto de nodos para "tapar" el hueco.
Ahora mientras escribo esto se me acaba de ocurrir por ejemplo que podría mover el último para tapar ese hueco, quizás gano algo de tiempo, voy a probar!!!
sí, soy yo :P
Me creo que estoy identificado y luego no.
Lo peor es que no puedo editar (grrr)
De todos modos tendré que hacer más pruebas para salir de dudas.
Un ejemplo claro de caminos con diferentes costes es un mapa de carreteras.
La carretera de menor distancia no siempre es la mejor, las autovías deben tener mucho menos coste que las comarcales a igual recorrido.
Entonces si A* encuentra un camino de cabras como mejor recorrido mal vamos.
Hola,
a ver, A* se basa en una heurística, y esa heurística te dice el COSTE estimado para llegar a un nodo. La heurísitca euclídea usa la DISTANCIA para estimar el COSTE. Otra heurística podría ser generar un número al azar y multiplicarlo por 23, otra usar el índice del nodo en la lista de nodos del grafo, etc etc etc. Vamos, lo que te de la gana ;) A* también te dice que si el coste que te da la heurística es siempre menor que el coste real, entonces A* encontrará el mejor camino.
Si tienes ascensores y cosas extrañas (teleportadores, etc etc), está claro que la heurística euclídea de por si no te vale. Deberías hacer otra cosa para acomodar esos "caminos" extraños.
Así que no te lies con las distancias y los costes. En un mapa con terrenos (como el que comentas de las carreteras), donde por ejemplo el coste de un nodo a otro es: coste arco = (distancia * el coste del terreno), la heurística euclídea te va a funcionar (y el A* va a ir por carreteras). Ten en cuenta que A* no entiende de distancias, entiende de costes: si le sale más barato ir por la carretera que por el camino de cabras aunque el camino de cabras tenga menos distancia real, va a ir por la carretera, porque para decidir usa dos valores: el coste real para llegar a un punto y el coste estimado para llegar de ese punto al final. Puede que el camino de cabras tenga un coste estimado menor (por la euclídea), pero su coste para llegar real es mayor que el de las carreteras, con lo cual, se va por las carreteras.
Mira un ejemplo: queremos ir de I (inicio) a F (final). Usamos la euclídea. Cada número es el coste para movernos a ese nodo en el grafo.
I 10 10 F
1 10 10 1
1 10 10 1
1 10 10 1
1 10 10 1
1 1 1 1
Aunque el camino con menos distancia es I -> 10 -> 10 -> F, A* va a ir por la fila de 1 que rodean a los 10. Y eso que tu estimas el coste con la distancia! ;) Pero es que no solo es la estimación, es lo que te cuesta moverte de verdad, y cuesta más moverse por dos 10s (2x10 = 20, tu camino de cabras) que por doce 1s (12x1 = 12, las autopistas).
A ver si así queda más claro ;) Un saludo!
Vicente
Sí, si supongo que tendrás razón (más te vale (twist))
La intención es hacer un algoritmo genérico que sirva para cualquier tipo de caminos y creo que la mejor heurística posible es la de la distancia euclídea, ya que por lo general (a no ser que sea un mundo muy extraño) las distancias están muy relacionadas con sus costes.
Claro que en un mundo 3D se pueden dar infinidad de casos en los que no siempre sea así, como tipos de terreno, escaleras, teleportadores, diferentes medios de transporte, lugares donde hay que dar una serie de palancas o usar llaves y en las que por lo tanto hay un coste añadido. Y tenía mi temor de que pudiera fallar en alguna circunstancia la heurística por distancia suponiendo que añadiera o quitara costes a algunos arcos, en cuyo caso tiraría por tierra el algoritmo.
Entonces, ya tengo implementado A* correctamente, el principal lastre que tenía (entre otros) era el del calculo de las distancias, ya que usaba la fórmula de la raíz cuadrada de la suma de las distancias al cuadrado. Pero he podido comprobar que funciona sin hallar la raíz cuadrada ya que al usarse para comparar si es mayor o menor, se puede hacer aunque estén elevadas al cuadrado (es un truco que suelo usar, supongo que lo conoceréis), el caso es que ahora sí que va rápido :) y creo que lo podré optimizar aún más.
La forma de tratar la lista lo hago con una lista de punteros, extraigo el nodo de menor distancia que he calculado y guardado previamente la primera vez que fue expandido, meto en el hueco el último, y reduzco en 1 el tamaño de la lista.
Voy a intentar hacerlo como tú para ver si mejora la velocidad, aunque creo que el mayor tiempo se lo lleva el cálculo de la distancia euclídea entre nodos.
Hola,
como bien dices, hay multitud de casos raros que pueden hacer que A* no valga para tu problema (los tipos de terreno no veo porque, pero si ascensores, teleportadores, etc etc). Seguramente para tu problema en concreto tendrás que cacharrear con el algoritmo básico para que haga lo que quieres exactamente.
Respecto a la velocidad, yo supongo que la mejor forma de optimizar el algoritmo es reduciendo el número de nodos que expande: a menos nodos menos operaciones :) Respecto a la lista, si lo he entendido bien tu usas una lísta y buscas línealmente el siguiente elemento a extraer no? Mientras que para añadir un elemento simplemente lo pones en la lista y fin (o eso he creido entender). Tu tienes O(d) para sacar algo de la lista y O(1) para insertarlo. Con una cola de prioridad implementada como un heap tienes O(lg d) para insertar y extraer. Ya es cuestión de hacer números ;)
Otra cosa, no se el problema que tienes, pero A* es muy pesado en memoria normalmente. Otro aspecto que a lo mejor te interesa optimizar (claro que si el grafo es pequeño da igual).
Ya nos contarás los resultados ;) Un saludo!
Vicente
P.D.: la optimización de la euclídea de usar las distancias al cuadrado para evitarse una raíz cuadrada es útil también sip ;)
Citar
como bien dices, hay multitud de casos raros que pueden hacer que A* no valga para tu problema (los tipos de terreno no veo porque, pero si ascensores, teleportadores, etc etc). Seguramente para tu problema en concreto tendrás que cacharrear con el algoritmo básico para que haga lo que quieres exactamente.
No tengo pensado hacer nada especial para ningún problema en concreto, simplemente con el algoritmo A* con heurística por distancias, pero teniendo en cuenta que en algunos casos (o en muchos) puede no ser siempre el mejor camino la distancia mas corta por lo que no debe fallar.
Lo de los tipos de terreno te pongo un ejemplo: Imagina que estás en un extremo de una piscina o lago, y quieres ir al otro lado, la distancia más corta es atravesarlo a nado, recto, sin embargo la de menor coste (la mejor) es dar un rodeo por el borde.
Se me ocurren montones de situaciones en las que puede darse este problema, uno de ellos que no he comentado antes y que es muy habitual, es cuando por ejemplo en un camino hay unos bichos que le van a hacer perder un tiempo valioso a todo el que vaya por ahí (siendo el mejor camino). En ese caso el trayecto más corto (de tiempo) puede estar yendo por otro lado.
El de la piscina es como el ejemplo que te he puesto arriba con los 1s y los 10s. Prueba tu A* usando la distancia euclídea con ese problema y verás como no falla ;) En el ejemplo de tu piscina también funciona, con los bichos también funciona,... Simplemente es que pongas bien los costes a los arcos de los nodos.
El A* vale para muchas cosas, olvidate de la distancia ;) (por ejemplo, con las heurísticas adecuadas se usa para resolver el cubo de rubrick ;)).
Un saludo!
Vicente
Ya hice las pruebas y funciona bien, me puedo fiar de la heurística por la distancia ;)
Ahora el problema que tengo es falla al usar el cuadrado de las distancias en algunas circunstancias por lo que consume bastante el tener que hallar la raíz cuadrada, por lo que tengo de nuevo el problema :(
Supongo que tendré que ajustar también el resto de variables donde guardo distancias para que también sean al cuadrado :huh:
En cualquier caso estas discusiones me han aclarado algunas cosas :)
No hay mejor convencimiento que hacer la prueba ;)
Un saludo!
Vicente
mira si quires salir de dudas sobre q el a* encuentra siempre el camino más corto con una buena eurística date un paseo por este applet http://www.vision.ee.ethz.ch/~buc/astar/AStar.html. fijate q tienes a la izquiera un sistema de pesos, esto arreglaria tu problema del ascensor, y problemas como el de cruzar montañas,rios, etc etc etc.