Problema De Algoritmos

Ronald Tucuman Alarcon

Algoritmos Avanzados – Ing. Sistemas - UMSS

Análisis de la resolución del problema “9.6.4 Slash Maze” del libro Programming Challenges.
Para la siguiente entrada,encontrar el ciclo con mayor cantidad de cuadritos. 64 \//\/ \///\/ //\/\ \/\/// A continuación se muestra la imagen de ejemplo que nos da el libro para esa entrada.

Claramente se pueden ver dos ciclos,uno grande compuesto de 16 cuadritos remarcados con círculos grises y el segundo de 4 cuadritos. Ahora cambiemos un poco la imagen de ejemplo, de manera que nos sea más fácil abstraerla.

Aunque nose puede diferenciar con claridad los cuadritos involucrados en el problema, se tiene otro punto de referencia. Son las intersecciones de las líneas de la cuadricula sobre la que se dibujó la entrada.Como se muestra a continuación. 1

Ronald Tucuman Alarcon

Algoritmos Avanzados – Ing. Sistemas - UMSS

¿Pero como sabemos cuántos vértices dibujar? Desde el punto de vista de una matrix y conla primera línea de entrada que nos dieron, tenemos. Para el número de columnas tomamos el primer número entero que lo denominamos w = 6: numColumnas = (w -1) * 2 + 3 = 13 Para el número de filastomamos el segundo número entero que lo denominamos h = 4: numFilas = (h -1) * 2 + 3 = 9 En la siguiente imagen se muestra los vértices usados para dibujar las líneas de entrada pintadas de color verde,tomando en cuenta que para dibujar una línea de entrada se necesita solo dos vértices.

¿Cómo dibujamos una línea de entrada ya sea “/” o “\” en nuestra matrix? Primero necesitamos coordenadas o ennuestro caso posiciones de la matrix. Se hizo el siguiente análisis.

2

Ronald Tucuman Alarcon

Algoritmos Avanzados – Ing. Sistemas - UMSS

Antes de empezar debemos fijar algunosestándares. Los vértices útiles para dibujar las líneas de entrada, de ahora en adelante serán de color verde. Las líneas de entrada de color verde claro. Los vértices que formaran parte del grafo solución...