Verzweigen und binden für minimale lineare Anordnung

Ich versuche, dieses Problem zu lösen, aber ich konnte keine ungefähre Kostenfunktion finden, die besser ist als die Kosten.

Angenommen, ist ein Graph von n Knoten \ {1, 2, 3, \ ldots, n \} . Für eine Permutation f des Knoten von G , das Gewicht jeder Kante (x, y) wird | f (x) -f (y) | . Das Gesamtgewicht von G ist die Summe der Gewichte seiner Kanten. Sie können sich f als eine Neukennzeichnung der Knoten von G vorstellen , wobei f (x) die neue Bezeichnung des Knotens x ist .$G$$n$$\{1, 2, 3, \ldots , n\}$$f$$G$$(x,y)$$|f(x)-f(y)|$$G$$f$$G$$f(x)$$x$

Ich versuche eine Permutation f zu finden $f$, die zu einem minimalen Gesamtgewicht von $G$ .

Wenn ich nun versuche, dies zu lösen, könnte ich nur die ungefähren Kosten ermitteln, die die Summe der Gewichte jeder bis jetzt abgeschlossenen Kante (für jeden Backtracking-Baumknoten) sind, und vom Knoten mit den minimalen Kosten ausgehen. Ich frage mich, ob mir jemand mit einer besseren Näherungsformel helfen kann.

Eine der besten Lösungen basiert wahrscheinlich auf einer linearen Programmierrelaxation oder einer direkten ganzzahligen Programmierung . Für letztere ist das Verzweigen und Zurückverfolgen implizit und Sie müssen es nicht selbst verwalten.

Ich habe gesehen, wie es mit dieser Technik auf zwei Arten gelöst wurde. Wir können auch Ihren Begrenzungsalgorithmus leicht verbessern.

Die Lehrbuchmethode

Mit den binären Variablen die , können Sie kontinuierliche Variablen$x_{ij}$$f(i) = j$$f(i) = \sum_{j=1}^n j x_{ij}$

Fügen Sie die Einschränkungen und darstellen, dass einer Position nur ein Knoten zugewiesen ist.$\sum_i x_{ij} = 1$$\sum_j x_{ij} = 1$

Für jede Kante haben die Kosten zwei Einschränkungen: und , und Sie möchten minimieren$c_e$$c_e \geq f(i) - f(j)$$c_e \geq f(j) - f(i)$$\sum_e c_e$

Sie können dieses Problem einem ganzzahligen Programmierlöser geben, der gerne das Backtracking für Sie und mehr übernimmt - oder Sie können die lineare Programmierentspannung jedes Mal selbst lösen (nur wenn Sie lernen möchten, optimiert der Löser sie intern).

Noch eine Entspannung

Anstatt die Positionen als binäre Variablen zu verwenden, können Sie dh Knoten geht vor Knoten . Dies ist besser geeignet, wenn Sie die Verzweigung selbst durchführen und diese Variablen nicht explizit angeben möchten.$f(i) < f(j)$$i$$j$

Mit diesem Ansatz kann es manchmal vorkommen, dass an jedem Knoten ein schnelleres Problem zu lösen ist. Hier kann es als einfacheres Problem mit minimalem Kostenfluss gelöst werden, wie in diesem Dokument gezeigt . Ich würde es nicht empfehlen, wenn Sie nicht bereit sind, viel Zeit zu untersuchen und Ihr Problem zu untersuchen.

Andere Techniken

Für Branch-and-Bound reicht jede Untergrenze Ihrer Kostenfunktion aus. Für kleine Probleme ist Ihr Bounding-Ansatz vollkommen in Ordnung.

Sie könnten es enger machen: Wählen Sie für jede Kante mit einem nicht platzierten Knoten die bestmögliche kostenlose Beschriftung aus, um die Kosten abzuschätzen. Mehrere Kanten verwenden möglicherweise dieselbe Platzierung für verschiedene Knoten. Dies ist jedoch besser, als ihre Kosten auf 0 zu schätzen.

Es gibt viele mögliche Variationen dieses Schemas: Wählen Sie die beste freie Beschriftung für jeden unbeschrifteten Knoten (unabhängig von Überlappungen) oder berücksichtigen Sie Überlappungen nur innerhalb kleiner Gruppen von Knoten.