¿Ordenar una matriz 2D binaria?

Question

Estoy buscando algunos punteros aquí, ya que no sé por dónde empezar a investigar este.

que tienen una matriz 2D con 0 o 1 de cada célula, tales como:

1 2 3 4 
A 0 1 1 0 
B 1 1 1 0 
C 0 1 0 0 
D 1 1 0 0 

y me gustaría a solucionar el problema por lo que es como "triangular superior" como sea posible, de este modo:

4 3 1 2 
B 0 1 1 1 
A 0 1 0 1 
D 0 0 1 1 
C 0 0 0 1 

Las filas y columnas deben permanecer intactas, es decir, los elementos no se pueden mover individualmente y solo se pueden intercambiar "enteros".

entiendo que probablemente habrá casos patológicos en una matriz tiene varios posibles resultados ordenados (es decir, misma forma, pero difieren en la identidad de las filas/columnas "originales".)

Por lo tanto, puede alguien sugiero dónde podría encontrar algunos puntos de partida para esto? Una biblioteca/algoritmo existente sería genial, ¡pero me conformaré con saber el nombre del problema que trato de resolver!

Dudo que sea un problema de álgebra lineal como tal, y tal vez haya algún tipo de técnica de procesamiento de imágenes que sea aplicable.

Cualquier otra idea aparte, mi conjetura inicial es sólo para escribir un simple tipo de inserción en las filas, a continuación, las columnas y que iterar hasta que se estabilice (y espero que la detección de los casos patológicos no es demasiado difícil.)

Más detalles: Más información sobre lo que estoy tratando de hacer puede ayudar a aclarar. Cada fila representa un competidor, cada columna representa un desafío. Cada 1 o 0 representa "éxito" para el competidor en un desafío particular.

Al ordenar la matriz para que todos los 1s estén en la esquina superior derecha, espero proporcionar una clasificación de la dificultad intrínseca de cada desafío y una clasificación de los competidores (que tendrá en cuenta la dificultad de los desafíos que tenido éxito en, no sólo el número de aciertos)

Nota sobre la respuesta aceptada:. he aceptado recocido simulado como "la respuesta", con la salvedad de que esta pregunta no tiene una respuesta correcta. Parece un buen enfoque, aunque no he logrado encontrar una función de puntuación que funcione para mi problema.

Answer 1

Un algoritmo basado en simulated annealing puede manejar este tipo de cosas sin demasiado problema. No es genial si tienes matrices pequeñas que probablemente tengan una solución fija, pero es genial si tus matrices se vuelven más grandes y el problema se vuelve más difícil.

(Sin embargo, también falla su deseo de que las inserciones se pueden realizar de forma incremental.)

Preliminares

1. idear una función de rendimiento que las "puntuaciones" una matriz - matrices que están más cerca su triángulo debería obtener una mejor puntuación que aquellos que son menos triángulo-y.

2. Diseña un conjunto de operaciones que son permitidas en la matriz. Su descripción fue un poco ambigua, pero si puede cambiar las filas, entonces una operación sería SwapRows(a, b). Otro podría ser SwapCols(a, b).

El bucle de recocido

No voy a dar una exposición completa aquí, pero la idea es simple. Realiza transformaciones aleatorias en la matriz usando sus operaciones. Usted mide cuánto "mejor" es la matriz después de la operación (usando la función de rendimiento antes y después de la operación). Entonces decides si comprometer esa transformación. Repite este proceso mucho.

Decidir si confirmar la transformación es la parte divertida: debe decidir si realizar esa operación o no. Hacia el final del proceso de recocido, solo acepta transformaciones que mejoraron el puntaje de la matriz. Pero antes, en un momento más caótico, permites transformaciones que no mejoran el puntaje. Al principio, el algoritmo está "caliente" y todo vale. Eventualmente, el algoritmo se enfría y solo se permiten buenas transformaciones. Si linealmente fresco del algoritmo, entonces la elección de si se debe aceptar una transformación es:

public bool ShouldAccept(double cost, double temperature, Random random) { 
    return Math.Exp(-cost/temperature) > random.NextDouble(); 
} 

usted debe leer la información relevante contenida en Numerical Recipes para más información sobre este algoritmo.

historia larga corta, debe aprender algunos de estos algoritmos de propósito general. Hacerlo le permitirá resolver grandes clases de problemas que son difíciles de resolver analíticamente.

algoritmo de puntuación

Esta es probablemente la parte más complicada. Deberá diseñar un anotador que guíe el proceso de recocido hacia su objetivo. El anotador debe ser una función continua que dé como resultado números más grandes a medida que la matriz se aproxima a la solución ideal.

¿Cómo se mide la "solución ideal" - triángulo? Aquí hay un anotador ingenuo y fácil: para cada punto, usted sabe si debe ser 1 o 0.Agregue +1 al puntaje si la matriz es correcta, -1 si está mal. Aquí hay algo de código por lo que puede ser explícita (no probado! Revise!)

int Score(Matrix m) { 
    var score = 0; 
    for (var r = 0; r < m.NumRows; r++) { 
     for (var c = 0; c < m.NumCols; c++) { 
      var val = m.At(r, c); 
      var shouldBe = (c >= r) ? 1 : 0; 
      if (val == shouldBe) { 
       score++; 
      } 
      else { 
       score--; 
      } 
     } 
    } 
    return score; 
} 

Con este algoritmo de puntuación, un campo aleatorio de 1s y 0s dará una puntuación de 0. Un "opuesto" triángulo dará la puntuación más negativa, y la solución correcta dará la puntuación más positiva. Diffing dos puntajes le dará el costo.

Si este anotador no funciona para usted, entonces tendrá que "ajustarlo" hasta que produzca las matrices que desea.

Este algoritmo se basa en la premisa de que ajustar este marcador es mucho más simple que idear el algoritmo óptimo para clasificar la matriz.

Answer 2

Aquí es un punto de partida:

convertir cada fila de bits binarios en un número

Ordenar los números en orden descendente.

A continuación, convierta cada fila en binaria.

Answer 3

algoritmo básica:

1. Determinar las sumas de filas y almacenar valores. Determine las sumas de columna y almacene los valores.
2. Ordene las sumas de fila en orden ascendente. Ordene las sumas de la columna en orden ascendente.

Afortunadamente, debe tener una matriz lo más cerca posible de una región triangular superior derecha.

Answer 4

Encontré el siguiente algoritmo y parece funcionar correctamente.

Fase 1: filas se mueven con más 1 s arriba y columnas con la mayoría 1 s derecha.

1. Primero las filas. Ordene las filas contando sus 1 s. No nos importa si 2 filas tienen el mismo número de 1 s.
2. Ahora las columnas. Ordene los cols por contando sus 1 s. No nos importa si 2 cols tienen el mismo número de 1 s.

Fase 2: repetición fase 1 pero con criterios adicionales, por lo que satisfacen la metamorfosis matriz triangular.
Criterio para las filas: si 2 filas tienen el mismo número de 1 s, nos movemos hacia arriba la fila que comienza con menos 0 s.

Criterio para la cols: si 2 cols tienen el mismo número de 1 s, nos movemos derecho la col que tiene menos 0 s en la parte inferior.

---

Ejemplo:

Fase 1

1 2 3 4      1 2 3 4     4 1 3 2 
A 0 1 1 0     B 1 1 1 0     B 0 1 1 1 
B 1 1 1 0 - sort rows-> A 0 1 1 0 - sort cols-> A 0 0 1 1 
C 0 1 0 0     D 1 1 0 0     D 0 1 0 1 
D 1 1 0 0     C 0 1 0 0     C 0 0 0 1 

Fase 2

4 1 3 2      4 1 3 2 
B 0 1 1 1     B 0 1 1 1 
A 0 0 1 1 - sort rows-> D 0 1 0 1 - sort cols-> "completed" 
D 0 1 0 1     A 0 0 1 1 
C 0 0 0 1     C 0 0 0 1 

Editar: resulta que mi algoritmo no da matrices triangulares adecuadas siempre.
Por ejemplo:

Fase 1

1 2 3 4     1 2 3 4     
A 1 0 0 0     B 0 1 1 1     
B 0 1 1 1 - sort rows-> C 0 0 1 1 - sort cols-> "completed" 
C 0 0 1 1     A 1 0 0 0     
D 0 0 0 1     D 0 0 0 1     

Fase 2

1 2 3 4     1 2 3 4     2 1 3 4 
B 0 1 1 1     B 0 1 1 1     B 1 0 1 1 
C 0 0 1 1 - sort rows-> C 0 0 1 1 - sort cols-> C 0 0 1 1 
A 1 0 0 0     A 1 0 0 0     A 0 1 0 0 
D 0 0 0 1     D 0 0 0 1     D 0 0 0 1 
          (no change) 

(*) Tal vez un fase 3 aumentará la buenas resultados. En esa fase colocamos las filas que comienzan con menos 0 s en la parte superior.

Answer 5

filas tratan como números binarios, con la columna de la izquierda como el bit más significativo, y clasificarlos en orden, la parte superior que desciende hasta la parte inferior

Tratar las columnas como números binarios con la fila más inferior que el bit más significativo y ordenarlos en orden ascendente, de izquierda a derecha.

Repita hasta llegar a un punto fijo. Prueba de que el algoritmo termina como un ejercicio para el lector.

Answer 6

Busque un documento de 1987 de Anna Lubiw sobre "Matrices de matrices doblemente léxicas".

Hay una cita de abajo. El orden no es idéntico a lo que está buscando, pero es bastante cercano. Si nada más, deberías poder obtener una muy buena idea desde allí.

http://dl.acm.org/citation.cfm?id=33385