Mi problema es el siguiente:
Tengo un grupo de n cursos
Cada curso tiene varias lineas horarias de dictado
Se desea encontrar o saber la forma de elegir un horario de tal forma que el alumno se inscriba en la mayor cantidad de cursos
Para ello se desea utilizar el algoritmo de backtracking
Para esto partimos del ejemplo básico:
Tenemos 3 cursos:curso1,curso2,curso3 con sus respectivas lineas horarias
curso1{'a','b','c'} curso1 tiene la linea horaria 'a', linea horaria 'b', linea horaria 'c'
curso2{'D','E'} curso2 tiene la linea horaria 'D', linea horaria 'E'
curso3{'1','2','3'} curso3 tiene la linea horaria '1', linea horaria '2', linea horaria '3'
se desea conseguir todas las combinaciones de los cursos para ello se sigue el siguiente algoritmo
0
// \\
// \\
// \\
// \\
curso1 V F
// \\ // \\
curso2 V F V F
// \\ // \\ // \\ // \\
V F V F V F V F
1 2 3 4 5 6 7 8
El algoritmo buscaria por profundidad llegaria primero al nodo 1(V,V,V) que implica {curso1,curso2,curso3}, luego ira al nodo2(V,V,F) que implica {curso1,curso2} y
asi sucesivamente. Para eso he utilizado el algoritmo que está en la pagina 187(Construir todos los subconjuntos) del link http://acm.uva.es/p/jorgeteran.pdf
La cuestion es al llegar al nodo 1 debe empezar otra ramificación para empezar la combinación de lineas horarias(Ahí es donde les solicito su ayuda).
Para el Nodo 1 se formaria un arbol que llegaria a 18 nodos los cuales serian en el orden siguiente:
{'a', 'D', '1'}
{'a', 'D', '2'}
{'a', 'D', '3'}
{'a', 'E', '1'}
{'a', 'E', '2'}
{'a', 'E', '3'}
{'b', 'D', '1'}
{'b', 'D', '2'}
{'b', 'D', '3'}
{'b', 'E', '1'}
{'b', 'E', '2'}
{'b', 'E', '3'}
{'c', 'D', '1'}
{'c', 'D', '2'}
{'c', 'D', '3'}
{'c', 'E', '1'}
{'c', 'E', '2'}
{'c', 'E', '3'}
Para el Nodo 2 como implica solo las lineas horarias de los cursos1 y curso2 sería
{'a', 'D'}
{'a', 'E'}
{'b', 'D'}
{'b', 'E'}
{'c', 'D'}
{'c', 'E'}
He acomodado la clase que se muestra en http://acm.uva.es/p/jorgeteran.pdf
de tal forma que está si muestra todos los nodos finales(combinaciones de lineas horarias que se puede formar con los cursos)
el problema es que no es en el orden correcto que se requiere. Ahi adjunto el código para ver quien me ayuda a q éste algoritmo siga el orden correcto que debe seguir.
public class SubconjuntosX {
List<Object[]> conjuntos;
public SubconjuntosX(List<Object[]> conjuntos) {
this.conjuntos = conjuntos;
Object[][] presente = new Object[conjuntos.size()][2];
for(int i = 0; i < conjuntos.size(); i++)
{
presente[i][0] = false;
presente[i][1] = new boolean[conjuntos.get(i).length];
}
// Inicialmente conjuntos esta todo en false
imprimeSubconjuntos(presente, 0);
}
private void procesarSolucion(Object[][] presente) {
// imprimir la solucion,
// conjuntos indica cuales imprimir
List<Object> subconjuntos = new ArrayList<Object>();
for (int i = 0; i < presente.length; i++)
{
if (Boolean.parseBoolean(presente[i][0].toString()))
{
boolean[] presente1 = (boolean[])presente[i][1];
for(int j = 0; j < presente1.length; j++)
{
if(presente1[j])
subconjuntos.add(conjuntos.get(i)[j]);
}
}
}
System.out.println(subconjuntos);
}
private void imprimeSubconjuntos(Object[][] presente,int posicionActual)
{
if(presente.length == posicionActual)
{
procesarSolucion(presente);
}
else
{
presente[posicionActual][0] = true;
// procesar una nueva solucion
for(int i = 0; i < conjuntos.get(posicionActual).length; i++)
{
boolean[] presente1 = new boolean[conjuntos.get(posicionActual).length];
presente1[i] = true;
presente[posicionActual][1] = presente1;
imprimeSubconjuntos(presente, posicionActual + 1);
}
// retornar (bactrack) al caso anterior
presente[posicionActual][0] = false;
// procesar una nueva solucion
imprimeSubconjuntos(presente, posicionActual + 1);
}
}
}
Y asi es como la llamo:
List<Object[]> conjunto = new ArrayList<Object[]>();
Object[] object1 = {'a','b','c'};
Object[] object2 = {'D','E'};
Object[] object3 = {'1','2','3'};
conjunto.add(object1);
conjunto.add(object2);
conjunto.add(object3);
SubconjuntosX subconjuntos = new SubconjuntosX(conjunto);
