Von der teuren Suche bis zur Integer-Programmierung oder Constraint-Programmierung?

Diese Frage ist wahrscheinlich mathematischer als Progammieren. Ich habe die endgültige Antwort noch nicht gefunden, aber zumindest einige Ideen sind hier:

Wir können das Problem auf folgende Weise neu definieren.

  

Problem A: Fixiere positive Ganzzahlen m und n . Lassen Sie S die Menge von n -dimensionalen Vektoren sein, deren Einträge 0 oder 1 sind. Gibt es m by n matrix M , deren Einträge 0 oder 1 sind, so dass für zwei beliebige Vektoren v_1 und v_2 in S die Vektoren Mv_1 und Mv_2 sind unterschiedlich. (Oder Sie können sagen, dass die Matrix M , die als eine Anwendung von n -dimensionalen Vektoren bis m -dimensionalen Vektoren betrachtet wird, auf der Menge S injektiv ist.)

Kurz gesagt: Gibt es für das Paar (m, n) ein solches injektives M ?

Problem A entspricht dem ursprünglichen Problem. In der Tat, wenn Mv_1 = Mv_2 für zwei verschiedene v_1 und v_2 in S , dann haben wir M(v_1 - v_2) = 0 , und der Vektor v_1 - v_2 hat nur 0 , 1 , - 1 als Einträge . Das Gegenteil ist natürlich auch richtig.

Eine weitere Neuinterpretation ist:

  

Problem B: Lassen Sie m , n eine positive Ganzzahl und S die Menge von n -dimensionalen Vektoren, deren Einträge 0 und 1 sind. Können wir m vectors r_1, ..., r_m in S finden, so dass für jedes Paar verschiedener Vektoren v_1 und v_2 in S ein r_i existiert, das <v_1, r_i> != <v_2, r_i> erfüllt? Hier ist <x, y> das übliche innere Produkt.

Kurz gesagt: können wir m vectors in S wählen, um alle in S zu unterscheiden, indem wir das innere Produkt mit den ausgewählten Produkten aufnehmen?

Problem B entspricht Problem A, weil Sie die Matrix M mit m Vektoren in S identifizieren können.

Im Folgenden werde ich beide Beschreibungen des Problems frei verwenden.

Nennen wir das Paar (m, n) ein " gutes Paar ", wenn die Antwort auf Problem A (oder B) ja ist.

Mit der Beschreibung von Problem B wird klar, dass es für eine gegebene n eine minimale m gibt, so dass (m, n) ein gutes Paar ist. Lassen Sie uns m(n) für diese minimale m schreiben, die mit n verknüpft ist.

Ebenso gibt es für ein gegebenes m ein maximales n , so dass (m, n) gut ist. Wenn (m, n) gut ist, d. H. Es gibt eine injektive M , wie in Problem A angegeben, dann wird für jede n' <= n das Löschen aller n - n' Spalten von M eine injektive M' ergeben. Lassen Sie uns n(m) für dieses maximale n schreiben, das zu m gehört.

Die Aufgabe besteht also darin, die Funktionen m(n) und / oder n(m) zu berechnen.

Wir beweisen zuerst mehrere Lemmata:

  

Lemma 1: Wir haben m(n + k) <= m(n) + m(k) .

Beweis: Wenn M eine m(n) by n ist Injektivmatrix für das Paar (m(n), n) und K ist eine m(k) by k Injektivmatrix für das Paar (m(k), k) , dann die (m(n) + n(k)) by (n + k) Matrix

funktioniert für das Paar (m(n) + 1, n + 1) . Um dies zu sehen, lassen Sie v_1 und v_2 ein beliebiges Paar unterschiedlicher (n + k) -dimensionaler Vektoren. Wir können beide in zwei Teile schneiden: die ersten n -Einträge und die letzten k -Einträge. Wenn die ersten Teile von ihnen nicht gleich sind, dann können sie durch eine der ersten m(n) Reihen der obigen Matrix unterschieden werden; Wenn die ersten Teile gleich sind, dann müssen die zweiten Teile von ihnen verschieden sein, daher können sie durch eine der letzten m(k) Reihen der obigen Matrix unterschieden werden.

  

Bemerkung: Die Sequenz m(n) ist also eine Subadditiv Sequenz.

Eine einfache Folge:

  

Korollar 2: Wir haben m(n + 1) <= m(n) + 1 , also m(n) <= n .

Beweis: Nimm k = 1 in Lemma 1.

Beachten Sie, dass Sie von anderen bekannten Werten von m(n) bessere obere Grenzen erhalten können. Zum Beispiel, da wir m(4) <= 3 kennen, haben wir m(4n) <= 3n . Wie auch immer, diese geben dir immer O(n) obere Grenzen.

Das nächste Lemma gibt Ihnen eine untere Grenze.

  

Lemma 3: m(n) >= n / log2(n + 1) .

Beweis: T sei die Menge von m(n) -dimensionalen Vektoren, deren Einträge in {0, 1, ..., n} liegen. Any m(n) by n matrix M ergibt eine Karte von S bis T , wobei v an Mv gesendet wird.

Da es eine M gibt, so dass die obige Karte injektiv ist, ist die Größe der Menge T notwendigerweise mindestens die Größe der Menge S . Die Größe von T ist (n + 1)^m und die Größe von S ist 2^n , also haben wir:

(n + 1)^m(n) >= 2^n

oder äquivalent, m(n) >= n / log2(n + 1) .

Zurück zur Programmierung

Ich muss sagen, dass ich keinen guten Algorithmus gefunden habe. Sie könnten das Problem als Setze das Cover-Problem wie folgt:

Lassen Sie U die Menge von n dimensionalen Vektoren mit den Einträgen 1 , 0 oder - 1 und S wie oben sein. Jeder Vektor w in S gibt eine Untermenge C_w von U : C_w = {v in U: <w, v> != 0} . Die Frage ist dann: Können wir m vectors w so finden, dass die Vereinigung der Teilmengen C_w gleich U ist.

Das allgemeine Set-Cover-Problem ist NP-vollständig, aber im obigen Wiki-Link gibt es eine ganzzahlige lineare Programmformulierung.

Wie auch immer, das kann Sie nicht viel weiter bringen als n = 10 , denke ich.

Ich werde diese Antwort weiter bearbeiten, wenn ich weitere Ergebnisse habe.

Ich denke, mit Boolescher Matrixmultiplikation können Sie das Mv = 0 Problem mit nur 1 & amp; 0 ist effizienter. Mit dieser Methode sollten Sie in der Lage sein zu lösen, ohne sich über Rangmängel aufgrund der RHS gleich Null Gedanken zu machen. Hier finden Sie einen Link zur Dokumentation einiger Algorithmen zur Verwendung von BMM:

Ссылка