Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión

 
Búsqueda Avanzada

15.707 Mensajes en 3.130 Temas- por 371 Usuarios - Último usuario: lasfirrot
Mayo 18, 2012, 05:21:45
Foro de Hispabyte.netProgramaciónCompeticiones de programación y algorítmicaTema: Backtracking recursivo
« anterior próximo »
Páginas: [1]   Ir Abajo
Imprimir
Autor Tema: Backtracking recursivo  (Leído 3133 veces)
0 Usuarios y 1 Visitante están viendo este tema.
SCoRPiT
Asiduo
***
Mensajes: 132



Ver Perfil WWW
« : Agosto 11, 2006, 08:16:49 »

Hola, necesito que alguien me explique, todo cuanto pueda, el algoritmo de backtracking ya que tengo que realizar un ejercicio y no lo tengo claro del todo, he estado buscando en internet pero lo ?nico que he conseguido ha sido liarme mas. No es necesario que me lo expliquen con ejemplos en java, ya que para implementarlo espero no tener problemas.

Salu2 y gracias  Cheesy


P.D: Aqui dejo el ejercicio por si alguien le interesa.
 
* bactracking.rar (3.85 KB - descargado 345 veces.)
En línea
<<{SCoRPiT}>>
"Lo que una mente crea otra lo supera"
"Entre dos hombres iguales en fuerza, el m?s fuerte es el que tiene raz?n." - Pit?goras
HQH
Administrator
Miembro Imprescindible
*****
Mensajes: 1.813



Ver Perfil
« Respuesta #1 : Agosto 13, 2006, 11:19:39 »
Este problema que planteas es igualito a uno de la ACM UVA

15-Puzzle Problem

http://acm.uva.es/p/v101/10181.html

La clave para resolverlo usando backtranking es simplemente probar todas las combinaciones posibles, sin repetirlas hasta que se encuentre una solucion.

Si ademas por el problema, se te exige un limite temporal y probando las soluciones no se cumple, probablemente tendras que hacer algun tipo de poda para evitar tener que probar determinadas combinaciones.

Tambien es importante tener en cuenta, que este tipo de puzzles pueden NO ser resolubles, cosa que sabras si no ha encontrado ninguna solucion al puzzle.

Basicamente eso es el backtraking, probar todas las combincaciones.

Un saludo.

PD: He movido el tema a Algoritmica
PD2: ?En que asignatura te han pedido el ejercio?  
« Última modificación: Agosto 13, 2006, 11:21:17 por ]_HQH_[ » En línea
SCoRPiT
Asiduo
***
Mensajes: 132



Ver Perfil WWW
« Respuesta #2 : Agosto 14, 2006, 11:17:17 »
Gracias por la info HQH, el ejercico me lo han pedido para unas practicas en Java de la asignatura Metodologia y Tecnologia de la Programacion.
Lo que creo es que el problema si que ha de tener al menos una solucion siempre, o al menos asi me ense?aron a mi para que se pueda aplicar backtracking, lo que puede ocurrir es que alguno de los caminos que eligas sea demasiado largo y por eso han puesto el limite de 50 movimientos.

Salu2 y gracias  Cheesy  
En línea
<<{SCoRPiT}>>
"Lo que una mente crea otra lo supera"
"Entre dos hombres iguales en fuerza, el m?s fuerte es el que tiene raz?n." - Pit?goras
Páginas: [1]   Ir Arriba
Imprimir
Foro de Hispabyte.netProgramaciónCompeticiones de programación y algorítmicaTema: Backtracking recursivo « anterior próximo »
Ir a:  


Tema diseñado por RJ-45 para Hispabyte.net basado en el
theme famouspadexx v.09 designed by Formado Comprido
Downloable here. My present to padexx.de