Problema2 de Diseño de Analisis y Algoritmos

Dejeme aclarar que algunas soluciones de los problemas resuleto aca, no son todas mias.

Problema2

Considere una ciudad cuyas calles están dadas por una red ortogonal X´Y (todas las manzanas son cuadrados del mismo tamaño y forman una matriz, hay X calles en una dirección y Y calles en la otra). Se desea caminar de la esquina superior izquierda a la esquina inferior derecha, pero hay intersecciones de calles por las que está prohibido pasar. Estas intersecciones prohibidas están dadas en una matriz P donde el valor P[i, j]=1 quiere decir que la intersección está prohibida y P[i,j]=0 quiere decir que se puede pasar por ella. Diseñe un algoritmo que encuentre el camino más corto (de la esquina superior izquierda a la inferior derecha) sin pasar por las intersecciones prohibidas.

La idea general de la estrategia de solución es la siguiente:

· Marca en el mapa todas las esquinas que un número que sea indicador de la longitud mínima de un camino que vaya desde el inicio hasta esa esquina.

· Se marcara con –(k + 1) todas aquellas esquinas para las cuales los caminos más cortos desde el inicio hasta ellas tienen longitud k.

· Se marcaran con 0 todas las esquinas que no tengan un camino desde el inicio hasta ellas.

· Si una casilla se marco con –m y tiene una vecina que está marcada con 0 se actualiza la marca para esa casilla con el valor –(m+1). Esto es debido a que hasta ese momento no se habían encontrado caminos desde el origen hasta ella pero en el momento en que corroboramos que era vecina de una marcada con –m podemos asegurar que existe un camino desde el inicio hasta ella con longitud m (camino hasta la marcada con –m tiene longitud m-1 y le añadimos el viaje hacia la nueva esquina).

· Para garantizar que cuando se marque una casilla es porque se encontró uno de los caminos más cortos desde el inicio hasta la casilla vamos explorando el mapa de forma tal que primero se marquen todas las casillas que se pueden alcanzar en m pasos y luego pasamos a marcar las que se alcanzan en (m+1).

Se han dejado claras las bases fundamentales del algoritmo. Solo nos queda mencionar que su implementación se hizo en el lenguaje CSharp. Para un mejor encapsulamiento de código se implementaron tres métodos auxiliares:

· Ady: Recibe un punto como parámetro y devuelve una lista con los puntos látices adyacentes a él.

· EndCorner: Recibe un punto, el mapa y retorna un valor booleano indicador de si el punto es la esquina inferior derecha del mapa.

· InsideMap: Recibe un punto, el mapa y retorna un valor booleano indicador de si el punto está dentro del mapa.


Metodos auxiliares

static List Ady(Point p)

{

List res = new List();

for (int i = -1; i <= 1; i++)

for (int j = -1; j <= 1; j++)

if (i != j && i*j == 0)

res.Add(new Point(p.X + i, p.Y + j));

return res;

}

static bool EndCorner(int[,] map, Point p)

{

return p.X == map.GetLength(0) - 1 && p.Y == map.GetLength(1) - 1;

}

static bool InsideMap(int[,] map, Point p)

{

return p.X >= 0 && p.Y >= 0 && p.X <>

p.Y <>

}

Algoritmo de solución

static List Lee(int[,] map)

{

Queue q = new Queue();

// Marcar el comienzo

map[0, 0] = -1;

q.Enqueue(new Point(0, 0));

while (q.Count > 0)

{

Point cur = q.Dequeue();

foreach (Point p in Ady(cur))

// Si el punto no esta marcado

if (InsideMap(map, p) && map[p.X, p.Y] == 0)

{

// no se habia podido llegar en menos pasos y

// marcar con los pasos para llegar al

// anterior mas uno

map[p.X, p.Y] = map[cur.X, cur.Y] - 1;

// Si llegue a la esquina inferior derecha

if (EndCorner(map, p))

{

// Suspender la busqueda para pasar a

// reconstruir el camino

q.Clear();

break;

}

}

}

// Construir el camino

List path = new List();

Point end = new Point(map.GetLength(0) - 1,

map.GetLength(1) - 1);

// Si se llego a marcar la esquina inferior derecha

if (map[end.X, end.Y] != 0)

{

// Mientras end no sea la ezquina superior izquierda

while(map[end.X, end.Y] != -1)

{

// Buscar en los vecinos de end un punto al que se

// pueda llegar en 1 paso menos

foreach (Point p in Ady(end))

if (InsideMap(map, p) &&

map[p.X, p.Y] == map[end.X, end.Y] + 1)

{

path.Add(end);

end = p;

break;

}

}

// Adicionar el punto inicial

path.Add(new Point(0, 0));

// Obtener el camino en el orden correcto

path.Reverse();

}

return path;

}

Orden del Algoritmo

Para analizar el orden del algoritmo podemos separar su estructura en dos partes fundamentales:

· Marcar las casillas del mapa

· Construir el camino a partir del mapa marcado



Marcar las casillas del mapa

Para analizar el costo de esta operación es necesario cerciorarse de que las operaciones realizadas en el interior del ciclo while son constantes. Dentro del ciclo se itera sobre una colección de 8 elementos y por cada uno de estos se realizan operaciones O (1) . Luego el costo de esta operación viene dado por la cantidad de elementos que puede contener la cola utilizada para almacenar los nuevos puntos en el algoritmo. Dicha cola solo puede almacenar puntos del mapa por lo que la cantidad de elementos que pueden pertenecer a ella son O(n*m) donde n y m son respectivamente la cantidad de filas y columnas del mapa.

Construir el camino a partir del mapa marcado

Para construir el camino se realizan por cada punto intermedio del camino operaciones O(1) por lo que el costo de esta operación depende explícitamente de la longitud del camino. La longitud del camino esta acotada superiormente por la cantidad de casillas del tablero, que es O(n*m) .

Luego el costo de dar solución al problema es O(n*m) debido a que las dos partes fundamentales del mismo se realizan en este orden.

Correctitud del Algoritmode longitud p+k-i+1 < k lo que sería una contradicción. El vértice

Para mostrar la correctitud del problema demostraremos que el camino encontrado por el algoritmo es mínimo. Para ello haremos uso del método de reducción al absurdo. Sea v1,v2,v3...vk un camino del inicio al fin cuya longitud es menor a la del camino encontrado por el algoritmo. Además como este camino es menor que el obtenido por el algoritmo podemos garantizar que la esquina inferior derecha fue marcada con un número menor que -k. Todo vértice vi del camino mínimo tiene que haber sido marcado con el numero –i. Si fue marcado con uno mayor entonces existe un camino v1,v2,v3...vp,vi
con p < i-1 que parte desde el inicio hasta i, luego, podemos formar un camino v1,v2,v3...vp,vi,v(i+1),...vk de longitud p+k-i+1 < k lo que sería una contradicción. El vértice vk fue marcado con el numero –k lo cual es una contradicción. Luego la suposición inicial de que el camino era más corto no ha lugar.