Autor
|
Tema: Ejercicio de Universidad.. (Leído 10,577 veces)
|
$Edu$
Desconectado
Mensajes: 1.842
|
Pajaras, ahora que estas conectado.. cuando haras el tutorial que no he podido entender backtracking o no se que tengo mal xD
|
|
|
En línea
|
|
|
|
]_HQH_[
|
Este programa es tipico de ejemplo para quien se introduce en competiciones de programacion. Recuerda siempre que el nombre lo dice, back-tracking es recorrer al reves... Y al recorrerlo, si un paso ha costado mas que el anterior, no lo hagas. Aqui tienes información sobre algoritmica http://hispabyte.net/foro/index.php?board=92.0
|
|
|
En línea
|
|
|
|
$Edu$
Desconectado
Mensajes: 1.842
|
Si me puedes dar una mano te agradezco mucho, mira.. yo lo que primero hice fue que mi programa haga movimientos en sentido del reloj hasta que no haya mas solucion, entonces ahi vuelve una posicion atras y anota el movimiento que hizo la ultima vez, para repetir eso pero con el movimiento anterior. Despues me di cuenta que tendria problemas con eso, ya que despues que avanza ese mov anterior no lo cambio y haria un paso menos.
Entonces hice una lista de los movimientos y usaba solo el ultimo, pero tampoco funciono, entonces yo ahora uso un array multidimensional que voy a ir anotando los movimientos para cada numero de paso en su posicion en el tablero y el movimiento que hizo.
Pero me acabo de dar cuenta que haciendo otros movimientos se puede llegar al mismo numero y la misma posicion, entonces otra vez me caga todo :S
Si no me entiendes pregunta, aunque como ves estoy perdido y si me explicas desde 0 es mejor, espero que me ayudes ya que entre al foro q pasas y sobre el ejercicio este no habla pero hay otras cosas si y me cuesta mucho entender mirando codigo simplemente
|
|
|
En línea
|
|
|
|
Ragnarok
|
Lo más fácil es hacerlo con backtracking, como ya han dicho. http://es.wikipedia.org/wiki/BacktrackingEs mucho más eficiente hacerlo con restricciones: http://es.wikipedia.org/wiki/Programaci%C3%B3n_con_restriccionesEsto es el código del algoritmo de backtracking mejorado, hace BEP igual que bactracking, pero en cada bifurcación escoge el camino más prometedor dependiendo de la heurística que le pongas en lugar de escoger uno aleatoriamente. module MyBacktrac (backtracking) where import List
backtracking:: (tsolucionParcial -> tsolucionParcial -> Ordering) -- Ordenar para A* -> (tsolucionParcial -> Bool) -- EsSolucionFinal? -> (tsolucionParcial -> tsolucion) -- Convertir -> (tsolucionParcial -> [tsolucionParcial]) -- Ampliar -> (tsolucionParcial -> Bool) -- EsValida? -> [tsolucionParcial] -- Estado inicial -> Maybe tsolucion
backtracking _ _ _ _ _ [] = Nothing backtracking orden essolucion convertir ampliar esvalida (sp:sps) | essolucion sp = Just (convertir sp) | otherwise = (backtracking orden essolucion convertir ampliar esvalida) (sortBy orden ((filter esvalida (ampliar sp)) ++ sps))
|
|
|
En línea
|
|
|
|
$Edu$
Desconectado
Mensajes: 1.842
|
Sigo sin entender :S, no podrias decirme con palabras los pasos a seguir, q yo despues veo como lo implemento, pero siendo mas puntual claro
|
|
|
En línea
|
|
|
|
farresito
Desconectado
Mensajes: 302
|
|
|
|
En línea
|
|
|
|
$Edu$
Desconectado
Mensajes: 1.842
|
Pero veo que usa Random y la idea es no usar random, porque con random ya lo tengo, pero bueno.. esperare hasta la universidad, gracias a todos
|
|
|
En línea
|
|
|
|
|
|
|