Zeilensummennorm durch Vertauschen von Werten in Spalten minimieren |
29.12.2013, 20:54 | Thomas1204 | Auf diesen Beitrag antworten » |
Zeilensummennorm durch Vertauschen von Werten in Spalten minimieren Hallo, ich stehe vor folgendem Problem: Gegeben ist eine Matrix, z.B. der Form: 4 1 3 Zeilensumme = 8 4 1 3 Zeilensumme = 8 4 0 3 Zeilensumme = 7 4 0 3 Zeilensumme = 7 0 0 3 Zeilensumme = 3 0 0 0 Zeilensumme = 0 Aufgabe ist es nun, dass die Werte innerhalb einer Spalte derart vertauscht werden, dass die Zeilensummennorm, also die größte Summe in einer Zeile, minimal wird. Meine Ideen: Ich habe bereits versucht einen genetischen Algorithmus zu programmieren, um dieses Problem zu lösen, allerdings mit mäßigem Erfolg. Habt ihr eventuell Ideen, wie man dieses Problem besser lösen könnte? |
||
03.01.2014, 19:12 | Thomas1204 | Auf diesen Beitrag antworten » |
Hallo, ich habe überlegt, das als binäres Optimierungsproblem zu betrachten. Meine Zielfunktion, die ich minimieren will wäre: f = max(a, b, c, d...) a, b, c, d... entspricht der Summe der 1., 2., 3., 4. ... Zeile. Pro Spalte hat man als Nebenbedingung eine lineare Gleichung, in der festgehalten wird, wieviele von Null unterschiedliche Werte in der jeweiligen Spalte stehen. Da die Zielfunktion nicht linear ist, habe ich ein Problem damit einen Lösungsansatz zu finden. Ich möchte noch erwähnen, dass das oben nur ein einfaches Beispiel ist. Die Matrix könnte auch eine Größe von z.B. 100 x 20 haben. Somit würde ein durchprobieren von allen Lösungen glaube ich wegfallen. Hat eventuell jemand einen Lösungsansatz oder eine Idee wie man das Problem einfacher betrachten könnte? |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|