2

estoy implementando el algoritmo A* en Java y me ha surgido una duda en cuanto al Comparator que se le pasa a la cola con prioridad para ordenar la cola de ABIERTOS.

Este es el código que tengo para el comparador:

        public int compare(Nodo n1, Nodo n2) {
            int diff = n1.f - n2.f;
            if( diff > 0) return 1;
            else if (diff < 0) return -1;
            else {
                diff = n1.g - n2.g;
                if (diff > 0) return 1;
                else if (diff < 0) return -1;
                else return 0; //son iguales

            }
        }
    };

En este caso, la ordenación se corresponde a los criterios que se me han pedido, primero comparo según la f que tenga cada nodo, si la diferencia entre f's es positiva pues el primero es mayor que el segundo, por ello se devuelve un entero positivo. Si es negativa el primero es menor, por eso se devuelve menos 1. En caso de ser iguales se pasa a comparar según el valor de g de cada nodo de igual manera.

Mi duda viene en caso de que ambos nodos tengan igual f e igual g. Se me pide que se ordenen según su entrada en la cola de abiertos, es decir, en caso de empate en f y en g, el más antiguo de los nodos iría primero. Si devuelvo 0 en caso de empate, ¿estaría garantizando esto?

Un saludo y muchas gracias a todos, espero que haya explicado todo lo mejor posible.

1
  • Hola David, sin ver el código de tu aplicación, es difícil saber que responder, obviamente, a tu método le falta una última comparación, la del lugar en la cola de abiertos, ahora, de donde sacas eso... ni idea. Commented el 5 abr. 2023 a las 2:20

2 respuestas 2

2

Muchas gracias a todos por las respuestas, he probado a hacer lo siguiente:

Comparator<Nodo> NodeComparator = new Comparator<Nodo>() {
        public int compare(Nodo n1, Nodo n2) {
            int diff = n1.f - n2.f;
            if (diff > 0)
                return 1;
            else if (diff < 0)
                return -1;
            else {
                diff = n1.g - n2.g;
                if (diff > 0)
                    return 1;
                else if (diff < 0)
                    return -1;

                else {
                    diff = n1.contador - n2.contador;
                    if (diff > 0)
                        return 1; //si el primero es más nuevo tiene menos prioridad
                    else if (diff < 0)
                        return -1;
                    else
                        return 0;
                }
            }
        }
    };

El atributo contador de cada nodo me indica el orden en el que ha sido generado, es decir, cada vez que expando un nodo padre sumo uno al contador de sus hijos, así garantizo que los más antiguo sean tomados antes.

La duda ahora va más encaminada a cuando se devuelve 0 porque dos nodos también son descendientes del mismo padre, ¿se respeta el orden de introducción en la cola con prioridad? Es decir, yo siempre expando el Nodo de la misma forma: UP, DOWN, LEFT, RIGHT. ¿Puedo afirmar que se garantiza que en caso de empatar en todo, me tomará primero el nodo generado con UP que es el primero que se introduce?

1
  • Hola David, recuerda marcar tu respuesta como aceptada (debes esperar unos días), con la corrección que hiciste, solo puede devolver "0" si es el mismo nodo, dado que dos nodos distintos no deberían poder tener el mismo valor de "contador". Commented el 5 abr. 2023 a las 11:11
1

No, no estarías garantizando eso por que se espera (por que lo entiendo) que se devuelva un 1 o un -1 .

Así que en caso de empate tienes que devolver el mismo resultado que en el caso de que el nodo más antiguo sea mayor.

Pero claro, ¿ cual es el más antiguo ? Eso lo sabes tu.

Lo normal es que el primer nodo sea más antiguo que el segundo (al leerlos en orden, suponiendo que se han introducido cronológicamente). Por lo que en caso de empate devuelves un 1 positivo. Pero insisto, depende, por que si es el resultado de una consulta a una DB, dependerá de la consulta como se ha ordenado.

Si aceptamos que estan introducidor cronológicamente, lo que tienes que hacer es cambiar esta línea del segundo else:

if (diff > 0) return 1;
// en vez de decirle "si es mayor que 0"

por esta otra:

if (diff >= 0) return 1;
// Le dices "si es mayor o igual que 0"

i eliminas esta:

else return 0; //son iguales
// ya no pinta nada esta linea

Un saludo.

4
  • Hola ferter3006, si usa if ( diff >= 0 ) return 1; cuando sean iguales (osea diff = 0), le devolverá que es mayor... Commented el 5 abr. 2023 a las 2:23
  • Si, i esto es exactamente lo que dice su enunciado: si la diferencia entre f's es positiva pues el primero es mayor que el segundo, por ello se devuelve un entero positivo // en caso de que ambos nodos tengan igual f e igual g. Se me pide que se ordenen según su entrada en la cola de abiertos, es decir, en caso de empate en f y en g, el más antiguo de los nodos iría primero. Es decir que al poner ** if ( diff >= 0 ) return 1** el más antiguo en caso de empate se ordena primero.
    – ferter3006
    Commented el 5 abr. 2023 a las 6:27
  • Es decir, no es que le devuelva que es mayor (como tu dices) si no que le devuelve el orden, si le retorna un 1 es por que el primer nodo va primero, si le retorna un -1 es pro que el segundo nodo va primero. Al final, da igual el valor, solo el orden (según entiendo yo).
    – ferter3006
    Commented el 5 abr. 2023 a las 6:28
  • Normalmente, el método compare, devuelve -1 si es menor, 0 si es igual, y 1 si es mayor, cuando tu invocas el metodo sort(), este usa el compare y espera una devolución como la que mencioné, como no sabemos mucho, debido a la poca info que da el OP, yo soy de la idea de mantenernos dentro de ese esquema... pero tu puedes pensar distinto y obrar en consecuencia, saludos!. Commented el 5 abr. 2023 a las 9:00

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.