Skyline de una ciudad

INDICE

1. DESCRIPCION ESQUEMA ALGORITMICO UTILIZADO ……………………………… pag 3.
2. ANALISIS COSTE COMPUTACIONAL ………………………………………………………..pag 5.
3. DATOS DE PRUEBAUTILIZADOS………………………………………………………………pag 7.
4. CODIGO FUENTE…………………………………………………………………………………….pag 9.




















1. DESCRIPCION ESQUEMA ALGORITMICO UTILIZADO

Este problema puede ser resueltomediante un algoritmo voraz, así como por el método divide y vencerás, como en el enunciado se especifica que ha de realizarse aplicando el esquema que tenga el menor coste computacional, optamos por lasolución mediante el método divide y vencerás.
El problema de encontrar el skyline de una ciudad se puede realizar mediante divide y vencerás, ya que el problema se puede descomponer en problemasmás pequeños y de idéntica naturaleza.
El enfoque, a priori, podría ser tanto dividir el número de edificios, como dividir el eje de las x, en la práctica se opta por dividir el número de edificios.Supongamos sin perder generalidad que n=2k y que elegimos dividir el problema en subproblemas de n/2, la solución de cada subproblema es una línea de horizonte, formada por una lista de puntos en elplano.
Cada subproblema nos proporciona una línea de horizonte, representada por una lista de puntos, la combinación de los subproblemas es recorrer ambas, y elegir en cada momento el punto de mayorordenada.
Por tanto, el problema se puede descomponer en subproblemas, estos subproblemas son independientes, el problema es suficientemente simple cuando n=1, las soluciones obtenidas para estossubproblemas se pueden combinar para obtener la solución.
Esto nos lleva a la conclusión de que el método divide y vencerás es válido para la resolución del problema del skyline.PASOS DE LA TECNICA:

1 División: plantear el problema de forma que pueda ser descompuesto en k subproblemas del
mismo tipo, pero de menor tamaño.


2...