Ordnen eines Wörterbuchs, um gemeinsame Buchstaben zwischen benachbarten Wörtern zu maximieren

Question

Dies soll eine konkretere, leicht formulierbare Form meiner früheren Frage sein.

Nehmen Sie eine Liste von Wörtern aus einem Wörterbuch mit gemeinsamer Buchstabenlänge.
Wie kann diese Liste neu geordnet werden, damit möglichst viele Buchstaben zwischen benachbarten Wörtern übereinstimmen?

Beispiel 1:

AGNI, CIVA, DEVA, DEWA, KAMA, RAMA, SIVA, VAYU
reorders to:  
AGNI, CIVA, SIVA, DEVA, DEWA, KAMA, RAMA, VAYU  

Beispiel 2:

DEVI, KALI, SHRI, VACH
reorders to:
DEVI, SHRI, KALI, VACH

Der einfachste Algorithmus scheint zu sein: Wähle irgendetwas und suche dann nach der kürzesten Entfernung?
DEVI->KALI (1 gemeinsam) ist jedoch gleichwertig mit DEVI->SHRI (1 gemeinsam)
Die Wahl der ersten Übereinstimmung würde zu weniger gemeinsamen Paaren in der gesamten Liste führen (4 gegenüber 5).

Dies scheint einfacher zu sein als ein vollständiger TSP?

Answer 1

Sie versuchen, den kürzesten hamiltonschen Pfad in einem vollständigen gewichteten Graphen zu berechnen, in dem jedes Wort ein Knoten ist und das Gewicht jeder Kante die Anzahl der Buchstaben ist, die sich zwischen diesen beiden Wörtern unterscheiden.

In Ihrem Beispiel würden die Kanten des Graphen folgendermaßen gewichtet werden:

     DEVI KALI SHRI VACH
DEVI   X    3    3    4
KALI   3    X    3    3
SHRI   3    3    X    4
VACH   4    3    4    X

Dann ist es nur noch eine Frage der Zeit, bis Sie Ihren Favoriten ausgewählt haben. TSP-Lösungsalgorithmus und schon kann es losgehen.

Answer 2

Mein Pseudo-Code:

• Erstellen Sie einen Graphen aus Knoten, wobei jeder Knoten ein Wort darstellt.
• Erstellen Sie Verbindungen zwischen allen Knoten (jeder Knoten ist mit jedem anderen Knoten verbunden). Jede Verbindung hat einen "Wert", der die Anzahl der gemeinsamen Zeichen angibt.
• Verbindungen verwerfen, bei denen der "Wert" 0 ist.
• Gehen Sie den Graphen durch, indem Sie die Verbindungen mit den höchsten Werten bevorzugen. Wenn Sie zwei Verbindungen mit demselben Wert haben, versuchen Sie beide rekursiv.
• Speichern Sie die Ausgabe eines Spaziergangs in einer Liste zusammen mit der Summe des Abstands zwischen den Wörtern in diesem bestimmten Ergebnis. Ich bin mir nicht 100%ig sicher, ob ATM die von Ihnen verwendeten Verbindungen einfach summieren kann. Überzeugen Sie sich selbst.
• Wählen Sie aus allen Ausgaben diejenige mit dem höchsten Wert aus.

Dieses Problem ist wahrscheinlich NP-vollständig, was bedeutet, dass die Laufzeit des Algorithmus unerträglich wird, wenn die Wörterbücher wachsen. Im Moment sehe ich nur eine Möglichkeit, es zu optimieren: Schneiden Sie den Graphen in mehrere kleinere Graphen, führen Sie den Code für jeden aus und fügen Sie die Listen dann zusammen. Das Ergebnis wird nicht so perfekt sein, wie wenn man jede Permutation ausprobiert, aber die Laufzeit wird viel besser sein und das Endergebnis könnte "gut genug" sein.

[EDIT] Da dieser Algorithmus nicht alle möglichen Kombinationen ausprobiert, ist es durchaus möglich, das perfekte Ergebnis zu verpassen. Es ist sogar möglich, in einem lokalen Maximum gefangen zu sein. Nehmen wir an, Sie haben ein Paar mit einem Wert von 7, aber wenn Sie dieses Paar wählen, sinken alle anderen Werte auf 1; wenn Sie dieses Paar nicht nehmen, wären die meisten anderen Werte 2, was ein viel besseres Gesamtergebnis ergibt.

Dieser Algorithmus tauscht Perfektion gegen Geschwindigkeit. Wenn das Ausprobieren aller möglichen Kombinationen Jahre dauern würde, selbst mit dem schnellsten Computer der Welt, muss man einen Weg finden, die Laufzeit zu begrenzen.

Wenn die Wörterbücher klein sind, können Sie einfach jede Permutation erstellen und dann das beste Ergebnis auswählen. Wenn sie über eine bestimmte Grenze hinauswachsen, ist man verloren.

Eine andere Lösung besteht darin, beides zu mischen. Verwenden Sie den Gieralgorithmus, um "Inseln" zu finden, die wahrscheinlich ziemlich gut sind, und verwenden Sie dann die "vollständige Suche", um die kleinen Inseln zu sortieren.

Answer 3

Dies kann mit einem rekursiven Ansatz geschehen. Pseudocode:

Start with one of the words, call it w
FindNext(w, l) // l = list of words without w
  Get a list l of the words near to w
  If only one word in list
    Return that word
  Else
    For every word w' in l do FindNext(w', l') //l' = l without w'

Sie können einige Punkte hinzufügen, um gemeinsame Paare zu zählen und um "bessere" Listen zu bevorzugen.

Answer 4

Vielleicht möchten Sie einen Blick werfen auf BK-Bäume die das Auffinden von Wörtern mit einem bestimmten Abstand zueinander effizient machen. Das ist keine Komplettlösung, aber möglicherweise ein Teil einer solchen.

Answer 5

Dieses Problem hat einen Namen: n-ärer Gray-Code. Da du englische Buchstaben verwendest, ist n = 26. Die Wikipedia-Artikel zum Gray-Code beschreibt das Problem und enthält einen Beispielcode.