Zeilensummennorm minimieren < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:11 Sa 04.01.2014 | | Autor: | felixf |
Moin!
> Gegeben ist eine Matrix, z.B. der Form:
>
> [mm]\begin{matrix}
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
\end{matrix}[/mm]
>
> Man hat in einer Spalte also eine bestimmte Anzahl von
> konstanten Werten und eine bestimmte Anzahl von Nullen.
> Innerhalb einer Spalte können die Konstanten mit den
> Nullen vertauscht werden.
>
> Ziel ist es, die Werte in den Spalten so anzuordnen, dass
> die Zeilensummennorm, also die größte Summe in einer
> Zeile, minimal wird.
Ich weiss nicht, ob dieser Algorithmus das optimale Ergebnis liefert, aber wie waer's mit folgender Idee:
du hast in Spalte $i$ [mm] $n_i$ [/mm] mal den Wert [mm] $c_i$. [/mm] Ordne die Spalten so an, dass [mm] $c_1 \ge c_2 \ge \dots \ge c_k$ [/mm] gilt. Fange mit einem Vektor der Laenge [mm] $\ell$ [/mm] (Anzahl Spalten) an, der ueberall 0 enthaelt.
Jetzt mache fuer $i = 1, [mm] \dots, [/mm] k$ folgendes: suche die [mm] $n_i$ [/mm] kleinsten Eintraege des Vektors, und addiere jeweils [mm] $c_i$ [/mm] hinzu.
Der entstehende Vektor ist der Vektor mit den Zeilensummen, und die Eintraege sollten eher klein sein.
Ich wuerd das mal fuer einen Haufen kleine Werte mit einem optimalen Algorithmus (der ruhig langsam sein kann, sagen wir durch enumeration) vergleichen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:02 Sa 04.01.2014 | | Autor: | DieAcht |
Hallo,
Meinst du sowas?
[mm] \pmat{ 4 & 1 & 0 \\ 4 & 0 & 3 \\ 4 & 0 & 3 \\ 4 & 0 & 3 \\ 0 & 1 & 3 \\ 0 & 0 & 3}
[/mm]
DieAcht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:09 Sa 04.01.2014 | | Autor: | felixf |
Moin,
> Meinst du sowas?
>
> [mm]\pmat{ 4 & 1 & 0 \\ 4 & 0 & 3 \\ 4 & 0 & 3 \\ 4 & 0 & 3 \\ 0 & 1 & 3 \\ 0 & 0 & 3}[/mm]
nein, bei meinem Algorithmus kommt folgendes heraus:
[mm]\pmat{ 4 & 0 & 0 \\ 4 & 0 & 3 \\ 4 & 0 & 3 \\ 4 & 0 & 3 \\ 0 & 1 & 3 \\ 0 & 1 & 3}[/mm]
(Bis auf Permutation der Zeilen natuerlich... :) )
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Sa 04.01.2014 | | Autor: | DieAcht |
Hallo Felix,
> Moin,
>
> > Meinst du sowas?
> >
> > [mm]\pmat{ 4 & 1 & 0 \\ 4 & 0 & 3 \\ 4 & 0 & 3 \\ 4 & 0 & 3 \\ 0 & 1 & 3 \\ 0 & 0 & 3}[/mm]
>
> nein, bei meinem Algorithmus kommt folgendes heraus:
>
> [mm]\pmat{ 4 & 0 & 0 \\ 4 & 0 & 3 \\ 4 & 0 & 3 \\ 4 & 0 & 3 \\ 0 & 1 & 3 \\ 0 & 1 & 3}[/mm]
>
> (Bis auf Permutation der Zeilen natuerlich... :) )
>
> LG Felix
>
Ja, bei mir würde die gewünschte Zeilensummennorm beachtet.
Ich glaube übrigens, dass du nicht beachtet hast, dann man nur die Nullen vertauschen darf.
Sprich: Wenn eine ganze Spalte aus Zahlen ungleich Null ist, dann ordnet er trotzdem die Spalte, obwohl er das nicht darf, oder irre ich mich?
Schönen Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:46 Sa 04.01.2014 | | Autor: | thomas199 |
Erstmal vielen Dank für die Antworten!
Der Algorithmus von Felix sieht schon sehr gut aus. Ich werde es damit einmal probieren. Muss nur mal schauen wie ich zum Vergleich die tatsächlich optimalen Lösungen finde. Zur Not dann wohl alle Permutationen jeweils einer Zeile bilden...
Was die gewünschte Zeilensummennorm angeht:
Dies sollte nur ein alternatives Ziel sein, falls es nicht möglich sein sollte immer eine minimale Zeilensummennorm zu finden.
Gruß
Thomas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Mi 08.01.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
