artificial-intelligence - algoritmo - greedy algorithm geeks for geeks
¿Cuál es la diferencia entre Greedy-Search y Uniform-Cost-Search? (3)
En una búsqueda de costos uniforme, siempre consideras todos los nodos no visitados que has visto hasta ahora, no solo los que están conectados al nodo que miraste. Entonces, en su ejemplo, después de elegir C, verá que la visita a G tiene un costo total de 40 + 5 = 45, que es más alto que el costo de comenzar de nuevo desde la raíz y la visita a D, que tiene un costo de 7. Por lo que visitaría D siguiente.
Cuando busco en un árbol, mi comprensión de la búsqueda de costo uniforme es que para un nodo A dado, que tiene nodos hijos B, C, D con costos asociados de (10, 5, 7), mi algoritmo elegirá C, ya que tiene un costo más bajo. Después de expandir C, veo los nodos E, F, G con costos de (40, 50, 60). Elegirá 40, ya que tiene el valor mínimo de ambos 3.
Ahora, ¿no es lo mismo que hacer una búsqueda codiciosa, donde siempre se elige lo que parece ser la mejor acción?
Además, al definir los costos al pasar de ciertos nodos a otros, ¿debemos considerar el costo total desde el comienzo del árbol hasta el nodo actual, o simplemente el costo en sí mismo de pasar del nodo n al nodo n ''?
Gracias
La diferencia entre ellos es que Greedy elige el nodo con el valor heurístico más bajo, mientras que UCS elige el nodo con el menor costo de acción. Considere el siguiente gráfico:
Si ejecuta ambos algoritmos, obtendrá:
- UCS
Selecciones: S (costo 0), B (costo 1), A (costo 2), D (costo 3), C (costo 5), G (costo 7)
Respuesta: S-> A-> D-> G
- Codicioso:
* Suponiendo que elija la A en lugar de B; A y B tienen el mismo valor heurístico.
Selecciones: S, A (h = 3), C (h = 1), G (h = 0)
Respuesta: S-> A-> C-> G
Por lo tanto, es importante diferenciar el costo de la acción para llegar al nodo del valor heurístico, que es una información que se agrega al nodo según mi experiencia del problema.
No Tu entendimiento no es del todo correcto.
El siguiente nodo que se visitará en el caso de una búsqueda de costo uniforme sería D, ya que tiene el costo total más bajo desde la raíz (7, a diferencia de 40 + 5 = 45).
La búsqueda codiciosa no vuelve a subir al árbol: elige el valor más bajo y se compromete con eso. Costo uniforme elegirá el costo total más bajo de todo el árbol.