Ridurre a icona la funzione negli elementi adiacenti di un array

Question

Ho un array ( arr ) di elementi e una funzione ( f ) che accetta 2 elementi e restituisce un numero.

Ho bisogno di una permutazione dell'array, in modo tale che f (arr [i], arr [i + 1]) sia il meno possibile per ogni i in arr . (e dovrebbe essere in loop, cioè dovrebbe anche minimizzare f (arr [arr.length - 1], arr [0]) )

Inoltre, f funziona in modo simile a una distanza, quindi f (a, b) == f (b, a)

Non ho bisogno della soluzione ottimale se è troppo inefficiente, ma una che funziona abbastanza bene ed è veloce poiché devo calcolarle praticamente in tempo reale (non so che lunghezza di arr è, ma penso che potrebbe essere qualcosa intorno ai 30)

Answer 1

Che cosa è "tale che f (arr [i], arr [i + 1]) sia il meno possibile per ogni i in arr " significare? Vuoi minimizzare la somma ? Vuoi ridurre al minimo il più grande di quelli? Vuoi minimizzare f (arr [0], arr [1]), quindi tra tutte le soluzioni che minimizzano questo, scegli quello che minimizza f (arr [1], arr [2]), ecc., E così via on?

Se vuoi minimizzare la somma , questo è esattamente il Problema del commesso viaggiatore nella sua piena generalità (bene, "metrica TSP", forse, se le tue f anzi formano una metrica). Ci sono ottimizzazioni intelligenti per la soluzione ingenua che ti darà l'esatto ottimale e funzioneranno in tempo ragionevole per circa n = 30; potresti usare una di quelle o una delle euristiche che ti danno approssimazioni.

Se vuoi minimizzare il massimo , è un problema più semplice sebbene sia NP-difficile: puoi fare una ricerca binaria sulla risposta; per un valore particolare d, disegna i bordi per le coppie che hanno f (x, y)

Se vuoi minimizzarlo lessicograficamente , è banale: scegli la coppia con la distanza più breve e mettila come arr [0], arr [1], quindi scegli arr [ 2] quello più vicino ad arr [1] e così via.

A seconda della provenienza delle f (,), questo potrebbe essere un problema molto più semplice di TSP; sarebbe utile menzionarlo anche tu.

Answer 2

Non sei del tutto chiaro su cosa stai ottimizzando: la somma dei valori f (a [i], a [i + 1]), il massimo di essi o qualcos'altro?

In ogni caso, con i tuoi limiti di velocità, l'avidità è probabilmente la soluzione migliore: scegli un elemento per fare uno [0] (non importa quale a causa dell'involucro), quindi scegli ogni elemento successivo a [i + 1] per essere quello che minimizza f (a [i], a [i + 1]).

Sarà O (n ^ 2), ma con 30 elementi, a meno che questo non sia in un ciclo interno o qualcosa che andrà bene. Se f () è veramente associativo e commutativo, allora potresti essere in grado di farlo in O (n log n). Chiaramente non più veloce riducendo all'ordinamento.

Answer 3

Non credo che il problema sia ben definito in questo modulo:

Definiamo invece n fcns g_i: Perms - > Real

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

Dire che vuoi minimizzare f su tutte le permutazioni implica davvero che puoi scegliere un valore di i e minimizzare g_i su tutte le permutazioni, ma per ogni p che minimizza g_i , una permaturazione correlata ma diversa minimizza g_j (solo coniugare la permutazione). Quindi quindi non ha senso parlare minimizzando f sulle permutazioni per ogni i .

Answer 4

Se non sappiamo qualcosa di più sulla struttura di f (x, y) questo è un problema NP-difficile. Dato un grafico G e tutti i vertici x, y lascia che f (x, y) sia 1 se non c'è bordo e 0 se c'è un bordo. Ciò che il problema si pone è un ordinamento dei vertici in modo da ridurre al minimo il valore massimo di f (arr [i], arr [i + 1]). Poiché per questa funzione può essere solo 0 o 1, restituire uno 0 equivale a trovare un percorso hamiltoniano in G e 1 sta dicendo che non esiste tale percorso.

La funzione dovrebbe avere una sorta di struttura che non consente questo esempio perché sia ??tracciabile.