Minimieren Funktion in benachbarte Elemente eines Arrays

Question

Ich habe ein Array (arr) von Elementen, und eine Funktion (f), die 2 Elemente nimmt und gibt eine Zahl ein.

Ich brauche eine Permutation des Arrays, so dass f(arr[i], arr[i+1]) wie möglich für jede i in arr so wenig ist. (Und es sollte Schleife, dh. Es sollte auch f(arr[arr.length - 1], arr[0]) minimieren)

Außerdem funktioniert f wie eine Art Abstand, so f(a,b) == f(b,a)

Ich brauche die optimale Lösung nicht, ob es zu ineffizient ist, sondern eine, die vernünftig funktioniert gut und ist schnell, da ich sie in Echtzeit so ziemlich müssen berechnen (ich weiß nicht, was von arr zu lang ist, aber ich denken könnte es etwas um die 30)

sein

Answer 1

Was bedeutet "so dass f (arr [i], arr [i + 1]) für jeden so wenig wie möglich ist i in arr" bedeuten? Wollen Sie die Summe minimieren ? Wollen Sie die größte von denen, minimieren? Haben Sie f wollen (arr [0], arr [1]) zuerst, dann unter allen Lösungen zu minimieren, die diese minimieren, die eine auswählen, die f (arr [1], arr [2]), etc. und so minimiert auf?

Wenn Sie die Summe minimieren möchten, ist dies genau die Reiseproblem in seiner vollen Allgemeinheit (na ja, "metrische TSP", vielleicht, wenn Ihr f in der Tat die bilden eine metric). Es gibt clevere Optimierungen an die naive Lösung, die Ihnen die genaue optimale und laufen in angemessener Zeit für etwa geben n = 30; Sie einer von denen verwenden könnte, oder einer der Heuristiken, die Sie Annäherungen geben.

Wenn Sie möchten, zu minimieren, die max , es ist ein einfacheres Problem obwohl noch NP-hart: Sie können sich auf die Antwort binäre Suche tun; zeichnen Kanten für Paare für einen bestimmten Wert d, wobei f hat (x, y)

Wenn Sie wollen, es zu minimieren lexiocographically , es ist trivial: das Paar mit der kürzesten Entfernung auswählen und setzt es als arr [0], arr [1], dann arr [Pick 2], dass am nächsten ist, arr [1], und so weiter.

Je nachdem, wo Sie Ihre f (,) s kommt aus, könnte dies ein Problem viel einfacher als TSP sein; es wäre nützlich für Sie, dass auch zu erwähnen.

Answer 2

Sie sind nicht ganz klar, was Sie zu optimieren - die Summe der f (a [i], a [i + 1]) Werte, die max von ihnen, oder etwas anderes

?

Auf jedem Fall mit Geschwindigkeitsbegrenzungen, gierig ist wahrscheinlich die beste Wahl - ein Element auswählen, um eine Marke [0] (es ist egal, welche aufgrund der Wraparound), dann jedes aufeinanderfolgende Element wählen, a [i + 1] zu sein, die eine, die f (a [i], a [i + 1]).

minimiert

Das wird O (n ^ 2) sein, aber mit 30 Einzelteilen, es sei denn, dies in einer inneren Schleife oder etwas ist, das in Ordnung sein wird. Wenn Ihr f () wirklich assoziativ und kommutativ ist, dann könnten Sie in der Lage sein, es in O zu tun (n log n). Offensichtlich nicht schneller durch Reduktion zu sortieren.

Answer 3

Ich glaube nicht das Problem wohldefiniert in dieser Form:

Lassen Sie uns stattdessen definieren n fcns g_i: Perms -> Reals

g_i(p) = f(a^p[i], a^p[i+1]), and wrap around when i+1 > n

sagen, Sie minimieren wollen f über alle Permutationen wirklich bedeutet, dass Sie einen Wert von auswählen können i und minimieren g_i über alle Permutationen, aber für jeden p die minimiert g_i , ein verwandter, aber andere permatation mindernd g_j (nur die Permutation konjugiert). So also macht es keinen Sinn für jede Minimierung f über Permutationen zu sprechen i .

Answer 4

Wenn wir etwas mehr über die Struktur von f (x, y) wissen, das ist ein NP-hartes Problem. Bei einem gegebenen Graphen G und alle Ecken x, y sei f (x, y) 1, wenn es keine Kante ist, und 0, wenn es eine Kante ist. Was ist das Problem stellt, ist eine Ordnung der Eckpunkte, so dass die maximale f (arr [i], arr [i + 1]) Wert minimiert wird. Da für diese Funktion kann nur 0 oder 1 sein, die Rückkehr ein 0 entsprechen einen Hamilton-Pfad in G zu finden und 1 sagt, dass kein solcher Pfad vorhanden ist.

Die Funktion würde irgendeine Art von Struktur haben, dass dieses Beispiel nicht zulässt, für sie gefügig sein.