تحديد النقاط من مجموعة المسافات الزوجية

Question

بالنظر إلى مصفوفة المسافات بين النقاط، هل توجد خوارزمية لتحديد مجموعة من النقاط ذات الأبعاد n التي لها هذه المسافات؟(أو على الأقل تقليل الخطأ)

نوعًا ما مثل نسخة ذات أبعاد n لمشكلة الباب الرئيسي.

أفضل ما يمكنني التوصل إليه هو استخدام القياس متعدد الأبعاد.

Answer 1

وأنت على الطريق الصحيح مع التوسع متعدد الأبعاد (MDS)، ولكن MDS غير عملي لمجموعات البيانات الكبيرة، مع مرور الوقت تعقيدها هو من الدرجة الثانية في عدد من النقاط. قد ترغب في النظر في FastMap، التي لديها الخطي الوقت التعقيد وهو أكثر ملاءمة للفهرسة. انظر:

<اقتباس فقرة>   

وكريستوس فالوتسوس والملك الملكية الفكرية لين:   "FastMap: خوارزمية سريعة ل   الفهرسة والبيانات والتعدين   التصور التقليدي و   مجموعات البيانات والوسائط المتعددة، في <ط> بروك.   SIGMOD ، 1995، دوى: 10.1145 / 223784،223812

Answer 2

يمكنك "الغش" واستخدام طريقة رقمية تكرارية لهذا الغرض.خذ جميع النقاط لتكون في بعض المواضع "العشوائية" في البداية، ثم قم بالتمرير عبرها، وحركها بعيدًا عن بعضها البعض بشكل متناسب مع المسافة المطلوبة.هذا سيفضل بعض النقاط، لكن أخذ متوسط ​​التحركات قبل تطبيقها ثم تطبيق المتوسط ​​سيزيل هذه المشكلة.هذه خوارزمية O(n²)، ولكنها سهلة التنفيذ والفهم.في المثال ثنائي الأبعاد أدناه، يكون الخطأ << 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;
}

Answer 3

وهناك خوارزمية للقيام بذلك في البرمجة الجماعية المخابرات ، ص . 49، "عرض البيانات في بعدين"، والتي يمكن تكييفها لن الأبعاد.

ويا - انها التحجيم متعدد الأبعاد -. لذا أعتقد أنك على الطريق الصحيح

Answer 4

وأنا لا يمكن تعديل النص الأصلي، لأنني لم يكن لديك ما يكفي من مندوب، ولكني حاولت أن أكرر المشكلة هنا.

ووOP له مدخلا NxN مصفوفة من المسافات. انه يريد إنشاء صفيف الإخراج، حجم N، الإحداثيات N-الأبعاد التي تمثل نقطة، حيث يتم تخزين المسافة بين كل نقطة في المصفوفة الإدخال.

ملحوظة أن هذه ليست قابلة للحل في الحالة العامة:

لنفترض لدي مصفوفة مثل هذا

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

و(أ) هو 1 وحدة المسافة (مثلا 1 متر) بعيدا عن B، و A هو متر واحد بعيدا عن C. ولكن B و C هي في نفس المكان.

في هذه الحالة بالذات مبلغ الحد الأدنى من الأخطاء هو 1 متر، وهناك طائفة لا حصر لها من الحلول التي تحقق تلك النتيجة