Lo que intento hacer en última instancia es encontrar la solución que maximiza una ecuación dada por lo que necesito encontrar todas las soluciones posibles para poder comprobarlas. Necesito todas las soluciones posibles de una $n \times n$ matriz, dados los totales de filas y columnas. Todos los valores deben ser no negativos. Aparte de eso, la fila y la suma de las columnas son las únicas restricciones.
Respuestas
¿Demasiados anuncios?
GmonC
Puntos
114
Podría ser interesante mencionar la Correspondencia de RSK (aunque podría no ser de suficiente ayuda si $n$ es realmente muy grande). Da una biyección algorítmica entre el conjunto de matrices enteras no negativas con sumas de columnas y filas $\alpha,\beta$ respectivamente (son vectores de enteros no negativos) y los pares $(P,Q)$ de igual forma semiclandestino Cuadros de jóvenes de los pesos respectivos $\alpha,\beta$ . Por lo tanto, el número de matrices viene dado por $$ \sum_\lambda K_{\lambda,\alpha}K_{\lambda,\beta} $$ donde $\lambda$ es una partición de $\sum\alpha=\sum\beta$ y $K_{\lambda,\alpha}$ es el número de tablas de Young semiestándar de forma $\lambda$ y el peso $\alpha$ que es un Número de Kostka . Esto al menos da un método para contar el número de matrices que es mucho más eficiente que enumerarlas todas (debido al producto en la fórmula y al hecho de que el $K_{\lambda,\alpha}$ son no negativos). No hay fórmulas realmente sencillas para calcular los números de Kostka, pero como son multiplicidades de pesos, hay una fórmula recursiva que los calcula de nuevo de forma mucho más eficiente que contando tablas de Young semiestándar.
jwarzech
Puntos
2769
En principio existe un procedimiento recursivo "eficiente" para generar todos los posibles enteros no negativos $n \times n$ matrices con sumas de filas y columnas prescritas ( tablas de contingencia ), pero hay que advertir que el número de estas soluciones puede ser enorme y difícil de estimar con precisión.
La generación más sencilla (pero todavía voluminosa) de $2 \times n$ tablas de contingencia es el tema de esta pregunta anterior y un problema más general con (esencialmente) $m \times k$ se debatió sobre las matrices aquí incluyendo un procedimiento de generación recursivo declarado de manera informal.
A menudo los autores contemplan el problema de la selección aleatoria de soluciones con probabilidad uniforme, pero aquí el objetivo declarado es una búsqueda exhaustiva/fuerza bruta para determinar una función objetivo maximizada. Si se supiera más sobre la estructura de esa función objetivo, probablemente se podrían encontrar algunos atajos prácticos (por ejemplo, explotando las simetrías del espacio de búsqueda).
La pregunta nos pide que generemos todas las matrices posibles con sumas de filas y columnas prescritas. Contarlas no tiene por qué preocuparnos directamente. Cualquier algoritmo que evite la duplicación o el ensayo-error innecesario es "eficiente". A continuación presentamos el código Prolog que implementa un algoritmo de este tipo, predicado contingencyTable/3 tomando como entrada dos listas, de sumas de filas y sumas de columnas respectivamente, y produciendo en el backtracking todas las posibles matrices enteras no negativas que satisfagan esas restricciones.
balanceCondition/2 Comprueba que los totales de las sumas de las filas y de las columnas coinciden, condición necesaria y suficiente para que existan soluciones.
generateTable/3 Seleccione las entradas no negativas para la primera fila (véase generateRow ) para que coincida con su suma de filas y reduzca las respectivas sumas de columnas (pero no a menos de cero). La "condición de equilibrio" se conserva, por lo que el procedimiento puede rellenar recursivamente la siguiente fila. Cuando queda una fila, la selección es única, y en ese momento la suma de las últimas sumas de columna reducidas es igual a la última suma de la fila.
generateRow/4 Las entradas de una fila también pueden seleccionarse de forma recursiva. La primera entrada de una fila tendrá dos límites inferiores y dos límites superiores. Mientras que uno de los límites inferiores es trivial (no negatividad), el otro es más sutil: asignar lo suficiente para que las sumas posteriores de las columnas no limiten la consecución de la suma de la fila. Ambos límites superiores son obvios; la entrada no puede superar la suma de filas o la suma de columnas cuando se selecciona la entrada. Una vez elegida una entrada dentro de los límites permitidos, reduzca la suma de la fila en consecuencia y aplique el mismo procedimiento al resto de la fila. La última entrada de la fila está determinada de forma única.
/*
Generate 2-way contingency tables with specified margins,
non-negative matrices with prescribed row & column sums.
*/
/* contingencyTable(+RowSums,+ColSums,?Table) */
contingencyTable(RowSums,ColSums,Table) :-
balanceCondition(RowSums,ColSums), /* feasible? */
generateTable(RowSums,ColSums,Table).
balanceCondition(RowSums,ColSums) :-
sum(RowSums,0,Total),
sum(ColSums,0,Total).
generateTable([_],ColSums,[ColSums]) :- !.
generateTable([RowSum|RowSums],ColSums,[Row|Rows]) :-
generateRow(RowSum,ColSums,ReducedColSums,Row),
generateTable(RowSums,ReducedColSums,Rows).
generateRow(RowSum,[ColSum],[ColRed],[RowSum]) :-
!,
ColRed is ColSum - RowSum.
generateRow(RowSum,[ColSum|ColSums],[ColRed|ColReds],[R|Rs]) :-
sum(ColSums,0,Sum),
(Sum > RowSum -> RMin = 0 ; RMin is RowSum - Sum),
(ColSum > RowSum -> RMax = RowSum ; RMax = ColSum),
between(RMin,RMax,R),
RowRed is RowSum - R,
ColRed is ColSum - R,
generateRow(RowRed,ColSums,ColReds,Rs).
/* helper predicates sum/3 and between/3 */
sum([ ],Sum,Sum).
sum([H|T],Start,Total) :-
SoFar is Start + H,
sum(T,SoFar,Total).
/* argument order compatible with SWI-Prolog builtin */
between(X,Z,X) :- X =< Z.
between(X,Z,_) :- X > Z, !, fail.
between(X,Z,K) :-
Y is X+1,
between(Y,Z,K).
