Búsqueda Local

Los algoritmos de búsqueda local se caracterizan por definir, dada una posible
solución del problema, soluciones vecinas. Dos soluciones se consideran vecinas si
ellas son parecidas bajo algún criterio. Definida la función de vecindad, el algoritmo lo
que hace es generar una solución inicial y proseguir a enumerar sus vecinos. Después bajo algún criterio se selecciona una mejor solución de acuerdo a la función objetivo.

La función objetivo esta  definida como un valor  (en este caso el numero de vértices que se utilizaron para la cubierta modificada). Luego reinicia el procedimiento pero esta vez tomando como solucion inicial a la elegida anteriormente como mejor vecina. El algoritmo  finaliza cuando no existe una mejor solución que la actual.
Notar que la heurística (tal y como por definición de heurística debería de ser) no
es exacta, es decir que no brinda (necesariamente) la mejor solución al problema.

Como solución inicial se eligió una bastante sencilla. Consistió en recorrer todos los conjuntos de nodos y verificar si en la solución a devolver no existía ya alguno de sus aristas . De no ser así se agregaba uno al azar.

-Se genera solución inicial
-mientras no encuentre un menor resultado
    s= solución actual       
-el actual sera el mejor
-regresa el mejor


BusquedaLocal
El algoritmo lo primero que realiza es generar la solución inicial, lo cual le cuesta O(nm). Luego ejecuta modifica y búsqueda hasta encontrar una mejor solución. Dado que el bucle se ejecuta si hay una mejora en la soluci ́n, y que  ́sta no puede tener mas de n nodos, el caso en donde más veces iterará será cuando la otra solución arroje un resultado de longitud n y en cada iteración se disminuya la respuesta en uno, hasta alcanzar el mínimo en un conjunto con un solo nodo. En éste caso se harían n iteraciones, por lo que la complejidad sería

O(nm + n(n⁴ m)) = O(n⁵ m).

# Instancia generada para 5 vértices con densidad .5 

Cota inferior: 3.
Cota superior: 2.

0 0 2 factible
0 1 2 factible
0 2 2 factible
0 3 2 factible
0 4 2 factible
1 0 2 factible
1 1 2 factible
1 2 2 factible
1 3 2 factible
1 4 2 factible
2 0 2 factible
2 1 2 factible
2 2 2 factible
2 3 2 factible
2 4 2 factible
3 0 3 factible
3 1 3 factible
3 2 3 factible
3 3 3 factible
3 4 3 factible
4 0 3 factible
4 1 3 factible
4 2 3 factible
4 3 3 factible
4 4 3 factible

/**
       Crea el conjunto de solucion inicial 
       lo mismo que el procedimiento de la cota inferior pero en lugar de ordenarlo 
     */
    public static ArrayList<integer> inicial(ArrayList<arista> grafo) { //lista de solucion inicial 

 ArrayList<integer> cubierta = new ArrayList<integer>();//lista de la cubierta (conjunto seleccionado como solucion inicial)
 ArrayList<arista> copia = new ArrayList<arista>();//lista de aristas copia de la cubierta 
 //de nuevo recorre el grafo 
 Iterator<arista> it = grafo.iterator();
 while (it.hasNext()) {
     copia.add(it.next());//y lo agrega a la copia
 }
 //si el conjunto es mayor a 0 
 while (copia.size() > 0) {
     int largo = copia.size();//se toma el largo del arreglo de aristas 
     //System.out.println("Faltan " + largo + " aristas por cubrir.");//el largo de las aristas 
     /**SELECCIONA*/
     //selecciona un vertice al azar y lo toma en el conjunto seleccion 
     int seleccion = Arista.r.nextInt(largo);
     //System.out.println(seleccion);
     //de acuerdo a la posicion del elemento seleccionado verifica el arista
     Arista a = copia.get(seleccion);
     //cualquier vertice tenga este arista podra formar parte del conjunto de seleccion
     if (Arista.r.nextBoolean()) {
  seleccion = a.desde;
     } else {
  seleccion = a.hasta;
     }
     //crea la cubierta con los elementos seleccionados
     cubierta.add(new Integer(seleccion));
     it = grafo.iterator();
     //lista de aristas eliminados
     ArrayList<arista> eliminados = new ArrayList<arista>();
     //agrega los eliminados tanto los vertices hasta y desde  a la lista 
     while (it.hasNext()) {
  a = it.next();
  //si los aristas forman parte de la seleccion los agrega a la lista eliminados 
  if (a.desde == seleccion || a.hasta == seleccion) {
      eliminados.add(a);
  }
     }
     copia.removeAll(eliminados); //de la copia quita los eliminados
 }

 return cubierta;//regresa la cubierta seleccionada como solucion inicial 
}
public static boolean factible(ArrayList<integer> solucion, ArrayList<arista> grafo) {
 Iterator<arista> it = grafo.iterator();//recorre la lista de aristas del grafo
 while (it.hasNext()) {
     Arista a = it.next(); //
     if (!(solucion.contains(new Integer(a.hasta)) || solucion.contains(new Integer(a.desde)))) {
  //si la solucion no contiene(cubre) todas las aristas regresa un false no es factible 
  return false;
     }
 }
 return true; //y si si pues si :D
    }
    /**Recibe una solucion inicial 
       Regresa el tamaño de la modificacion 
     */
    public static ArrayList<integer> modificacion(ArrayList<integer> solucion, int n, boolean fact)//recibe solucion inicial
    {
 ArrayList<integer> nueva = new ArrayList<integer>();//nueva es la copia de una solucion inicial
 int k = solucion.size();// tamaño de esta
 int brinca = (fact || k == n) ? Arista.r.nextInt(k) : -1;
        //si es factible o es igual al total de vertices quita un elemento de forma aleatoria 
 
 for (int i = 0; i < k; i++) {
     if (i != brinca) {
  nueva.add(solucion.get(i));//agrega un nuevo vertice a la solucion
     }
 }
 if (!fact && k < n) {//si no es factible y el tamaño de la solucion inicial es menor 
     while (true) {
  Integer agrega = new Integer(Arista.r.nextInt(n));//agrega
  if (nueva.indexOf(agrega) < 0) {
      nueva.add(agrega);
      break;
  }
     }
 }

 return nueva;//regresa la nueva
    }
    //busqueda
    public static ArrayList<Integer> busqueda(ArrayList<arista> grafo, int n) {
 ArrayList<integer> mejorSol = null;
        //define la mejor solucion como nula para que cualquiera pueda superarla
 int mejorObj = n;//tamaño de la cubierta inicial seria el total de nodos en el grafo idem

 for (int reinicio = 0; reinicio < 5; reinicio++) {//pasos de reinicio
     ArrayList<Integer> solucion = Arista.inicial(grafo);//solucion inicial
     //Arista.imprime(solucion);
     int obj = Arista.objetivo(solucion);//objetivo de la solucion

     for (int iter = 0; iter < 5; iter++) {//iteraciones de comparar
  boolean fact = Arista.factible(solucion, grafo);//la solucion es factible
  ArrayList<Integer> otrasolucion = modificacion(solucion, n, fact);
                //modifica la solucion inicial en otrasolucion
  boolean otraFact = Arista.factible(otrasolucion, grafo);
                //verifica que sea factible
  int otraObj = Arista.objetivo(otrasolucion);//define su tamanio
  if (otraFact && otraObj <= obj) {//si es mejor que la anterior
      solucion = otrasolucion;//se toma esa solucion
      obj = otraObj;//ese objetivo
      fact = otraFact;//la factibilidad
      if (obj < mejorObj) {//y se convierte en la mejor
   mejorObj = obj;//:3
   mejorSol = new ArrayList<Integer>();
   Iterator<integer> it = solucion.iterator();
   while (it.hasNext()) {
       mejorSol.add(it.next());
   }
      }
  } 
  System.out.println(reinicio + " " +iter + " " + obj + " " + (fact ? "factible" : "no factible")) ;
     }
 }
 return mejorSol;//devuelve la mejor solucion 
    }

Referencias
Informe Algoritmos 2007