Busqueda Local
- A veces el camino para llegar a la solución no nos importa, buscamos en el espacio de soluciones
- Queremos la mejor de entre las soluciones posibles alcanzable en un tiempo razonable (el óptimo es imposible)
- Tenemos una función que nos evalúa la calidad de la solución, pero que no esta ligada a ningún coste necesariamente
- La búsqueda se realiza desde una solución inicial que intentamos mejorar modificándola (operadores)
Basándonos de la "solución inicial" el programa estará interando n veces,
comparando nodo por nodo, decidiendo y reasignando el nuevo valor de
"solución inicial" en caso de que la solución encontrada fuera mayor.
Como lo unico que importa es encontrar la solución, este algoritmo es lento.
Codigo:
Funcion principal: Escarga de buscar un posibles cliques y comparlos con los anteriores.
Esta funcion se encarga de comparar un "posible clique" al "mayor clique". En caso de que este sea mayor devuelve un TRUE y el nuevo tamaño del clique.
Grafica:
Para generar esta grafica se usaron:
- nodos = 20
- clique(inicial) = 7
- Densidad = 0.5
- intentos 10
- maxIntentos = 10
O sea, son puros reinicios. Eso en sí aún no es búsqueda local. El realizar pequeñas modificaciones de forma iterativa es lo esencial de una búsqueda local. Van 4 pts por el avance parcial.
ResponderEliminar