Hallo Liste und Joke,
Am 18.04.2011, 10:11 Uhr, schrieb Joke de Buhr <j...@seiken.de>:
> natürlich nicht auf anhieb verstanden.
Hoffe, nach mehrmaligem Durchlesen war es dann doch verständlich.
> Aber mal anders gefragt: Du meintest du hättest da schon ein
ähnliches Programm vorliegen. a) Welche
> Programmiersprache b) hast du es mal modifiziert c) kann man etwas
> betrachten?
>
Das Programm ist in C++ geschrieben, allerdings ist der Code nicht sehr
schön. Es vertauscht Spalten einer Matrix per Backtracking, um die
Diagonale mit 1en zu füllen. Es gibt nur Einträge mit 1 und 0.
Zu modifizieren sind also die zulässigen Werte für Einträge und das
Renormieren nach dem Vertauschen. Die Laufzeit ist recht gut, nur das
initiale Sortieren läuft über bidirektionales Bubblesort (bei 1000*1000
experimentell O(10s), also vernachlässigbar gegenüber der restlichen
Laufzeit).
Ein Hinweis, wie man gewichtete Optimierungsprobleme sehr gut Lösen
kann.
Es gibt da ein Programm namens lpsolve [1]. Ich weiß nicht, ob es jetzt
gerade mit dem bestehenden Gedankengang weiterhilft, generell ließe sich
lpsolve allerdings für hier einsetzen. Das fällt in den Bereich Linear
Programming.
[1] http://lpsolve.sourceforge.net/
Das klingt sehr interessant. Schau ich mir die Tage mal an.
Gruß, Marco8
