Minimizar la función en elementos adyacentes de una matriz

Question

Tengo una matriz ( arr ) de elementos y una función ( f ) que toma 2 elementos y devuelve un número.

Necesito una permutación de la matriz, de modo que f (arr [i], arr [i + 1]) sea lo menos posible para cada i en arr . (y debe hacer un bucle, es decir, también debe minimizar f (arr [arr.length - 1], arr [0]) )

Además, f funciona como una distancia, por lo que f (a, b) == f (b, a)

No necesito la solución óptima si es demasiado ineficiente, pero una que funciona razonablemente bien y es rápida ya que necesito calcularla en tiempo real (no sé qué longitud de arr es, pero creo que podría ser alrededor de 30)

Answer 1

¿Qué significa " tal que f (arr [i], arr [i + 1]) es lo menos posible para cada i en arr " ¿media? ¿Desea minimizar la suma ? ¿Quieres minimizar el más grande de esos? ¿Desea minimizar f (arr [0], arr [1]) primero, luego, entre todas las soluciones que minimizan esto, elija la que minimice f (arr [1], arr [2]), etc., y así encendido?

Si desea minimizar la suma , este es exactamente el problema del vendedor ambulante en toda su generalidad (bueno, '' TSP métrico '', tal vez, si su f es de hecho forman una métrica). Hay ingeniosas optimizaciones para la solución ingenua que le dará el óptimo exacto y se ejecutará en un tiempo razonable durante aproximadamente n = 30; podría usar uno de esos, o una de las heurísticas que le dan aproximaciones.

Si desea minimizar el máximo , es un problema más simple aunque aún NP-hard: puede hacer una búsqueda binaria en la respuesta; para un valor particular d, dibuje aristas para pares que tengan f (x, y)

Si quiere minimizarlo lexiocógraficamente , es trivial: elija el par con la distancia más corta y póngalo como arr [0], arr [1], luego elija arr [ 2] que está más cerca de arr [1], y así sucesivamente.

Dependiendo de dónde provengan sus f (,) s, este podría ser un problema mucho más fácil que TSP; Sería útil para usted mencionar eso también.

Answer 2

No tiene completamente claro qué está optimizando: ¿la suma de los valores f (a [i], a [i + 1]), el máximo de ellos u otra cosa?

En cualquier caso, con sus limitaciones de velocidad, codicioso es probablemente su mejor opción: elija un elemento para hacer un [0] (no importa cuál sea el resultado), luego elija cada elemento sucesivo un [i + 1] para ser el que minimiza f (a [i], a [i + 1]).

Eso va a ser O (n ^ 2), pero con 30 elementos, a menos que esté en un bucle interno o algo que esté bien. Si su f () es realmente asociativa y conmutativa, entonces podría hacerlo en O (n log n). Claramente no más rápido por reducción a la clasificación.

Answer 3

No creo que el problema esté bien definido en este formulario:

En su lugar, definamos n fcns g_i: Perms - > Reales

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

Decir que desea minimizar f sobre todas las permutaciones realmente implica que puede elegir un valor de i y minimizar g_i sobre todas las permutaciones, pero para cualquier p que minimice g_i , una permatación relacionada pero diferente minimiza g_j (solo conjuga la permutación). Por lo tanto, no tiene sentido hablar minimizando f sobre permutaciones para cada i .

Answer 4

A menos que sepamos algo más sobre la estructura de f (x, y), este es un problema NP-difícil. Dado un gráfico G y cualquier vértice x, y sea f (x, y) sea 1 si no hay borde y 0 si hay un borde. Lo que pregunta el problema es un ordenamiento de los vértices de modo que el valor máximo de f (arr [i], arr [i + 1]) se minimice. Como para esta función solo puede ser 0 o 1, devolver un 0 es equivalente a encontrar una ruta hamiltoniana en G y 1 dice que no existe tal ruta.

La función debería tener algún tipo de estructura que no permita que este ejemplo sea manejable.