Wie erzeugt man Matrizen, die die Dreiecksungleichung erfüllen?

Question

Mal

(n ist eine Dimension der Matrix E und fixiert (zum Beispiel n = 4 oder n = 5)) quadratische Matrix berücksichtigen. Matrix Einträge erfüllen folgende Bedingungen:

Die Aufgabe besteht darin zu erzeugen, alle Matrizen E. Meine Frage ist, wie das zu tun? Gibt es einen gemeinsamen Ansatz oder Algorithmus? Ist das überhaupt möglich? Was soll anfangen?

Answer 1

Naive Lösung

A naive Lösung ist zu berücksichtigen, jede mögliche n -by- n Matrix zu erzeugen E wobei jede Komponente ist eine nicht-negative ganze Zahl nicht größer als n, nehmen dann von diesen nur die Matrizen, die die zusätzlichen befriedigen Einschränkungen. Was wäre die Komplexität davon?

Jede Komponente kann n + 1 Werte übernehmen, und es gibt n^2 Komponenten, so gibt es O((n+1)^(n^2)) Kandidatenmatrizen. Das hat eine wahnsinnig hohe Wachstumsrate.

-Link: WolframAlpha analysis of (n+1)^(n^2)

Ich denke, es sicher ist sicher, dass dies kein gangbarer Weg.

Bessere Lösung

Eine bessere Lösung folgt. Es beinhaltet viel Mathematik.

Lassen Sie S die Menge aller Matrizen E sein, die Ihre Anforderungen erfüllen. Lassen Sie N = {1, 2, ..., n}.

Definitionen:

• Lassen Sie eine metrische auf N die übliche Definition haben, außer dem Erfordernis der Symmetrie verzichtet.

• Lassen Sie I und J Partition der Satz N. Lassen Sie D(I,J) die n x n Matrix sein, die D_ij = 1 hat, wenn i in I und j ist in J und D_ij = 0 anders.

• Lassen Sie A und B in S sein.Dann A ist benachbarte-B, wenn und nur wenn es existiert I und J Partitionierung N so dass A + D(I,J) = B.

  Wir sagen A und Bbenachbarten sind, wenn und nur wenn A benachbart ist B oder B-A benachbart ist.

• zwei Matrizen A und B in S sind wegzusammenhängend wenn und nur wenn es eine Folge von benachbarten Elementen S zwischen ihnen existiert.

• Die Funktion M(E) bezeichnet die Summe der Elemente der Matrix E.

Lemma 1:
E = D(I,J) ist eine Metrik auf N.

Beweis:
Dies ist eine triviale Aussage außer für den Fall einer I-J gehenden Flanke. Sei i in I und j in J. Dann E_ij = 1 nach Definition von D(I,J). Lassen Sie k in N sein. Wenn k in I ist, dann E_ik = 0 und E_kj = 1, so E_ik + E_kj >= E_ij. Wenn k in J ist, dann E_ik = 1 und E_kj = 0, also E_ij + E_kj >= E_ij.

Lemma 2:
E in S sein lassen, so dass E != zeros(n,n). Dann existieren I und J Partitionierung N so dass E' = E - D(I,J) in S mit M(E') < M(E) ist.

Beweis:
Let (i,j) so beschaffen sein, dass E_ij > 0. Sei I die Teilmenge von N, die von i über einen gerichteten Kostenpfad 0 erreicht werden kann. I kann nicht leer sein, weil i in I ist. I kann nicht N sein, weil j nicht in I ist. Dies liegt daran, dass E die Dreiecksungleichung und E_ij > 0 erfüllt.

Lassen Sie J = N - I. Dann I und J sind beide nicht leer und Partition N.Nach der Definition von I gibt es keine (x,y), so dass E_xy = 0 und x in I und y in J ist. Daher E_xy >= 1 für alle x in I und y in J.

Also E' = E - D(I,J) >= 0. Das M(E') < M(E) ist offensichtlich, weil alles, was wir getan haben, von Elementen E subtrahiert wird, um E' zu erhalten. Da nun E eine Metrik auf N und D(I,J) eine Metrik auf N ist (durch Lemma 1) und E >= D(I,J) haben wir E' ist eine Metrik auf N. Daher ist E' in S.

Satz:
Let E in S sein. Dann sind E und zeros(n,n) pfadverbunden.

Beweis (durch Induktion):
Wenn E = zeros(n,n), dann ist die Aussage trivial.

Angenommen . Sei M(E) die Summe der Werte in E. Dann können wir durch Induktion annehmen, dass die Aussage für jede Matrix E' mit M(E') < M(E) wahr ist.

Da E != zeros(n,n) durch Lemma 2 wir haben einige E' in S so dass M(E') < M(E). Dann wird durch die induktive Hypothese E' mit zeros(n,n) verbunden. Daher ist E mit zeros(n,n) verbunden.

Corollary:
Das Set S wegzusammenhängend ist.

Beweis:
Lassen A und B in S sein. Durch die Theorem, A und B sind beide Weg-Verbindung zu zeros(n,n). Daher ist A mit B verbunden.

Algorithmus

Die Corollary sagt uns, dass alles in S wegzusammenhängend ist. Eine effektive Möglichkeit, alle Elemente von S zu finden, besteht darin, eine Breitensuche über das Diagramm durchzuführen, das durch Folgendes definiert wird.

• Die Elemente S sind die Knoten des Graphen
• Knoten des Graphen durch eine Kante verbunden sind, wenn und nur wenn sie

Bei einem Knoten E benachbart sind, können Sie alle finden der (potentiell) nicht besuchten Nachbarn von E durch einfaches Aufzählen aller möglichen Matrizen D(I,J) (davon gibt es 2^n) und Erzeugen von E' = E + D(I,J) für jedes. Das Aufzählen der D(I,J) sollte relativ einfach sein (es gibt eine für jede mögliche Untergruppe I von , mit Ausnahme des leeren Satzes und).

Beachten Sie, dass im vorhergehenden Absatz E und D(I,J) beide Messwerte auf N sind. Wenn Sie also E' = E + D(I,J), erzeugen, müssen Sie nicht überprüfen, ob es die Dreiecksungleichung erfüllt. - E' ist die Summe zweier Metriken, also ist es eine Metrik. Um zu überprüfen, dass E' in S ist, müssen Sie nur überprüfen, ob das maximale Element in E'n nicht überschreitet.

Sie können die Breitensuche von einem beliebigen Element aus S starten und sicherstellen, dass Sie keines von S verpassen. So können Sie die Suche mit zeros(n,n) starten.

---

Beachten Sie, dass die Mächtigkeit der Menge S extrem schnell n steigt wächst, so das gesamte Set Computing S wird nur für kleine n lenkbar sein.