쌍별 거리 세트에서 점 결정

StackOverflow https://stackoverflow.com/questions/182086

  •  05-07-2019
  •  | 
  •  

문제

점 사이의 거리 행렬이 주어지면 이러한 거리를 갖는 n차원 점 집합을 결정하는 알고리즘이 있습니까?(또는 적어도 오류를 최소화합니다)

일종의 유료도로 문제의 n차원 버전과 같습니다.

내가 생각해 낼 수 있는 최선의 방법은 다차원 스케일링을 사용하는 것입니다.

도움이 되었습니까?

해결책

다차원 스케일링 (MDS)을 사용하는 올바른 길을 가고 있지만 MDS는 대규모 데이터 세트에 비현실적입니다. 시간 복잡성은 포인트 수에서 2 차이기 때문입니다. 선형 시간 복잡성이 있고 인덱싱에 더 적합한 FastMap을보고 싶을 수도 있습니다. 보다:

Christos Faloutsos와 King-IP Lin : "FastMap : 기존 및 멀티미디어 데이터 세트의 인덱싱, 데이터 마이닝 및 시각화를위한 빠른 알고리즘, Proc. 시그 모드, 1995, doi : 10.1145/223784.223812

다른 팁

당신은 이것을 위해 "속임수"를하고 반복적 인 수치 방법을 사용할 수 있습니다. 모든 지점을 초기에 "무작위"위치에있게 한 다음, 필요한 거리로 비례 적으로 서로 멀리 이동하십시오. 이것은 몇 가지 점을 선호하지만 적용하기 전에 평균 이동을 취하면 평균을 적용하면이 문제가 제거됩니다. 이것은 O (n²) 알고리즘이지만 구현하고 이해하기가 매우 간단합니다. 아래 2D 예에서 아래의 오류는 << 10%이지만, 주어진 거리가 비현실적이라면 그렇게 잘 작동하지 않을 수 있습니다.

C ++ 예 :

#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define DAMPING_FACTOR 0.99f

class point
{
public:
    float x;
    float y;
public:
    point() : x(0), y(0) {}
};

// symmetric matrix with distances
float matrix[5][5] =    {
                            { 0.0f, 4.5f, 1.5f, 2.0f, 4.0f },
                            { 4.5f, 0.0f, 4.0f, 3.0f, 3.5f },
                            { 1.5f, 4.0f, 0.0f, 1.0f, 5.0f },
                            { 2.0f, 3.0f, 1.0f, 0.0f, 4.5f },
                            { 4.0f, 3.5f, 5.0f, 4.5f, 0.0f }
                        };
int main(int argc, char** argv)
{
    point p[5];
    for(unsigned int i = 0; i < 5; ++i)
    {
        p[i].x = (float)(rand()%100)*0.1f;
        p[i].y = (float)(rand()%100)*0.1f;
    }

    // do 1000 iterations
    float dx = 0.0f, dy = 0.0f, d = 0.0f;
    float xmoves[5], ymoves[5];

    for(unsigned int c = 0; c < 1000; ++c)
    {
        for(unsigned int i = 0; i < 5; ++i) xmoves[i] = ymoves[i] = 0.0f;
        // iterate across each point x each point to work out the results of all of the constraints in the matrix
        // collect moves together which are slightly less than enough (DAMPING_FACTOR) to correct half the distance between each pair of points
        for(unsigned int i = 0; i < 5; ++i)
        for(unsigned int j = 0; j < 5; ++j)
        {
            if(i==j) continue;
            dx = p[i].x - p[j].x;
            dy = p[i].y - p[j].y;
            d = sqrt(dx*dx + dy*dy);
            dx /= d;
            dy /= d;
            d = (d - matrix[i][j])*DAMPING_FACTOR*0.5f*0.2f;

            xmoves[i] -= d*dx;
            ymoves[i] -= d*dy;

            xmoves[j] += d*dx;
            ymoves[j] += d*dy;
        }

        // apply all at once
        for(unsigned int i = 0; i < 5; ++i)
        {
            p[i].x += xmoves[i];
            p[i].y += ymoves[i];
        }
    }

    // output results
    printf("Result:\r\n");
    for(unsigned int i = 0; i < 5; ++i)
    {
        for(unsigned int j = 0; j < 5; ++j)
        {
            dx = p[i].x - p[j].x;
            dy = p[i].y - p[j].y;
            printf("%f ", sqrt(dx*dx + dy*dy));
        }
        printf("\r\n");
    }

    printf("\r\nDesired:\r\n");
    for(unsigned int i = 0; i < 5; ++i)
    {
        for(unsigned int j = 0; j < 5; ++j)
        {
            printf("%f ", matrix[i][j]);
        }
        printf("\r\n");
    }

    printf("Absolute difference:\r\n");
    for(unsigned int i = 0; i < 5; ++i)
    {
        for(unsigned int j = 0; j < 5; ++j)
        {
            dx = p[i].x - p[j].x;
            dy = p[i].y - p[j].y;
            printf("%f ", abs(sqrt(dx*dx + dy*dy) - matrix[i][j]));
        }
        printf("\r\n");
    }

    printf("Press any key to continue...");

    while(!_kbhit());

    return 0;
}

이 작업을 수행하기위한 알고리즘이 있습니다 집단 지능 프로그래밍, p. 49, "2 차원의 데이터보기", N- 차이에 적응할 수 있습니다.

이봐 - 다차원 스케일링입니다. 그래서 당신이 올바른 길을 가고 있다고 생각합니다.

담당자가 충분하지 않아 원본을 편집할 수 없지만 여기서 문제를 다시 언급하려고 했습니다.

OP에는 거리의 입력 NxN 행렬이 있습니다.그는 점을 나타내는 N차원 좌표의 출력 배열 크기 N을 생성하려고 합니다. 여기서 각 점 사이의 거리는 입력 행렬에 저장됩니다.

일반적인 경우에는 이 문제를 해결할 수 없습니다.

다음과 같은 행렬이 있다고 가정해 보겠습니다.

   A  B  C  
A  x  1  2  
B     x  0  
C        x

A는 B로부터 1단위 거리(예: 1미터) 떨어져 있고, A는 C로부터 1미터 떨어져 있습니다.그런데 B와 C는 같은 자리에 있다.

이 특별한 경우 최소 오류 합계는 1미터이며, 해당 결과를 달성하는 솔루션은 무한히 다양합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top