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
Las gráficas son un desastre :P Mañana revisamos bien. Corran un ejemplo un poco más largo (o sea, más pasos por reinicio) y con eso les hacemos una gráfica que sirve. Van 8 pts por hoy.
ResponderEliminar