Encuentre las distancias sumadas más pequeñas combinando de forma única elementos de un conjunto con elementos de otro conjunto

8

Como entrada tengo dos conjuntos de puntos en R N , típicamente para N grande, por ejemplo N = 40. Supongamos que ambos conjuntos tienen m elementos:

S = s 1 ... s m

T = t 1 ... t m

Semánticamente ambos conjuntos son iguales, pero debido al ruido (de cualquier tipo) en los puntos R ^ N, los elementos que deberían ser semánticamente iguales todavía tienen una distancia mayor que 0.

Lo que quiero encontrar es m tuplas (s i , t j ) de modo que la suma de la distancia (s i , t j ) se minimice y tal que s k y t k ocurran exactamente una vez en el conjunto de tuplas para k = 1 ...metro. Básicamente (i, j) deben elegirse como torres en un tablero de ajedrez que no pueden golpearse entre sí mientras minimizan las distancias sumadas.

En otras palabras, quiero encontrar un mapa uno a uno entre S y T que 'sea una especie de mapa de identidad, pero robusto al ruido'. Suponemos que la medida de la distancia es una buena indicación de cuán similares son los elementos.

Básicamente necesito encontrar una permutación de 1 ... N, y por lo tanto creo que este problema es NP-hard o NP-complete, ya que 'se siente' bastante similar al TSP; sin embargo, no he podido reescribir el problema de TSP a un subconjunto de mi problema aquí.

¿Es este problema realistamente solucionable para N grande? ¿Hay un nombre para este problema? ¿Cuál sería una solución factible? ¿Hay otro criterio que podría ser mejor que las distancias sumadas?

Pensé en un enfoque codicioso, que D sea una matriz de las distancias, d ij = distancia (s i , t j ).

T = {}
while D is not empty:
    (i,j) = argmin-(i,j) dij
    append (i,j) to T
    set row i and column j to infinity.

Esto no da como resultado la solución óptima, pero encuentra una solución. ¿Sería esta mi mejor apuesta? ¿Debo usar recocido simulado o es exagerado?

PD: desde mi punto de vista, este es solo un problema menor en un problema de LD más grande, sin embargo, estoy muy interesado en los antecedentes de CS.

Herbert
fuente
No estoy seguro, pero ¿tal vez este hilo puede ser de ayuda para usted?
Estoy muy interesado en este problema, ya que también me he encontrado con él al diseñar algunos algoritmos de ML ...
daaxix
No puedo ver ninguna manera de evitar resolver el problema de la suma de las raíces cuadradas como parte de este problema. (Tampoco veo ningún argumento de que este problema sea tan difícil como SoSR).
"Básicamente, necesito encontrar una permutación de 1 ... N, y por lo tanto creo que este problema es NP-hard o NP-complete", al igual que ordenar, ¿hm?
Raphael
@Raphael: Buen punto. Fue más una sensación instintiva, que, como se indica en el OP, no puedo encontrar argumentos. De ahí la pregunta "¿Es este problema realistamente solucionable para N grande?"
Herbert

Respuestas:

6

Este es el problema de encontrar la coincidencia máxima en un gráfico bipartito ponderado. Existen algoritmos eficientes que resuelven este problema en tiempo polinómico.

Básicamente, tiene un gráfico bipartito completo con 2metro vértices S forma un conjunto de vértices; Tforma el otro conjunto de vértices. Para cadayo,j, crea una ventaja desde syo a tj cuyo peso es igual a -re(syo,tj), la negación de la distancia entre syo y tj.

Ahora, desea encontrar una coincidencia cuyo peso sea lo más grande posible. Esto corresponde a un conjunto de pares(syo,tj)cuya distancia total es lo más pequeña posible. A partir de ahí, puede usar algoritmos existentes en este gráfico para encontrar la coincidencia de peso máximo.

DW
fuente
3

Aquí hay un método probabilístico rápido que podría funcionar para usted.

  1. Proyecte sus puntos en una línea aleatoria y resuelva el problema de coincidencia 1D en esta línea.

  2. Repita el proceso para un puñado de diferentes líneas aleatorias para obtener una colección de coincidencias de candidatos.

  3. Haga que sus coincidencias de candidatos "voten" punto por punto para llegar a la "mejor" coincidencia.

Nick Alger
fuente