viernes, 22 de mayo de 2009

Problema1 de Diseño de Analisis y Algoritmos

Considere n cuerdas en un círculo y cada una definida por sus puntos extremos. Diseñe un algoritmo de tiempo O(n log n) que determine el número de pares de cuerdas que se intersecan dentro del círculo. Asuma que ningún par de cuerdas tienen un extremo común.


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

• Ordenar los extremos de las cuerdas bajo algún criterio
• Etiquetar todos las cuerdas con un ID único que las identifique de todas las demás y que ese ID se le asigne según el orden de sus extremos. En otras palabras las cuerdas con extremos de menores recibirán IDs menores.
• Recorrer los extremos ordenados y utilizando una estructura de datos que almacene una lista ordenada eficientemente, mantener en ella todas las cuerdas que hasta el momento permanecen abiertas (se ha iterado por un solo extremo de la cuerda).
• Cuando se encuentre el segundo extremo de la cuerda se cuenta cuantas cuerdas se han abierto después de la inserción del primer extremo.


Criterio de orden para los extremos

El criterio para ordenar los extremos es sencillo. Primero cambiaremos las referencias de las cuerdas: En vez de tomar una cuerda como un par de puntos del plano tomaremos las referencias donde a es el ángulo formado por el eje positivo de las X y el vector u, análogamente b es el ángulo formado por el eje positivo de las X y el vector v. El ángulo se escoge siempre en sentido antihorario. Es fácil ver que en esta notación la cuerda también queda unívocamente determinada.
Luego una vez establecido que es lo que se va a entender por cuerda el criterio de ordenación a utilizar es el usual de los reales ya que los extremos de la cuerda no son pares ordenados sino son ángulos.


Algoritmo de Solución

En nuestro algoritmo de solución hacemos uso de las colecciones brindadas por CSharp tales como:
• SortedList: Estructura de datos que almacena pares de y se pueden recuperar tanto el índice de la llave en la lista de ordenada llaves como el valor asociado a una llave en . Esta estructura se puede implementar utilizando un ABB que tenga definida una estrategia para mantener sus alturas en O(log n). Tomamos como criterio de ordenación la llave, y dado el tipo de árbol utilizado aseguramos que las operaciones de de inserción, eliminación y búsqueda de un elemento dado su llave son O(log n). Las operaciones de indexado de una llave dentro de la lista ordenada de llaves también serían O(log n), para ello necesitamos en cada nodo un nuevo campo para almacenar la cantidad de nodos hijos que este posee. La actualización de este campo puede realizarse dentro de las operaciones de inserción y eliminación en O(1). Para conocer que índice ocupa una llave dentro de la lista ordenada de llaves bastaría descender por las ramas, teniendo en cuenta en cada paso que cada decisión de descender por un hijo derecho aumenta el índice del elemento buscado en la cantidad de nodos que posee el hijo izquierdo, cero si no existe este. Con esta estrategia, todas las operaciones requeridas se mantienen O(log n).
• List: Es una lista genérica que es utilizada para ordenar en los extremos (llamado al método Sort()).

Clases utilizadas en el algoritmo de solucion

class Chord
{
// Extremo 1 de la cuerda
public float A { get; set; }
// Extremo 2 de la cuerda
public float B { get; set; }
// Etiqueta de la cuerda
public int Tag { get; set; }
public Chord(float a, float b, int tag)
{
A = a;
B = b;
Tag = tag;
}
public Chord(float a, float b) : this(a, b, 0) { }
}

class Entry : IComparable
{
// Cuerda
public Chord Chord { get; set; }
// Extremo de la cuerda a tomar como llave en la ordenacion
public float Key { get; set; }
public Entry(float key, Chord cuerda)
{
Key = key;
Chord = cuerda;
}

public int CompareTo(Entry other)
{
return Key.CompareTo(other.Key);
}
}

Algoritmo de solución
static public int Solve(List col)
{
// Contador de intersecciones
int hit = 0;
// Colección ordenada según los extremos
List entries = new List();
for (int k = 0; k < col.Count; k++) { // Asignar etiquetas a las cuerdas col[k].Tag = -1; // Agregar extremos de la cuerda entries.Add(new Entry(col[k].A, col[k])); entries.Add(new Entry(col[k].B, col[k])); } // Ordenar los extremos entries.Sort(); // Contar interseccionnes SortedList open = new SortedList();
// Variable para asignar las etiquetas en orden
int tag = 0;
foreach (Entry e in entries)
{
if (e.Chord.Tag == -1)
{
// Primer extremo de la cuerda
open.Add(tag, e.Chord);
// Asignar una nueva etiqueta en orden
e.Chord.Tag = tag++;
}
else
{
// Extremo final de la cuerda
int index = open.IndexOfKey(e.Chord.Tag);
// Contar las intersecciones con esta cuerda
hit += open.Count - index - 1;
// Eliminarla de la lista de cuerdas abiertas
open.RemoveAt(index);
}
}
return hit;
}

Orden del Algoritmo

Debido a la concepción del algoritmo podemos separarlo en las siguientes operaciones.
• Ordenar los extremos de los segmentos.
• Recorrer la colección ordenada y contar las intersecciones con cada cuerda.
Ordenar los extremos de los segmentos: Son operaciones de comparación que se resuelven en O(1) ya que son entre números. El costo de la operación de ordenación es en su caso promedio O(2n log(2n))donde n es la cantidad de cuerdas pasadas al algoritmo (2n: es la cantidad de extremos).

Recorrer la colección ordenada y contar las intersecciones con cada cuerda: En cada iteración se realiza o bien una eliminación o bien una inserción sobre la colección que almacena las cuerdas abiertas. Estas operaciones son O(log n).Por tanto el costo del conteo es O(2n log n)
Resumiendo el costo de las partes del algoritmo podemos concluir que es O (n log n)

Correctitud del Algoritmo

Para demostrar la Correctitud del algoritmo demostramos en primer lugar que no cuenta intersecciones entre cuerdas que no existen y en una segunda demostración que ninguna intersección se queda sin contar. Esta estrategia de demostración nos garantiza que nuestro algoritmo no solo cuenta intersecciones que existen sino que también las cuenta todas. Para las demostraciones dividiremos las cuerdas en 3 tipos con respecto a una cuerda prefijada.
I. Son las cuerdas que terminan antes que el extremo final de la cuerda dada.
II. Son las cuerdas que comienzan antes que extremo inicial o después del extremo final y terminan después que el extremo final de la cuerda dada.
III. Son las cuerdas que comienzan después del extremo inicial de la cuerda dada y terminan después de su extremo final.



Cuenta solo las intersecciones existentes
Está claro que si tomamos como referencia la cuerda que vamos a contar las intersecciones solo realmente la intersecan las cuerdas de tipo III. Nuestro algoritmo no cuenta las cuerdas de tipo:
I. Debido a que cuando aparezca el extremo final de nuestra cuerda ya las cuerdas de este tipo han sido removidas de la colección de cuerdas abiertas.
II. Debido a que sus dos extremos son mayores que los extremos de la cuerda dada y cuando aparezca el extremo final de nuestra cuerda todavía las cuerdas de este tipo no han sido insertadas en la colección de cuerdas abiertas o porque la cuerda comenzó antes que la cuerda dada y tampoco se tendrá en cuenta.
Luego nuestro algoritmo solo cuenta cuerdas de tipo III que son las que producen intersecciones. Además podemos asegurar que no cuenta doble una intersección debido que la cuerda dada es una cuerda de tipo I si prefijamos cualquier cuerda de tipo III.

Todas las intersecciones son contadas
Toda intersección entre cuerdas se puede definir por las cuerdas que la generan. Luego para la cuerda que tiene el extremo menor la otra cuerda es de tipo III por lo que nuestro algoritmo siempre la va a contar.

No hay comentarios:

Publicar un comentario