La práctica consiste en la
resolución de un determinado tipo de problemas de enrutamiento
para diseño de circuitos integrados. Las posiciones
válidas en el circuito se determinan mediante una rejilla de
puntos rectangular de dimensiones
ROWS filas x
COLS columnas. Sobre esa rejilla, nos especifican un número
PATHS
de pares de puntos a conectar, así como una serie de posiciones
no válidas (obstáculos) que no se pueden utilizar. Se
desea obtener el trazado de líneas de cable que conecte entre
sí cada par de puntos, evitando tanto las posiciones
obstáculo como, por supuesto, las líneas de los restantes
pares.
Cuando el problema de enrutamiento tenga solución, se desea
además conocer cuál es el trazado mínimo en
términos de tramos de cable utilizados.
2. Ejemplo
Supongamos que tenemos 2 pares de puntos (el par p0 y el par p1)
distribuidos en una rejilla de 7 filas x 7 columnas como la siguiente:
Ejemplo 1.
dos posibles soluciones a este problema serían:La solución A consume 19
tramos de cable (13 para el par p0 + 6 para el par p1) y de hecho es
óptima para el problema planteado, mientras que la
solución B consume 25 tramos de cable (17 para el par p0 + 8
para el par p1).
La búsqueda se
realizará imaginando que "movemos" el cable de cada par de
puntos avanzando desde uno cualquiera de ellos (el que llamaremos inicial) hasta el otro (que llamaremos final).
La elección de cuál es el punto inicial y el final de
cada par es arbitraria e irrelevante. En cada paso, haremos "avanzar"
el cable evitando caer en un obstáculo o en una posición
ya ocupada por cable (ya sea del par actual, o de otro par).
Estados
La información a almacenar en cada estado incluye un array
llamado cells de ROWS filas x COLS columnas. Para cada posición
cells[i][j], el valor -1 indicará que está vacía,
el -2 que hay un obstáculo y un valor i entre 0 y PATHS-1
indicará que esa posición ha sido ocupada por el path i.
En realidad, sería suficiente con indicar que está
ocupada, pero almacenamos también el número de par a
efectos de visualización.
Como ejemplo, la situación inicial del Ejemplo 1 se representaría con el array
0 1 2 3 4 5 6
0 -1 0 -1 -1 -1 -1 -1
1 -1 -1 -1 -1 -1 -1 -1
2 -1 -1 1 -1 -1 -2 -2
3 -1 -2 -2 -1 -1 -2 -2
4 -1 -2 -2 -1 -1 -1 -1
5 -1 -1 -1 -1 -1 -1 -1
6 -1 -1 -1 -1 -1 -1 -1
En este caso, hemos tomado como
puntos iniciales el (0,1) para el par p0 y el (2,2) para el par p1.
Como segundo ejemplo, si hacemos avanzar ambos cables 2 posiciones a la derecha,
tendríamos el array:
Nótese que los extremos finales no aparecen marcados. Usaremos un array constante
endpoints de
PATHS puntos, tal que
endpoints[i].r y
endpoints[i].c indican la fila y la columna de la posición final para el par p
i. Como el array
endpoints no varía, se puede almacenar como una variable general y no es necesario repetirlo en cada estado.
Para terminar, necesitaremos también indicar de algún
modo el extremo actual de cada cable que hemos trazado, para saber por
dónde continuar. Esto se hará manteniendo un array
last[i] de modo que
last[i].r y
last[i].c indican la fila y la columna del extremo actual del cable p
i.
Acciones
En cada paso vamos a trazar un tramo de cable para cada par de puntos.
Los movimientos a realizar serán, para cada cable, uno de los 5
posibles: NOP (-), UP (u), DOWN (d), RIGHT (r) y LEFT (l). El
movimiento NOP significa que no movemos el cable y se reserva
exclusivamente para el caso en el que un cable concreto haya alcanzado su destino (esto es, cuando
last[i] y
endpoints[i] coinciden).
Cuando eso sucede, en ese cable sólo se puede ejecutar NOP,
mientras que si el cable no ha alcanzado el destino, nunca se puede
ejecutar NOP. Para los movimientos usaremos las constantes:
#define NOP 0
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4
Como en cada paso de búsqueda movemos todos los cables, si
PATHS=3 el aspecto de una acción sería, por ejemplo, una
tupla como (r,u,-), indicando que trazamos un tramo de cable desde
last[0] a la derecha, un tramo de cable desde
last[1] hacia arriba y dejamos sin mover el cable 2. El número total de acciones posibles será por tanto: 5
PATHS, esto es, 25 para PATHS=2, 125 para PATHS=3, etc. Para codificarlas usamos un valor entre 0 y 5
PATHS-1.
La siguiente función permite obtener un array ops[PATHS] con el
movimiento correspondiente para cada cable a partir de un código
de acción op:
void getOpsVector(int op,int ops[]) {
int i;
for (i=PATHS-1;i>=0;i--, op /= 5)
ops[i]=op % 5;
}
Como ejemplo, si PATHS=3, el código de
acción 113 devuelve el array {4,2,3} que corresponde a la
acción conjunta (r,d,l).
4. Código disponible
Los ficheros fuente se proporcionan total o parcialmente:
- routing.h está completo.
- routing.c deben rellenarse aquellas partes indicadas en comentarios.
Como se puede ver, el código para la obtención del estado inicial ya nos la facilitan. La función
initialState construye un estado inicial a partir de un array de strings llamado
settings. Para el Ejemplo 1, ese array tendría el aspecto:
char *setting[ROWS] = {
".0....1",
".......",
"..1..XX",
".XX..XX",
".XX...0",
".....XX",
".....XX"
};
donde '.' indica libre, 'X' indica un obstáculo y los
dígitos son los pares a conectar. En principio, almacenamos el
array settings en el fichero goal.h, de modo que cambiando ese fichero,
podemos cambiar el dominio del problema a resolver. Estos son algunos
ejemplos:
goal0.h,
goal1.h,
goal2.h,
goal3.h,
goal4.h,
goal5.h.
NOTA: al cambiar de dominio, podremos necesitar también cambiar
el valor de las constantes ROWS, COLS y PATHS, definidas en routing.h.
Como último comentario, nótese que en routing.c, la función
successorState
también está prefijada. La idea es que el cálculo
del estado siguiente se realizará simultáneamente con la
comprobación de si una acción es ejecutable (
executable), para evitar duplicar esfuerzos. De este modo,
executable trabajará sobre un estado auxiliar
aux, (ya declarado en routing.c) de forma que después,
successorState devuelve una copia de ese estado. Este esquema funciona gracias a que siempre se llama a
successorState justo después de comprobar si un estado es ejecutable.
5. Entrega
La práctica es individual y su plazo es el
lunes 10 de enero.
La forma de entrega por defecto es durante el desarrollo de las clases
de laboratorio, aunque también es posible usar el horario de
tutorías.