SPOJ Problemset (klassisch): 9386. Neuordnung II #[MAIN112]

Question

Beschreibung des Problems (der Einfachheit halber hier zitiert):

Für eine Folge von N ganzen Zahlen, A1, A2, ..... AN

Wir können den Stabilitätsfaktor P wie folgt berechnen

P = Summe aller (abs(Ai-Ai-1)*C[i]) mit 2 <= i <= N

C[i] sind die Kosten für die Platzierung einer Zahl an Position i

Ihre Aufgabe ist es, das Minimum P für die gegebenen N Zahlen zu finden unter Berücksichtigung alle verschiedenen Permutationen von ihnen.

---

Ich brauche nur einen Anstoß in die richtige Richtung, was den allgemeinen Ansatz zur Lösung dieses Problems angeht. (Kleine Pseudocode-Stücke sind willkommen, aber ich bin zuversichtlich, dass ich eine Lösung ziemlich genau programmieren kann, sobald der Gesamtalgorithmus allgemein klar ist).

Ich habe eine ganze Weile darüber nachgedacht, bin aber immer noch nicht in der Lage, eine Lösung zu finden, die den Beschränkungen dieses Problems (N <= 15) gerecht wird.

---

Zunächst einmal glaube ich nicht, dass Sie für den größtmöglichen Testfall N=15 alle 15! Permutationen aufzählen und berücksichtigen können, um Ihre Antwort in ausreichend guter Zeit zu finden, da die Komplexitätsklasse dies nicht zulässt.

Wir müssen also einige vereinfachende Annahmen treffen, um diesen Suchraum zu verkleinern. Hier komme ich nicht weiter. Oder geht es vielleicht einfach nur darum, einen intelligenteren Weg zu finden, um diesen Permutationsraum zu durchqueren?

Ich habe versucht, dynamische Programmierung zu verwenden, um dieses Problem zu lösen, weil Permutationen viele gemeinsame Bits teilen, die vorberechnet (memoised) und gespeichert und wiederverwendet werden können, wenn nötig, z. B. A[] = 123456 & A[] = 123465 beide die gleiche Teilsumme für 1234- geben, aber dies ergab keinen Erfolg, weil Sie noch durch die 15 gehen müssen!

Eine andere Idee ist, mit allen möglichen Permutationen der Differenzen zwischen aufeinanderfolgenden A's und allen Elementen von C[] zu arbeiten und zuerst das Paar zu finden, das den minimalen abs(A[i]-A[j])*C[k] Wert aus all diesen ergibt, diese zuzuordnen und als verwendet zu markieren, dann mit einem der i oder j fortzufahren, um das nächste Paar zu bilden, wieder zu iterieren und zu wiederholen. Dies sollte in polynomialer Zeit geschehen (ich schätze etwa n^3), aber die Annahme schlägt bei einigen Beispielen fehl.

Ich glaube nicht, dass dieses Problem so schwierig sein sollte, dass man es in eine Art Graphenproblem umwandeln müsste - wobei A[i], A[j] Knoten bilden und C[k] die Kosten der Kante ist, die diese Knoten verbindet, oder vielleicht ein boolesches SAT-Problem... das alles scheint mir auf einem völlig falschen Weg zu sein.

Wenn Sie dies googeln würden, würden Sie wahrscheinlich fast nichts zu diesem Problem finden, abgesehen von der SPOJ-Site, die dieses Problem beherbergt.

Vielen Dank im Voraus.

Answer 1

Man kann einen dynamischen Programmieralgorithmus mit O(n*2^n)-Raum und O(n^2*n^2)-Zeit auf Teilmengen anwenden, um die Aufgabe zu lösen.

Die wichtigste Erkenntnis ist, dass es beim Aufbau optimaler Lösungen von links nach rechts nur auf die zuvor platzierte Zahl und die verwendete Teilmenge ankommt, nicht aber auf die Reihenfolge, in der die Dinge in der verwendeten Teilmenge platziert wurden.

Die Berechnung hat im Wesentlichen die gleiche Struktur wie diese Lösung der Travelling Salesman Problem.

Sie waren mit Ihrer DV-Idee auf dem richtigen Weg. Die Erkenntnis ist nur, dass der optimale Weg nach all diesen Teilwegen derselbe ist

1235

1325

2135

2315

3125

3215

Sie müssen also nicht alle möglichen Kombinationen untersuchen, sondern nur diejenigen, die den besten Teilpfad aufweisen.

Hier ist ein TLE-Python-Code, der den beschriebenen Algorithmus implementiert, aber an der Verlangsamung durch den konstanten Faktor in Python scheitert. Ich habe ihn in C++ konvertiert und ein AC erhalten.

global A
global C

A = []
C = []

def Solve(used, last, cache):
  if (used, last) in cache:
      return cache[(used, last)]
  cur_pos = len(used)
  if cur_pos == len(A):
    return 0

  mn = 1e10
  for idx in range(len(A)):
      if not idx in used:
          next_used = used.union([idx])
          subcost = Solve(next_used, A[idx], cache)
          additional = C[cur_pos] * abs(last - A[idx])
          mn = min(mn, subcost + additional)
  cache[(used, last)] = mn
  return mn

T = int(raw_input())
for i in range(T):
  N = int(raw_input())
  A = map(int, raw_input().split())
  C = map(int, raw_input().split())
  cache = {}
  print min(Solve(frozenset([idx]), A[idx], cache) for idx in range(len(A)))