[ Foro de Pascal ]

Procedimiento recursivo (con backtracking)

Muy buenas,

Lo que pretendo es implementar un procedimiento recursivo en Pascal, que se encargue de "Colocar dos conjuntos a y b de bolas (a,b:integer) en 10 bloques de todas las maneras posibles. Con la peculiaridad de que entre los conjuntos a y b debe de haber almenos un bloque de por medio y en cada bloque solo se puede colocar una bola".

Esto es que si, tenemos por ejemplo a=2 y b=2, las bolas quedarían dispuestas así: (visionando el vector del resultado)

[a,a,0,b,b,0,0,0,0,0]
[a,a,0,0,b,b,0,0,0,0]
[a,a,0,0,0,b,b,0,0,0]
[a,a,0,0,0,0,b,b,0,0]
[a,a,0,0,0,0,0,b,b,0]
[a,a,0,0,0,0,0,0,b,b]
[0,a,a,0,b,b,0,0,0,0]

[etc].

Intento implementarlo pero el tema de la recursividad, y en este caso, el uso del Backtracking para generar todas las soluciones posibles me trae de cabeza ya que no me consigue aclarar las ideas.

Si alguien puede echarme una mano lo agradecería.

Gracias.

---

En principio, con esas limitaciones, al tener dos conjuntos de bolas distintos, quizá pudieras hacer con un bucle for anidado, algo como:

para cada posicionInic de grupoA entre 1 y 10
  para  cada posicionInic de grupoB entre 1 y 10
    si posicionValida escribir vectorActual

donde posicionValida comprobaría si realmente esa combinación es válida con los requisitos que te dan (por ejemplo, posIniA = 1 y posIniB = 1 no lo es, mientras que posIniA = 1 y posIniB = 4 sí lo es).

---

A través de bucles podría hacerlo. Pero como tengo que realizar todas las posibilidades posibles para una posibilidad de una fila con todas las de todas las columnas, la siguiente posibilidad de una fila con todas las de todas las columnas, etc etc, hasta comprobar todas las posibilidades de todas las filas con todas las posibilidades de todas las columnas, me puedo morir usando iteración.

Por eso necesito hacer un backtracking puro y duro. Dado que mi problema posee una sola solución única, y ésta se debe hacer comprobando TODAS las posibilidades entre filas y columnas de mi matriz.

Mi problema está en que no sé como generar todas las posibilidades de disposición de dos conjuntos disjuntos de dos bolas, en este caso, de todas las maneras posibles en una fila. Para que una vez que lo haya implementado, sea capaz de realizarlo para todas las filas y modificándolo para toda las columnas. Así conseguir mi solución única.

No obstante, puedo reducir casos del 'Árbol de posibilidades' generado por backtracking para que me sea más eficiente en tiempo. Pero primero necesito que me salga lo básico, que es mi problema mostrado.

Saludos.

---

Siento el retraso en contestar, pero he estado un poco desbordado.

No entendí tu problema original. Creía que sólo era una fila de 10 elementos lo que tenías que obtener, no una matriz cuadrada o rectangular... pero todavía no tengo claro qué solución tienes que mostrar.

El problema de recursión o iteración no es "que te puedas morir", sino que depende de lo que buscas. Si debes probar todas las soluciones posibles, y existe una forma iterativa de hacerlo, la solución iterativa será (en general) la más rápida y la que menos recursos consuma. La solución recursiva va generando un árbol de llamadas que consume muchos recursos, pero es la que te permite "podar" ramas cuando una solución parcial ya no es válida, y a veces (muchas) es la única forma posible de buscar la solución.

---

---