Hat man eine Matrix M der Größe m, n über Ganzzahlen, was wäre ein guter Algorithmus, um sie so zu transformieren, dass die Summe aller Elemente maximal ist?
Die einzigen erlaubten Operationen multiplizieren mit -1 spaltenweise oder zeilenweise. Es können beliebig viele solcher Operationen ausgeführt werden.
Grobe, allgemeine Idee : Ich habe überlegt, jedes Minuszeichen von einer solchen negativen Zahl in die positive Zahl zu verschieben, deren Wert am kleinsten ist, so dass das Minus den geringsten Einfluss darauf hat die Summe.
Nehmen wir zum Beispiel:
%Vor% Ich habe das versucht, indem ich einen der kürzesten Wege vom negativen Element zur kleinsten Zahl und invert_at jeder Zelle auf dem Weg dorthin gebaut habe.
Zuerst durch Einfügen der Start- und Endzellen:
%Vor%Ich lande mit:
%Vor% welche Art von Aussehen interessant. Es drückt das Minus auf die -1 in der unteren rechten Ecke, aber auch auf einige andere Bereiche. Nun, wenn ich am Anfang und an der Endposition wieder invertieren würde (das heißt, -1 * -1 = 1 ), also die Anfangs- und Endzellen an erster Stelle auslassen, habe ich am Ende:
Das sieht besser aus, wenn man bedenkt, dass ich an
kommen möchte %Vor%durch "Drücken" des Minus nach rechts "Hälfte" der Matrix.
Wenn wir von "Hälften" sprechen, habe ich auch (sehr) mit der Idee gespielt, Partitionen der Matrix zu verwenden, aber ich konnte keine brauchbaren Muster erkennen.
Die meisten Dinge, die ich versucht habe, haben mich zurück zur ursprünglichen Matrix geführt und dieser "Lawineneffekt", den wir beobachten können, macht mich verrückt.
Was wäre ein guter Ansatz, um dieses Problem zu lösen?
Jede von n Zeilen oder m Spalten kann entweder gewendet (-1) oder nicht geglättet (1) werden.
Dies bedeutet, dass die Gesamtzahl der Möglichkeiten 2 ^ (n + m) ist. Dies bedeutet, dass es eine Lösung gibt, die in exponentieller Zeit gefunden werden kann. Für kleine Matrizen können Sie Brute-Force verwenden und nach allen möglichen Kombinationen von gedrehten und unausgeflippten Spalten und Zeilen suchen.
Sie müssen jedoch warten, bis alles angewendet ist, oder Sie werden in lokalen Minima hängen bleiben.
In diesem speziellen Fall ist M bereits die maximale Summe (27)
%Vor%Gibt:
%Vor%Das Problem ist höchstwahrscheinlich NP-schwer als eine Pseudo-Boolesche Funktion (PB) -Optimierung.
Sie können mit der booleschen Variablen x_i die Tatsache bezeichnen, dass "i-te Zeile negiert wurde", und mit der booleschen Variablen y_j wurde die Tatsache "j-te Spalte negiert".
Dann kann das "Flip-Zeichen" jedes Matrixelements als
beschrieben werden %Vor%Wenn du also deine Matrix M verwendest, fragt dein Problem nach der Maximierung der PB-Funktion
%Vor%Es ist bekannt, dass die Optimierung von PB-Funktionen NP-schwer ist. Wenn also diese spezielle Klasse von Funktionen keine clevere Lösung zulässt, scheint intelligentes Brute-Forcing (Andrews Lösungen) der richtige Weg zu sein.
Es gibt eine nette Zusammenfassung für ein sehr ähnliches Problem in diesem Blogpost .
Ich bin mir nicht sicher, ob Ihr Problem eine polynomielle Zeitlösung hat. Ich denke nicht, aber ich kann auch nicht beweisen, dass es NP-vollständig ist.
Ein Ansatz, der vielversprechend sein könnte, ist es, es als (nichtkonvexes) quadratisches Programm zu schreiben: Wir wollen Vektoren v und w finden, so dass -1 & lt; = v & lt; = 1, -1 & lt; = w & lt; = 1, und v ^ TM w ist so groß wie möglich. Dies ist eine Entspannung; Ich brauche nicht v und w nur +/- 1 Einträge, aber es hat die gleiche optimale Lösung wie Ihr Problem. Sie sollten in der Lage sein, eine "angemessene" konvexe quadratische Relaxation für dieses Problem zu finden und dann ein Verzweigungs-und-Bindungs-Schema darüber zu bauen.
Tags und Links python algorithm python-3.x numpy