Réduire la fonction dans les éléments adjacents d'un tableau

Question

J'ai un tableau ( arr ) d'éléments et une fonction ( f ) qui prend 2 éléments et retourne un nombre.

J'ai besoin d'une permutation du tableau, telle que f (arr [i], arr [i + 1]) est aussi petit que possible pour chaque i dans arr . (et il devrait boucler, c'est-à-dire qu'il devrait aussi minimiser f (arr [arr.length - 1], arr [0]) )

De même, f fonctionne un peu comme une distance, donc f (a, b) == f (b, a)

Je n’ai pas besoin de la solution optimale si elle est trop peu efficace, mais une solution qui fonctionne bien et qui est rapide car j’ai besoin de les calculer en temps réel (je ne sais pas quelle longueur de arr est, mais je pense que cela pourrait être quelque chose autour de 30)

Answer 1

Que fait-on pour que f (arr [i], arr [i + 1]) soit aussi petit que possible pour chaque i dans arr " signifier? Voulez-vous minimiser la somme ? Voulez-vous minimiser le plus grand de ceux-ci? Voulez-vous réduire d'abord f (arr [0], arr [1]), puis parmi toutes les solutions qui le minimisent, choisissez celle qui minimise f (arr [1], arr [2]), etc., etc. sur?

Si vous souhaitez minimiser la somme , c’est exactement le problème du voyageur de commerce dans son ensemble (eh bien, "quotient TSP"), peut-être, si vos f forme effectivement une métrique). Il existe des optimisations intelligentes pour la solution naïve qui vous donneront l’optimum exact et fonctionneront dans un délai raisonnable pendant environ n = 30; vous pouvez utiliser l'une de ces méthodes ou l'une des méthodes heuristiques qui vous donnent des approximations.

Si vous souhaitez minimiser le maximum , il s’agit d’un problème plus simple bien que NP-difficile: vous pouvez effectuer une recherche binaire sur la réponse; pour une valeur particulière d, trace des arêtes pour les paires qui ont f (x, y)

Si vous voulez le réduire lexiocographiquement , c’est trivial: choisissez la paire avec la distance la plus courte et indiquez-la sous la forme arr [0], arr [1], puis sélectionnez arr [ 2] qui est le plus proche de arr [1], et ainsi de suite.

En fonction de la provenance de vos f (,) s, le problème peut être beaucoup plus simple que celui de TSP; il serait utile que vous le mentionniez également.

Answer 2

Vous n'êtes pas tout à fait clair de ce que vous optimisez - la somme des valeurs f (a [i], a [i + 1]), de leur maximum ou de quelque chose d'autre?

Quoi qu’il en soit, avec vos limitations de vitesse, glouton est probablement votre meilleur choix - choisissez un élément pour faire un [0] (peu importe en raison de l’enveloppement), puis choisissez chaque élément successif a [i + 1] soit celui qui minimise f (a [i], a [i + 1]).

Cela va être O (n ^ 2), mais avec 30 éléments, à moins que ce ne soit dans une boucle interne ou quelque chose qui ira bien. Si votre f () est vraiment associatif et commutatif, vous pourrez peut-être le faire dans O (n log n). Clairement pas plus vite en réduisant le tri.

Answer 3

Je ne pense pas que le problème soit bien défini sous cette forme:

Définissons plutôt n fcns g_i: Perms - > Reals

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

Dire que vous voulez minimiser f sur toutes les permutations implique réellement que vous pouvez choisir une valeur de i et minimiser g_i sur toutes les permutations, mais pour tout p qui minimise g_i , une permutation liée mais différente minimise g_j (il suffit de conjuguer la permutation). Il est donc inutile de parler de minimiser la permutation f pour chaque i .

Answer 4

À moins que nous en sachions plus sur la structure de f (x, y), il s’agit d’un problème difficile à résoudre. Étant donné le graphe G et les sommets x, y, f (x, y) vaut 1 s'il n'y a pas de bord et 0 s'il y a un bord. Le problème posé est un ordre des sommets pour que la valeur maximale f (arr [i], arr [i + 1]) soit minimisée. Étant donné que pour cette fonction, il ne peut s'agir que de 0 ou de 1, renvoyer un 0 équivaut à trouver un chemin hamiltonien dans G et 1 signifie qu'un tel chemin n'existe pas.

La fonction devrait avoir une sorte de structure qui interdisait cet exemple pour qu'elle soit traitable.