Grasp

RESUMEN Y ALGUNAS EXPLICACIONES

1) DIFERENCIAS ENTRE CLASES COMPLEJIDADES COMPUTACIONES
* Clase P
Problemas de decisión computables: Por una Máquina de Turing o un algoritmo determinista. Estos se solucionan en tiempo polinómicos.
Contiene problemas que pueden resolverse rápidamente.

* Clase NP
Problemas de decisión No computables:
Por una Máquina de Turing o un algoritmodeterminista. Estos se solucionan en tiempo polinómicos.
Contiene problemas cuya solución puede verificarse rápidamente.

* Problemas NP difícil
Este tipo de problemas se pueden reducir en tiempo polinómico problemas NP

* NP-Completo
Son NP difíciles y están en NP. Ejemplos de problemas:
* Viajante de comercio
* Ciclo hamiltoniano
* Buscaminas

* Porque se creeque P ≠ NP ?
La mayoría de informáticos creen que P ≠ NP. La razón principal por esta creencia es que después de décadas de estudiar estos problemas, nadie ha sido capaz de encontrar un algoritmo con tiempo polinomial por un problema NP-hard. Además, estos algoritmos ya se buscaban mucho antes que se conociera el concepto de NP-completo (los 21 NP-completo problemas de Karp). Por otro lado, elresultado P = NP implicaría extrañas consecuencias que se cruzan falsas, como por ejemplo que NP = co-NP y P = PH.
También de forma intuitiva se puede decir que la experiencia del mundo real nos dice que existen problemas difíciles de resolver pero las soluciones de los cuales son fáciles de verificar.

2) Sdfgdfg

1.1.1 ALGORITMO DE KERNIGHAN-LIN
Este algoritmo de partición, quese engloba dentro de los algoritmos de migración de grupos, que son algoritmos deterministas e iterativos, fue publicado en el año 1970 por B.Kernighan y S.Lin. Se trata de un algoritmo que, en su momento, tuvo bastante éxito y que ha servido de base para el desarrollo de numerosos métodos de placement.
El objetivo de este algoritmo es dividir el circuito en dos partes, de modo que se minimiceel número de nets que conectan celdas pertenecientes a particiones distintas (número de corte).
El algoritmo original supone que todas las nets del circuito conectan exactamente dos celdas y que, además, todas éstas tienen el mismo tamaño
El método comienza asignando aleatoriamente las 2N celdas a dos grupos A y B. Posteriormente, se van intercambiando celdas entre las dos particiones. Estosintercambios, implican un incremento o decremento del número de corte, que se representa mediante la ganancia g.
La ganancia g, asociada al intercambio de dos celdas cualesquiera, se obtiene a partir del parámetro D que caracteriza a cada una de las celdas. Dicho parámetro, se define como la diferencia entre el número de interconexiones de la celda que atraviesan la separación entre particiones,y el número de interconexiones que no atraviesan dicha frontera. Así, el parámetro D, asociado a una celda ai, será:
|
donde:
* outedge(ai), es el número de interconexiones entre la celda ai y otras celdas que no pertenecen a la misma partición.
* inedge(ai), es el número de interconexiones entre la celda ai y otras celdas pertenecientes a la misma partición.
El intercambio de dosceldas ai y bi, se caracteriza mediante una ganancia gi, definida como:

Por tanto, teniendo en cuenta la definición del parámetro D, es fácil deducir que, tal y como habíamos afirmado previamente, la ganancia gi representa la modificación en el número de cortes que implica el intercambio de ai y bi.
El primer paso es seleccionar dos celdas, a1 y b1, pertenecientes, respectivamente, a losgrupos A y B, de modo que la ganancia g1 asociada al intercambio de estos dos elementos sea mínima y, por tanto, la reducción del número de corte sea máxima. A continuación, se intercambian las celdas y, durante las iteraciones restantes, se impiden nuevos desplazamientos de las mismas.
El siguiente paso es seleccionar dos nuevas celdas, a2 y b2, cuyo intercambio ha de suponer un incremento...