¿Cuál es la diferencia entre la Búsqueda Codiciosa y la Búsqueda de Costo Uniforme?
Al buscar en un árbol, mi comprensión de la búsqueda de costos uniformes es que para un nodo dado A, teniendo nodos hijos B,C,D con costos asociados de (10, 5, 7), mi algoritmo elegirá C, ya que tiene un costo menor. Después de expandir C, veo 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 eliges lo que parece ser la mejor acción?
También, al definir costos de ir de ciertos nodos a otros, ¿debemos considerar el costo total desde el principio del árbol hasta el nodo actual, o solo el costo en sí mismo de ir de nodo n a nodo n'?
Gracias
3 answers
No. Tu entendimiento no es del todo correcto.
El siguiente nodo que se visitará en caso de uniform-cost-search sería D, ya que tiene el costo total más bajo desde la raíz (7, en lugar de 40+5=45).
La búsqueda codiciosa no vuelve a subir al árbol - elige el valor más bajo y se compromete a eso. Uniform-Cost elegirá el costo total más bajo de todo el árbol.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-01-18 05:18:03
En una búsqueda de costos uniforme siempre considera todos los nodos no visitados que ha visto hasta ahora, no solo aquellos que están conectados al nodo que miró. Así que en su ejemplo, después de elegir C, encontrará que visitar 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 visitar D, que ha costado 7. Así que visitarías a D después.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-01-17 20:46:17
La diferencia entre ellos es que el Codicioso elige el nodo con el valor heurístico más bajo, mientras que el UCS elige el nodo con el costo de acción más bajo. 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 elige 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 basado en mi experiencia del problema.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-10-15 02:25:49