Algoritmo per trovare le coppie corrispondenti in un elenco

Question

Definirò il problema nella forma precisa che desidero di seguito:

Data :     Due elenchi a virgola mobile N e D della stessa lunghezza k ( k è multiplo di 2).     È noto che per tutti i i = 0, ..., k-1 , esiste j! = I tale che D [j] * D [ i] == N [i] * N [j] . (Sto utilizzando l'indicizzazione in base zero)

Return :     Un elenco (lunghezza k / 2 ) di coppie (i, j) tale che D [j] * D [i] == N [i] * N [j] .     Le coppie restituite potrebbero non essere univoche (qualsiasi elenco valido di coppie va bene)

L'applicazione per questo algoritmo è di trovare coppie reciproche di autovalori di un problema di autovalori palindromici generalizzati. La condizione di uguaglianza è equivalente a N [i] / D [i] == D [j] / N [j] , ma funziona anche quando i denominatori sono zero (che è una possibilità definita). Le degenerazioni nel problema degli autovalori fanno sì che le coppie non siano univoche.

Più in generale, l'algoritmo è equivalente a:

Data :     Un elenco X di lunghezza k ( k è multiplo di 2).     È noto che per tutti i i = 0, ..., k-1 , esiste j! = I tale che IsMatch (X [i], X [j]) restituisce true, dove IsMatch è una funzione di corrispondenza booleana che è garantita per restituire true per almeno un j! = I per tutti < code> i .

Return :     Un elenco (di lunghezza k / 2 ) di coppie (i, j) tale che IsMatch (i, j) == true per tutte le coppie nella lista.     Le coppie restituite potrebbero non essere univoche (qualsiasi elenco valido di coppie va bene)

Ovviamente, il mio primo problema può essere formulato in termini di secondo con IsMatch (u, v): = {(u - 1 / v) == 0} . Ora, a causa dei limiti della precisione in virgola mobile, non ci sarà mai l'uguaglianza esatta, quindi voglio la soluzione che minimizzi l'errore di corrispondenza. In altre parole, supponiamo che IsMatch (u, v) restituisca il valore u - 1 / v e voglio che l'algoritmo restituisca un elenco per il quale IsMatch restituisce il set minimo di errori. Questo è un problema di ottimizzazione combinatoria. Pensavo di poter prima calcolare in modo ingenuo l'errore di corrispondenza tra tutte le possibili coppie di indici i e j , ma quindi avrei bisogno di selezionare il set di errori minimi, e io non so come lo farei.

Chiarimento

La funzione IsMatch è riflessiva ( IsMatch (a, b) implica IsMatch (b, a) ), ma non transitiva. Tuttavia, è 3-transitivo: IsMatch (a, b) & amp; & amp; IsMatch (b, c) & amp; & amp; IsMatch (c, d) implica IsMatch (a, d) .

Addendum

Questo problema è apparentemente identicamente il problema della corrispondenza perfetta del peso minimo nella teoria dei grafi. Tuttavia, nel mio caso so che dovrebbe esserci un "buono" abbinamento perfetto, quindi la distribuzione dei pesi dei bordi non è del tutto casuale. Sento che queste informazioni dovrebbero essere utilizzate in qualche modo. La domanda ora è se esiste una buona implementazione del problema di corrispondenza del peso minimo perfetto che utilizza le mie conoscenze precedenti per arrivare a una soluzione all'inizio della ricerca. Sono anche aperto a suggerimenti per una semplice implementazione di tale algoritmo.

Answer 1

Bene, ho finito per usare questo codice Fortran con porting , dove specifica semplicemente la densa matrice della distanza triangolare superiore usando:

complex_t num = N[i]*N[j] - D[i]*D[j];
complex_t den1 = N[j]*D[i];
complex_t den2 = N[i]*D[j];
if(std::abs(den1) < std::abs(den2)){
    costs[j*(j-1)/2+i] = std::abs(-num/den2);
}else if(std::abs(den1) == 0){
    costs[j*(j-1)/2+i] = std::sqrt(std::numeric_limits<double>::max());
}else{
    costs[j*(j-1)/2+i] = std::abs(num/den1);
}

Funziona benissimo ed è abbastanza veloce per i miei scopi.

Answer 2

Spero di avere il tuo problema.

Bene, se IsMatch (i, j) e IsMatch (j, l) quindi IsMatch (i, l) . Più in generale, la relazione IsMatch è transitiva, commutativa e riflessiva, vale a dire. è una relazione di equivalenza. L'algoritmo si traduce in quale elemento appare più volte nell'elenco (utilizzare IsMatch invece di =).

Answer 3

(Se capisco il problema ...) Ecco un modo per abbinare ogni coppia di prodotti nei due elenchi.

1. Moltiplica ciascuna coppia N e salvala in una struttura con il prodotto e i pedici degli elementi che compongono il prodotto.
2. Moltiplica ciascuna coppia D e salvala in una seconda istanza della struttura con il prodotto e i pedici degli elementi che compongono il prodotto.
3. Ordina entrambe le istruzioni sul prodotto.
4. Effettua un passaggio di tipo merge attraverso entrambi gli array di strutture ordinate. Ogni volta che trovi un prodotto di un array abbastanza vicino all'altro, puoi registrare i due pedici di ciascun elenco ordinato per una corrispondenza.
5. Puoi anche usare un elenco ordinato per una funzione ismatch, facendo una ricerca binaria sul prodotto.

Answer 4

bene??Moltiplica ciascuna coppia D e salvala in una seconda istanza della struttura con il prodotto e i pedici degli elementi che compongono il prodotto.

Answer 5

Ho appena chiesto al mio amico CS, e ha escogitato l'algoritmo di seguito. Non ha un account qui (e apparentemente non disposto a crearne uno), ma penso che valga la pena condividere la sua risposta.

// We will find the best match in the minimax sense; we will minimize
// the maximum matching error among all pairs. Alpha maintains a
// lower bound on the maximum matching error. We will raise Alpha until
// we find a solution. We assume MatchError returns an L_1 error.

// This first part finds the set of all possible alphas (which are
// the pairwise errors between all elements larger than maxi-min
// error.
Alpha = 0
For all i:
    min = Infinity
    For all j > i:
        AlphaSet.Insert(MatchError(i,j))
        if MatchError(i,j) < min
            min = MatchError(i,j)
    If min > Alpha
        Alpha = min

Remove all elements of AlphaSet smaller than Alpha

// This next part increases Alpha until we find a solution
While !AlphaSet.Empty()
    Alpha = AlphaSet.RemoveSmallest()
    sol = GetBoundedErrorSolution(Alpha)
    If sol != nil
        Return sol

// This is the definition of the helper function. It returns
// a solution with maximum matching error <= Alpha or nil if
// no such solution exists.
GetBoundedErrorSolution(Alpha) :=
    MaxAssignments = 0
    For all i:
        ValidAssignments[i] = empty set;
        For all j > i:
            if MatchError <= Alpha
                ValidAssignments[i].Insert(j)
                ValidAssignments[j].Insert(i)

        // ValidAssignments[i].Size() > 0 due to our choice of Alpha
        // in the outer loop

        If ValidAssignments[i].Size() > MaxAssignments
            MaxAssignments = ValidAssignments[i].Size()
    If MaxAssignments = 1
        return ValidAssignments
    Else
        G = graph(ValidAssignments)
        // G is an undirected graph whose vertices are all values of i
        // and edges between vertices if they have match error less
        // than or equal to Alpha
        If G has a perfect matching
            // Note that this part is NP-complete.
            Return the matching
        Else
            Return nil

Si basa sulla capacità di calcolare una corrispondenza perfetta di un grafico, che è NP-completo, ma almeno si riduce a un problema noto. Si prevede che la soluzione sia NP-completa, ma questo è OK poiché in pratica le dimensioni degli elenchi indicati sono piuttosto piccole. Aspetterò una risposta migliore per qualche giorno, o se qualcuno si espanderà su come trovare la corrispondenza perfetta in modo ragionevole.

Answer 6

Vuoi trovare j tale che D (i) * D (j) = N (i) * N (j) {Ho assunto * è la moltiplicazione reale ordinaria}

supponendo che tutti gli N (i) siano diversi da zero, let

Z (i) = D (i) / N (i).

Problema: trova j, in modo che Z (i) = 1 / Z (j).

Suddividi l'insieme in aspetti positivi e negativi e elaboralo separatamente.

accetta i log per chiarezza. z (i) = log Z (i).

Ordina indirettamente. Quindi nella vista ordinata dovresti avere qualcosa come -5 -3 -1 +1 +3 +5, per esempio. Leggi le coppie +/- e questo dovrebbe darti gli indici originali.

Mi sto perdendo qualcosa o il problema è semplice?

Answer 7

Dovresti essere in grado di ordinare le coppie (D [i], N [i]). Non è necessario dividere per zero: puoi semplicemente moltiplicare, come segue:

bool order(i,j) {
  float ni= N[i]; float di= D[i];
  if(di<0) { di*=-1; ni*=-1; }

  float nj= N[j]; float dj= D[j];
  if(dj<0) { dj*=-1; nj*=-1; }

  return ni*dj < nj*di;
}

Quindi, scansiona l'elenco ordinato per trovare due punti di separazione: (N == D) e (N == -D); puoi iniziare ad abbinare coppie reciproche da lì, usando:

abs(D[i]*D[j]-N[i]*N[j])<epsilon

come controllo di validità. Lasciare i punti (N == 0) e (D == 0) per ultimi; non importa se li consideri negativi o positivi, poiché si abbineranno tutti l'uno con l'altro.

modifica: in alternativa, puoi semplicemente gestire i casi (N == 0) e (D == 0) separatamente, rimuovendoli dall'elenco. Quindi, puoi usare (N [i] / D [i]) per ordinare il resto degli indici. Potresti comunque voler iniziare da 1.0 e -1.0, per assicurarti di poter abbinare casi quasi zero con casi esattamente zero.