Barra de porcentaje, en backtracking "dinamico"

[shephiroth]

Buenas. En la universidad me han mandado un ejercicio de backtracking, y el ejercicio en si no es muy dificil, pero como soy un poco masoca quiero añadirle una barra de progreso informando de cuanto lleva hecho y cuanto le falta. El ejercicio en cuestion es en un tablero cuadrado (la dimension es modificable) dando una posicion inicial, buscar caminos de caballo para recorrer el tablero entero sin repetir celda.

Como ya he comentado el ejercicio en si no es dificil, ya lo tengo funcionando...pero la barra de porcentaje no me termina de encajar. Primero he precalculado los saltos validos que hay desde cada una de las celdas, pero como hay saltos que se invalidan cuando ya han sido utilizados, no se como calcular lo que seria el 100%

Algun consejo?

[CoLSoN2]

Para tu caso, teniendo en cuenta que a "velocidad de crucero" el algoritmo se ejecuta en un santiamén, podrías ejecutar el algoritmo sin mostrar nada por pantalla, y así sabrías exactamente cuántos pasos reales tienes que hacer. Luego en el segundo pase, que se realizaría con retrasos tras cada salto para que el espectador pueda ver lo que ocurre, puedes avanzar la barra de progreso en porciones de 1/(pasos reales) cada vez.

[tamat]

O sea, quieres una barra de porcentaje para un valor que no es fijo ni predecible, no creo que las barras de progreso se hicieran para eso, pero si quieres una solucion usa el numero de casillas maximas alcanzadas.

[shephiroth]

El ejercicio nos pide la resolucion para buscar una solucion, y para buscarlas todas.....para buscar una utilizo la barra como me comentas.....casilla_actual/casillas_totales......pero para el algoritmo de todas las soluciones me gustaría una barra tal que salto_intento_actual/salto_total_posibles

El caso es, que para el primer nivel puedo precalcular cuantos saltos va a ver (como el tablero esta vacio tiene sus 8 posibilidades), pero para proximos saltos, no se puede saltar donde ya hay un caballo. Y esto es exactamente lo que no se como incluir en el algoritmo....como eliminar los futuros saltos sobre casillas que estaran ocupadas (y por tanto eliminar las posibilidades de futuros saltos derivados de este).

Sobre la idea de hacer una pasada, y en una segunda empezar a dibujar....cuando en un tablero de 6*6, iniciando en 0,0 me dura mas de 5 horas el algoritmo (dibujando a cada solucion encontrada) dudo que pueda hacer una pasada para precalcular y otra dibujando xDD

[tamat]

yo no decía casilla_actual/casillas_totales, decía MAX_casilla_actual/casillas totales, así cada vez que haces backtracking se te queda el porcentaje fijo.

[gdl]

Generalmente al usuario le gusta más que la barra de progreso salte a que se quede estancada, por eso quizás sea interesante buscar una cota superior.

En cada salto el caballo puede ir a 8 posiciones, ¿verdad? Entonces, si no tenemos en cuenta la restricción esa, sería 8^N. Pero podemos afinar algo más diciendo que son 8 al principio y 1 al final... entonces sería algo como

8 * (8(N-1)/N) * ... * 8(1/N)

O sea,

N! * (8 / N)^N


A ver si eso te vale.

[shephiroth]

Es mas peliagudo aun de lo que crees. Tienes q tener en cuenta que en un tablero no todas las posiciones tienen 8 posibles saltos, solamente la matriz central (2,n-2)(2,n-2) son 8 posibilidades. Las esquinas solo son 2 posibilidades, las 2 casillas en vertical/horizontal de las esquinas son 3 posibilidades, la casilla en diagonal son 4, las casillas (0)(2,n-2) y (2,n-2)(0) son 4, y por ultimo las casillas (1)(2,n-2) y (2,n-2)(1) son 6 posibilidades.

He pensado en crear una matriz con esas posibilidades iniciales, y tratar su composicion como SALTOS_MAXIMOS, modificar dinamicamente (a cada salto efectivo que se haga, o cuando se deshaga un salto) de modo que en cualquier momento en el que no se pueda hacer un salto por estar ocupada la casilla pueda evaluar SALTOS_MAXIMOS-=composicion_actual pero no se si realizar tantas composiciones podría aumentar de forma exponencial el tiempo empleado.

[Zaelsius]

Algun consejo?

Ves a ver a tu profesor en horarios de tutoría. Si llegas a la revisión con un 4.5 lo mismo se acuerda de tí luego :D

[zxs]

Es mas peliagudo aun de lo que crees. Tienes q tener en cuenta que en un tablero no todas las posiciones tienen 8 posibles saltos, solamente la matriz central (2,n-2)(2,n-2) son 8 posibilidades. Las esquinas solo son 2 posibilidades, las 2 casillas en vertical/horizontal de las esquinas son 3 posibilidades, la casilla en diagonal son 4, las casillas (0)(2,n-2) y (2,n-2)(0) son 4, y por ultimo las casillas (1)(2,n-2) y (2,n-2)(1) son 6 posibilidades.

He pensado en crear una matriz con esas posibilidades iniciales, y tratar su composicion como SALTOS_MAXIMOS, modificar dinamicamente (a cada salto efectivo que se haga, o cuando se deshaga un salto) de modo que en cualquier momento en el que no se pueda hacer un salto por estar ocupada la casilla pueda evaluar SALTOS_MAXIMOS-=composicion_actual pero no se si realizar tantas composiciones podría aumentar de forma exponencial el tiempo empleado.

Esto me ha hecho recordar una cosa, pero ya la comentaré más tarde cuando haya más soluciones para este tema. Pues es una burrada burra burra burrísima que hizo mi compáñero de proyecto para algo parecido a esto en la asignatura de inteligencia artificial y lenguages formales hace ya 7 años, pero me acuerdo como si fuese hoy.

[shephiroth]

Buenas. Creo que he dado con la solucion. Elimina la dependencia de combinatoria, a costa de utilizar mas memoria, pero puede ser rentable.

A ver, tal como lo hacia hasta ahora precalculaba (al menos intentaba) la cantidad de saltos, contaba los saltos hechos y conseguia la proporcion. Pero ahora que lo pienso, me conviene incluir en la recursiva 2float.....porcentajeAnterior y porcentajeProporcionalEsteNivel. Basicamente, porcentajeAnterior mantiene el porcentaje completado por todos los niveles anteriores, porcentajeProporcionalEsteNivel indica cuanto porcentaje aumentara el nivel actual. La primera llamada estara con porcentajeActual=0.0 y porcentajeProporcionalEsteNivel=100.0. A la hora de llamar a subniveles lo unico que he de tener en cuenta es ir acumulando el porcentajeActual, y para el proporcional del siguiente sivel hacer porcentajeProporcionalEsteNivel/saltosPosiblesNivelActual.

De esta manera no tengo que preocuparme de cuando un salto no es posible pq ya esta ocupada, cuando vuelva el nivel "hacia atras" se reajustara el solo.

Si hay algun interesado cuando termine cuelgo codigo, q de seguro se ve mas facil (eso si no me salta un ExceptionStackOutOfRange o algo parecido)

GRACIAS a todos ^^