Informe Trabajo Prctico de Programacin Dinmica y Greedy: Fernndez, Agustin - Canut, Iker October 22, 2019

Informe Trabajo Prctico de Programacin Dinmica y Greedy
Fernndez, Agustin - Canut, Iker

October 22, 2019
1
1 Greedy
1.1 Introduccin
Dado un tablero de ajedrez y una casilla inicial, queremos decidir si es posible que un caballo recorra todos y cada
uno de los escaques sin duplicar ninguno.
No es necesario en este problema que el caballo vuelva al escaque de partida.
1.2 Fuerza Bruta

Existen muchos caminos posibles, y la complejidad crece con el tamao del tablero. Para tener una idea, en un
tablero 6x6 existen 9862 ciclos cerrados, y 26,534,728,821,064 en uno 8x8...
Y esto es contando nicamente los cerrados, si tenemos en cuenta los abiertos, que es lo que se plantea, hay muchos
ms...
1.3 La regla de Warnsdorff

Warnsdorff plantea una heurstica, un algoritmo greedy, que decide mover el caballo a la casilla desde la cual domina
el menor nmero posible de casillas an no visitadas.
Por ejemplo, si el caballo comienza en el casillero (3, 7) de un tablero 8x8, se decidir mover a la casilla (1, 8),
porque domina un solo escaque, el (2, 6). Recordar que el casillero (3, 7) ya no es uno vlido.
1.4 Empates
Hay muchas formas de decidir que hacer en el caso de empates.
1. RANDOM: Una posibilidad, que es la que implementa Warnsdorff, es elegir un casillero random cuando
hay empates. Esto hace que eventualmente hayan errores.
2. PREDETERMINADOS: sta es la opcion que se implement. El orden de prioridad, totalmente arbitrario,

es el siguiente:
2 6
4 8
3 7
1 5
Como se dijo anteriormente, esto puede dar lugar a errores. A continuacin se marcan en verde las casillas
donde el algoritmo, siguiendo el orden marcado anteriormente, encuentra un camino vlido.
2
Claramente, las casillas pintadas en amarillo, tambin son vlidas. Y se puede demostrar girando el tablero, ya
que ahi si se encuentra un camino.
3. Propuesta de Arnd Roth: Roth busca romper los empates buscando el sucesor que est a mayor distancia
del centro del tablero. La primera falla aparece en un tablero de 428 filas, y los errores representan menos
del 1% en tableros con menos de 2000 filas.
4. Propuesta de Ira Pohl: Pohl decidi romper los empates aplicando la regla de Warnsdorff una segunda
vez. Es decir, comenzando en los casilleros que empataron, fijndose cual tiene menos dominio sobre el tablero
(sumando las posibilidades). Esto puede representar una bsqueda innecesariamente exhaustiva, y en un caso
bsico, como es empezar en una esquina, donde reina la simetra, tiene problemas.
1.5 Anlisis de Patrones

• NxN, ∀ N Impar: En un tablero de NxN, donde N es impar, la cantidad de casilleros en impar. Ergo
hay mas casilleros de un color que de otro. Sabiendo esto, por un simple tema de coloreo, se hace imposible
encontrar un camino (abierto o cerrado), que empiece en una casilla perteneciente al grupo de menor tamao.
• NxN, ∀ N Par: En el caso de que N sea par, no son necesarias las optimizaciones, de Roth ni de Pohl,
para encontrar caminos vlidos. En todos los casilleros con N par, desde cualquier celda se puede encontrar
un camino nicamente aplicando la heurstica de Warnsdorff.
3
1.6 Implementacin en Haskell
Comenzamos con funciones simples:
pertenece x [] = []
pertenece x ( y : ys ) = if ( x == y ) then [ x ] else pertenece x ys
makeSet n = [( j , i ) | j <- [1.. n ] , i <- [1.. n ]]
quitarElemento x [] = error " I n t e n t a n d o _ s a c a r _ e l e m e n t o _ d e _ l i s t a _ v a c i a "

quitarElemento x ( y : ys ) = if ( x == y ) then ys else y : quitarElemento x ys
makeSet 5
> [(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,2),(2,3),(2,4),(2,5),(3,1),(3,2),(3,3),(3,4),(3,5),
(4,1),(4,2),(4,3),(4,4),(4,5),(5,1),(5,2),(5,3),(5,4),(5,5)]
en u m e r a r P o s i bili dades (x , y ) posibilidades =
pertenece (x -1 , y -2) posibilidades ++
pertenece (x -1 , y +2) posibilidades ++
pertenece (x -2 , y -1) posibilidades ++
pertenece (x -2 , y +1) posibilidades ++
pertenece ( x +1 , y -2) posibilidades ++
pertenece ( x +1 , y +2) posibilidades ++
pertenece ( x +2 , y -1) posibilidades ++
pertenece ( x +2 , y +1) posibilidades
enumerarPosibilidades (3,3) (makeSet 5)
> [(2,1),(2,5),(1,2),(1,4),(4,1),(4,5),(5,2),(5,4)]
Luego hay una funcin un poco mas larga que se llama menorElemento, que tiene el siguiente formato:
menorElemento casillerosDondePuedeEstarElCaballo restoDelTablero =
casilleroConMenorDominio
1 1
3 3
3 3
en u m e r a r P o s i bili dades (3 ,4) ( makeSet 5)
> [(2,2),(1,3),(1,5),(4,2),(5,3),(5,5)]
menorElemento ( enum erarP osib ilid ades (3 ,4) ( makeSet 5)) ( makeSet 5)
> (1,5)
4
El resto es armar un Loop que vaya seleccionando la casilla con menor dominio, y aplicando las funciones que
vimos antes de manera recursiva, sacando los casilleros que se visitan y guardando en un array las casillas visitadas.
loop casilla [] = []
loop casilla posibilidades = casilla : loop
( menorElemento ( enum erar Posib ilid ades casilla posibilidades ) posibilidades )
( quitarElemento casilla posibilidades )
Para dejar linda la llamada inicial, se creo una funcion llamada game que se encarga de los preparativos:
game casillaInicial anchoTablero =
if ( length ( loop casillaInicial ( makeSet anchoTablero )) ==
length ( makeSet anchoTablero ))
then ( loop casillaInicial ( makeSet anchoTablero ))
else error " No_se_puede_armar "
Si el recorrido que devuelve tiene el mismo tamao que casillas en el tablero, se visitaron todas las casillas.
game (3,3) 5
>[(3,3),(2,1),(1,3),(2,5),(4,4),(5,2),(3,1),(1,2),(2,4),(4,5),(5,3),
(4,1),(2,2),(1,4),(3,5),(5,4),(4,2),(3,4),(1,5),(2,3),(1,1),(3,2),(5,1),(4,3),(5,5)]
game (5,3) 11
>[(5,3),(4,1),(2,2),(1,4),(2,6),(1,8),(2,10),(4,11),(6,10),(8,11),(10,10),(11,8),(10,6),
(11,4),(10,2),(8,1),(6,2),(4,3),(3,1),(1,2),(2,4),(1,6),(2,8),(1,10),(3,11),(4,9),(5,11),
(3,10),(1,11),(2,9),(1,7),(2,5),(1,3),(2,1),(3,3),(4,5),(3,7),(5,8),(4,10),(2,11),(1,9),
(3,8),(4,6),(3,4),(1,5),(2,7),(3,9),(5,10),(7,11),(6,9),(4,8),(3,6),(5,7),(6,5),(4,4),(3,2),
(1,1),(2,3),(3,5),(4,7),(5,5),(6,7),(5,9),(6,11),(7,9),(9,10),(11,11),(10,9),(9,11),(11,10),
(10,8),(8,9),(7,7),(5,6),(6,8),(7,10),(8,8),(7,6),(6,4),(5,2),(7,1),(8,3),(9,1),(11,2),(10,4),
(11,6),(9,7),(8,5),(7,3),(6,1),(4,2),(5,4),(6,6),(7,8),(8,10),(10,11),(9,9),(8,7),(7,5),(6,3),
(5,1),(7,2),(9,3),(10,1),(8,2),(7,4),(9,5),(10,3),(11,1),(9,2),(8,4),(9,6),(11,5),(10,7),(11,9),
(9,8),(11,7),(10,5),(8,6),(9,4),(11,3)]
menorElemento [] posibilidades = error " NO SE PUEDE ARMAR UN CAMINO "

menorElemento [ x ] posibilidades = if ( length ( enum erarP osib ilida des x posibilidades ) == 0)
then error " NO SE PUEDE ARMAR UN CAMINO "
else x
menorElemento ( x : y : zs ) posibilidades =
if ( length ( en umer arPos ibil idade s x posibilidades ) == 0
&& length ( en umer arPos ibil idade s y posibilidades ) == 0)
then error " NO SE PUEDE ARMAR UN CAMINO "
else if ( length ( en umer arPos ibil idade s x posibilidades ) == 0)
then menorElemento ( y : zs ) posibilidades
else if ( length ( en umer arPos ibil idade s y posibilidades ) == 0)
then menorElemento ( x : zs ) posibilidades
else if
( length ( enum erar Posib ilid ades x posibilidades ) <=
length ( en umer arPos ibil idade s y posibilidades ))
then menorElemento ( x : zs ) posibilidades
else menorElemento ( y : zs ) posibilidades
5
2 Programacin Dinmica
2.1 Introduccin
Se quiere encontrar una parentizacin apropiada para maximizar el valor de la siguiente expresin:
x1 /x2 /x3 .../xn−1 /xn
donde x1 , x2 , x3 , ..., xn son numeros naturales positivos y / denota la divisin.
2.2 Fuerza Bruta

En este problema, para probar todas las parentizaciones posibles se requieren 2(n−1) operaciones. Lo mismo resulta
absurdo cuando n crece, entonces deja de ser una opcin vlida.
2.3 Conceptos
Dada una parentizacin completa (P1..n ), la funcin c evaludada en P1..n es el resultado de aplicar las divisiones segn
la parentizacin. Una parentizacin optima de una expresin ser la que maximice la funcin c.
Una parentizacin completa P1..n de la expresin X1..n contiene dos parentizaciones completas P1..k y Pk+1..n de las
subsecuencias X1..k y Xk+1..n ∀ 1 ≤ k ≤ n − 1. Esto se cumple recursivamente.
2.4 Propiedad
Se cumple la siguiente propiedad:
c(P 1..n) = c(P 1..k)/c(P k + 1..n)

De aqui resulta que cualquier parentizacin maximal P1..n estar formada por una parentizacin P1..k que maximice
c(P1..k ) y una parentizacion Pk+1..n que minimice c(Pk+1..n ). Es decir, maximizar el numerador y minimizar el
denominador recursivamente.
2.5 Otras Funciones

• M (i, j) es el costo de una parentizacin Pi..j que maximice la funcin costo de la subsecuencia Xi..j .
Con 1 ≤ i ≤ j ≤ n.
• m(i, j) es el costo de una parentizacin Pi..j que minimice la funcin costo de la subsecuencia Xi..j .
Con 1 ≤ i ≤ j ≤ n.
Resulta que:
• si i = j entonces M (i, j) = m(i, j) = xi

M (i,k)
• si i < j entonces M (i, j) = max( m(k+1,j) ) con i ≤ k < j
• si i < j entonces m(i, j) = min( Mm(i,k)

(k+1,j) ) con i ≤ k < j
2.6 Cdigo en Imperativo

int chaindivision ( x1 , x2 ,.. , xn ) {
for ( i =1; i <= n ; i ++){
m [ i ][ i ] = xi
M [ i ][ i ] = xi
}
for ( l =2; l <= n ; l ++) {
for ( i =1; i <( n - l +1); i ++) {
j = ( i + l - 1);
M [i , j ] = 0;
m [i , j ] = -1; // INFINITE
}
for ( k = i ; k <( j -1); k ++) {
6
t1 = M [ i ][ k ] / m [ k +1][ j ];
t2 = m [ i ][ k ] / M [ k +1][ j ];
if ( M [ i ][ j ] < t1 )
M [ i ][ j ] = t1 ;
if ( m [ i ][ j ] > t2 )
m [ i ][ j ] = t2 ;
}
}
return M [1][ n ]
}

Informe Trabajo Prctico de Programacin Dinmica y Greedy: Fernndez, Agustin - Canut, Iker October 22, 2019

Cargado por

Copyright:

Formatos disponibles

Informe Trabajo Prctico de Programacin Dinmica y Greedy: Fernndez, Agustin - Canut, Iker October 22, 2019

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Informe Trabajo Prctico de Programacin Dinmica y Greedy: Fernndez, Agustin - Canut, Iker October 22, 2019

Cargado por

Copyright:

Formatos disponibles

Informe Trabajo Prctico de Programacin Dinmica y Greedy

Fernndez, Agustin - Canut, Iker

1.2 Fuerza Bruta

1.3 La regla de Warnsdorff

2. PREDETERMINADOS: sta es la opcion que se implement. El orden de prioridad, totalmente arbitrario,

1.5 Anlisis de Patrones

makeSet n = [( j , i ) | j <- [1.. n ] , i <- [1.. n ]]

quitarElemento x [] = error " I n t e n t a n d o _ s a c a r _ e l e m e n t o _ d e _ l i s t a _ v a c i a "

en u m e r a r P o s i bili dades (3 ,4) ( makeSet 5)

menorElemento [] posibilidades = error " NO SE PUEDE ARMAR UN CAMINO "

2.2 Fuerza Bruta

c(P 1..n) = c(P 1..k)/c(P k + 1..n)

2.5 Otras Funciones

• si i = j entonces M (i, j) = m(i, j) = xi

• si i < j entonces m(i, j) = min( Mm(i,k)

2.6 Cdigo en Imperativo

También podría gustarte