em função de itens adjacentes de uma matriz minimizar

Question

I tem uma matriz (arr) de elementos, e uma função (f) que leva elementos 2 e retorna um número.

Eu preciso de uma permutação da matriz, de tal forma que f(arr[i], arr[i+1]) é tão pouco quanto possível para cada i em arr. (E deveria laço, isto é. Também deve minimizar f(arr[arr.length - 1], arr[0]))

Além disso, f funciona como uma espécie de distância, de modo f(a,b) == f(b,a)

Eu não preciso a solução ideal se for muito ineficiente, mas que funciona bem razoáveis ??e é rápido desde que eu preciso para calculá-los praticamente em tempo real (não sei o que o comprimento de arr é, mas eu acho que poderia ser algo em torno de 30)

Answer 1

O que "tal que f (arr [i], arr [i + 1]) é tão pouco quanto possível para cada i em arr" significa? Você quer minimizar a soma ? Você quer minimizar o maior desses? Você quer minimizar f (arr [0], arr [1]) em primeiro lugar, em seguida, entre todas as soluções que minimizem isso, escolher o que minimiza f (arr [1], arr [2]), etc., etc. on?

Se você quiser minimizar o sum , este é exatamente do vendedor ambulante problema em toda a sua generalidade (bem, "TSP métrica", talvez, se a sua f é de fato formar uma métrica). Há otimizações inteligentes para a solução ingênua que lhe dará o melhor exata e executados em tempo razoável por cerca de n = 30; você poderia usar um desses, ou uma das heurísticas que lhe dão aproximações.

Se você quiser minimizar o máxima , é um problema mais simples, embora ainda NP-hard: você pode fazer busca binária sobre a resposta; para um determinado valor d, desenhar bordas para os pares que têm f (x, y)

Se você quer minimizá-lo lexiocographically , é trivial: escolher a par com a distância mais curta e colocá-lo como arr [0], arr [1], em seguida, escolher arr [ 2] que está mais próximo ao arr [1], e assim por diante.

Dependendo de onde seu f (,) s estão vindo, isso pode ser um problema muito mais fácil do TSP; seria útil para você mencionar isso também.

Answer 2

Você não está totalmente claro o que você está otimizando -? A soma do f (a [i], a [i + 1]) valores, o máximo deles, ou qualquer outra coisa

Em qualquer caso, com suas limitações de velocidade, ganancioso é provavelmente a sua melhor aposta - escolher um elemento para fazer a [0] (não importa qual, devido à envolvente), em seguida, escolher cada elemento sucessivo a [i + 1] para ser aquele que minimiza f (a [i], a [i + 1]).

Isso vai ser O (n ^ 2), mas com 30 itens, a menos que seja em um loop interno ou algo que vai ficar bem. Se o seu f () realmente é associativa e comutativa, então você pode ser capaz de fazê-lo em O (n log n). Claramente há mais rápido, redução de classificação.

Answer 3

Eu não acho que o problema é bem definida desta forma:

Vamos em vez definir n fcns g_i: Perms -> reais

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

Para dizer que você quer minimizar f sobre todas as permutações realmente implica que você pode escolher um valor de i e minimizar g_i sobre todas as permutações, mas para qualquer p que minimiza g_i , um relacionado, mas diferente permatation minimiza g_j (apenas conjugar a permutação). Assim, portanto, não faz sentido falar minimizando f sobre permutações para cada i .

Answer 4

A menos que saibamos algo mais sobre a estrutura de f (x, y), este é um problema NP-hard. Dado um gráfico G e quaisquer vértices x, y seja f (x, y) ser um, se não houver borda e 0 se existe uma aresta. Qual o problema pede é uma ordenação dos vértices de modo que ([i] arr [+ 1 i] arr,) valor máximo f é minimizado. Uma vez que para esta função só pode ser 0 ou 1, retornando a 0 é equivalente a encontrar um caminho hamiltoniano em G e 1 está dizendo que não existe tal caminho.

A função teria que ter algum tipo de estrutura que não permite esse exemplo para que seja tratável.