Ordinamento di una matrice 2D binaria?

Question

Sto cercando alcuni suggerimenti qui perché non so da dove iniziare la ricerca di questo.

Ho un matrice 2D con 0 o 1 in ciascuna cella, come ad esempio:

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

e vorrei di risolvere in modo è come "triangolare superiore" possibile, in questo 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 

Le righe e le colonne devono rimanere intatte, ovvero gli elementi non possono essere spostati singolarmente e possono essere scambiati solo "interi".

Capisco che ci sarà probabilmente casi patologici in cui una matrice ha diverse possibili risultati ordinati (ad esempio stessa forma, ma si differenziano per l'identità dei righe/colonne "originali".)

Così, qualcuno può suggerire dove potrei trovare alcuni punti di partenza per questo? Una libreria/algoritmo esistente sarebbe grandiosa, ma mi accontenterò di conoscere il nome del problema che sto cercando di risolvere!

Dubito che sia un problema di algebra lineare in quanto tale, e forse c'è un qualche tipo di tecnica di elaborazione dell'immagine applicabile.

Tutte le altre idee a parte, la mia ipotesi iniziale è solo per scrivere un semplice inserimento sorta sulle righe, poi le colonne e iterare che fino a stabilizzarsi (e la speranza che la rilevazione dei casi patologici non è troppo difficile.)

Maggiori dettagli: alcune ulteriori informazioni su ciò che sto cercando di fare possono aiutare a chiarire. Ogni riga rappresenta un concorrente, ogni colonna rappresenta una sfida. Ogni 1 o 0 rappresenta "successo" per il concorrente in una particolare sfida.

Ordinando la matrice in modo che tutti i 1 siano in alto a destra, spero di fornire una classifica della difficoltà intrinseca di ogni sfida e una classifica dei concorrenti (che terrà conto della difficoltà delle sfide che hanno riuscii a, non solo il numero di successi)

Nota sulla risposta accettata:. ho accettato Simulated Annealing come "la risposta" con l'avvertenza che questa domanda non ha una risposta giusta. Sembra un buon approccio, anche se in realtà non sono riuscito a trovare una funzione di punteggio che funzioni per il mio problema.

Answer 1

Un algoritmo basato su simulated annealing può gestire questo genere di cose senza troppo problemi. Non eccezionale se si hanno matrici piccole che molto probabilmente hanno una soluzione fissa, ma grandiose se le matrici diventano più grandi e il problema diventa più difficile.

(tuttavia, fallisce anche il vostro desiderio che gli inserimenti può essere fatto in modo incrementale.)

Preliminari

1. escogitare una funzione di prestazione che "punteggi" una matrice - matrici che sono più vicini a la tua eccellenza dovrebbe avere un punteggio migliore rispetto a quelli che sono meno triangolari.

2. Definire una serie di operazioni consentite nella matrice. La tua descrizione era un po 'ambigua, ma se riesci a scambiare le righe, una operazione sarebbe SwapRows(a, b). Un altro potrebbe essere SwapCols(a, b).

Il ciclo di ricottura

Non darò un'esposizione completa, ma l'idea è semplice. Esegui trasformazioni casuali sulla matrice usando le tue operazioni. Si misura quanto "migliore" è la matrice dopo l'operazione (utilizzando la funzione di prestazioni prima e dopo l'operazione). Quindi decidi se commettere quella trasformazione. Si ripete questo processo molto.

Decidere se eseguire il commit della trasformazione è la parte divertente: è necessario decidere se eseguire tale operazione o meno. Verso la fine del processo di ricottura, accettate solo le trasformazioni che hanno migliorato il punteggio della matrice. Ma prima, in un momento più caotico, consenti alle trasformazioni che non migliorano il punteggio. All'inizio, l'algoritmo è "caldo" e tutto va bene. Alla fine, l'algoritmo si raffredda e sono consentite solo buone trasformazioni. Se la pelle fresca linearmente l'algoritmo, quindi la scelta se accettare una trasformazione è:

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

Si consiglia di leggere le informazioni contenute in ottima Numerical Recipes per ulteriori informazioni su questo algoritmo.

Breve storia, dovresti imparare alcuni di questi algoritmi generali. Ciò consentirà di risolvere grandi classi di problemi difficili da risolvere in modo analitico.

algoritmo di punteggio

Questa è probabilmente la parte più difficile. Dovrai ideare un segnapunti che guida il processo di ricottura verso il tuo obiettivo. Il segnapunti dovrebbe essere una funzione continua che si traduce in numeri più grandi mentre la matrice si avvicina alla soluzione ideale.

Come si misura la "soluzione ideale" - triangleness? Ecco un segnaposto ingenuo e facile: per ogni punto, si sa se dovrebbe essere 1 o 0.Aggiungi +1 al punteggio se la matrice è corretta, -1 se è sbagliata. Ecco alcuni codice in modo che può essere esplicita (non testato! Si prega di consultare!)

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 questo algoritmo di punteggio, un campo casuale di 1 e 0 darà un punteggio pari a 0. Un "opposto" triangolo darà la punteggio più negativo, e la soluzione corretta darà il punteggio più positivo. Diffondere due punteggi ti darà il costo.

Se questo indicatore non funziona per te, dovrai "sintonizzarlo" finché non produce le matrici che desideri.

Questo algoritmo si basa sulla premessa che la messa a punto di questo scorer è molto più semplice rispetto alla definizione dell'algoritmo ottimale per l'ordinamento della matrice.

Answer 2

Ecco un punto di partenza:

Convertire ogni riga bit binari in un numero

ordinare i numeri in ordine decrescente.

Quindi riconvertire ogni riga in binario.

Answer 3

algoritmo di base:

1. determinare le somme riga e memorizzare valori. Determinare le somme della colonna e memorizzare i valori.
2. Ordinare le somme delle righe in ordine crescente. Ordinare la colonna somme in ordine crescente.

Si spera che si debba avere una matrice il più vicino possibile a una regione triangolare in alto a destra.

Answer 4

Mi è venuto in mente il seguente algoritmo e sembra funzionare correttamente.

Fase 1: spostare le righe con più 1 s su e colonne con la maggior parte 1 s destra.

1. Prima le righe. Ordina le righe contando i loro 1 s. Non ci interessa se 2 righe hanno lo stesso numero di 1 s.
2. Ora le colonne. Ordina i cols per contando i loro 1 s. Non ci interessa se 2 col hanno lo stesso numero di 1 s.

Fase 2: ripetizione fase 1 ma con criteri aggiuntivi, in modo da soddisfare il Variante matrice triangolare.
Criterio di righe: se 2 righe hanno lo stesso numero di 1 s, si sposta fino riga che inizia con meno 0 s.

Criterio di colli: se 2 cols hanno lo stesso numero di 1 s, ci muoviamo destra il colle che ha meno 0 s in fondo.

---

Esempio:

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 

Edit: si scopre che il mio algoritmo non dà adeguate matrici triangolari sempre.
Ad esempio:

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) 

(*) Forse una fase 3 aumenterà le buoni risultati. In questa fase posizioniamo le righe che iniziano con meno 0 s nella parte superiore.

Answer 5

righe trattano come numeri binari, con la colonna più a sinistra come il bit più significativo, e ordinarli in ordine, all'inizio decrescente verso il basso

Trattare le colonne come numeri binari con la riga in basso come il bit più significativo e ordinali in ordine crescente, da sinistra a destra.

Ripetere fino a raggiungere un punto fisso. Prova che l'algoritmo termina a sinistra come esercizio per il lettore.

Answer 6

Cerca un articolo del 1987 di Anna Lubiw su "Ordinazioni lessicali di matrici".

C'è una citazione qui sotto. L'ordine non è identico a quello che stai cercando, ma è piuttosto vicino. Se non altro, dovresti essere in grado di ottenere una buona idea da lì.

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