Herramientas de usuario
ai:techniques:search_algorithms
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
ai:techniques:search_algorithms [2010/10/24 09:09] alfred |
ai:techniques:search_algorithms [2020/05/09 09:25] (actual) |
||
|---|---|---|---|
| Línea 28: | Línea 28: | ||
| - De todos los nodos de la lista de nodos cerrados escogemos el de //f// más baja. | - De todos los nodos de la lista de nodos cerrados escogemos el de //f// más baja. | ||
| - Si el estado actual es el estado objetivo ya hemos acabado. Si no, volvemos al paso 1. | - Si el estado actual es el estado objetivo ya hemos acabado. Si no, volvemos al paso 1. | ||
| + | |||
| Línea 82: | Línea 83: | ||
| - | + | ===== IDA* ===== | |
| - | + | - Realizamos el cálculo de coste para el nodo 1, ese será el coste (o profundidad) inicial y máximo permitido. | |
| - | + | - Nos ponemos en el primer nodo. | |
| - | + | - Vamos al siguiente nodo (moviéndonos siempre en profundidad, es decir, siempre abriremos el último nodo. | |
| - | + | - Si el siguiente nodo no pasa del coste máximo actual lo cogemos como nodo actual y hacemos el paso 3. | |
| - | + | - Miramos el siguiente que toque (desde un nodo anterior). | |
| + | - Si ningún nodo puede expandirse por superar todos el coste máximo, incrementamos este y vamos al paso 2. | ||
| + | {{ ai:ida.png |}} | ||
| ===== Hill-Climbing ===== | ===== Hill-Climbing ===== | ||
| Línea 101: | Línea 103: | ||
| <code> | <code> | ||
| function Hill-Climbing (problema) retorna una posible solución | function Hill-Climbing (problema) retorna una posible solución | ||
| - | entrada: problema | + | entrada: |
| - | utiliza: currentNode, nextNode | + | problema |
| - | currentNode = getInitialState (problem) | + | utiliza: |
| - | loop do | + | currentNode |
| - | nextNode = currentNode.getSuccessors().getNodeWithMaximumValue() | + | nextNode |
| - | if (nextNode.value < currentNode.value) | + | ejecución: |
| - | return current | + | currentNode = getInitialState (problem) |
| - | currentNode = nextNode | + | loop do |
| - | end loop | + | nextNode = currentNode.getSuccessors().getNodeWithMaximumValue() |
| + | if (nextNode.value < currentNode.value) | ||
| + | return current | ||
| + | currentNode = nextNode | ||
| + | end loop | ||
| </code> | </code> | ||
| Línea 117: | Línea 123: | ||
| * **First-Choice hill climbing** es un stochastic hill climbing pero en la generación de futuros estados. Va generando pasos siguientes hasta que encuentra uno mejor, es decir, será el primer estado mejor el que escoja. Es una buena estrategia cuando el estado tiene muchos sucesores. | * **First-Choice hill climbing** es un stochastic hill climbing pero en la generación de futuros estados. Va generando pasos siguientes hasta que encuentra uno mejor, es decir, será el primer estado mejor el que escoja. Es una buena estrategia cuando el estado tiene muchos sucesores. | ||
| * **Random-restart hill climbing**, genera varios estados iniciales de forma aleatoria (en sí ya es un problema ya que no es trivial), a partir de estos inicia distintas soluciones. | * **Random-restart hill climbing**, genera varios estados iniciales de forma aleatoria (en sí ya es un problema ya que no es trivial), a partir de estos inicia distintas soluciones. | ||
| + | |||
| + | |||
| + | |||
| Línea 124: | Línea 133: | ||
| <code> | <code> | ||
| función SimulatedAnnealing (problema, organización) retorna un estado solución | función SimulatedAnnealing (problema, organización) retorna un estado solución | ||
| - | recibe | + | entrada: |
| + | problema | ||
| + | organización, asigna la relación tiempo\temperatura | ||
| + | ejecución: | ||
| + | current = getInitialState (problem) | ||
| + | for t = 1 hasta infinito hacer: | ||
| + | T = organización (t) | ||
| + | if T = 0: | ||
| + | return current | ||
| + | next = current.getRandomSuccessors() | ||
| + | ∧E = next.Value - current.Value | ||
| + | if ∧E > 0: | ||
| + | current = next | ||
| + | else if getProbability(∧E, T) > random(0,1): | ||
| + | current = next | ||
| </code> | </code> | ||
| El loop interno es similar al del hill climbing, pero en vez de escoger el mejor movimiento escoge uno aleatorio, si dicho movimiento mejora la situación será siempre aceptado pero si no a cada paso que se haga será, por probabilidad, más difícil que se siga. Es decir, la mala calidad de la solución hace que la temperatura (//T//) baje y, por lo tanto, la cantidad de evaluación (//∧E//) menor. | El loop interno es similar al del hill climbing, pero en vez de escoger el mejor movimiento escoge uno aleatorio, si dicho movimiento mejora la situación será siempre aceptado pero si no a cada paso que se haga será, por probabilidad, más difícil que se siga. Es decir, la mala calidad de la solución hace que la temperatura (//T//) baje y, por lo tanto, la cantidad de evaluación (//∧E//) menor. | ||
ai/techniques/search_algorithms.1287911346.txt.gz · Última modificación: 2020/05/09 09:24 (editor externo)
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: CC Attribution-Noncommercial-Share Alike 4.0 International
