Угадывание декартовых координат вершин из матрицы расстояний

Я пытаюсь найти программу, которая бы выяснила правильное расположение вершин в 2-й системе координат xy, учитывая матрицу расстояний (или список смежности) графа, обозначающего расстояния по весам ребер.

Первоначально я написал поиск грубой силы. Затем я решил изменить программу на C ++, чтобы решить матричное уравнение AB = C, что я и сделал раньше, чтобы решить эту проблему.

ВВОД:
матрица расстояний

ВЫХОД :
координаты вершин, которые будут удовлетворять заданной матрице расстояний с учетом веса ребер как расстояния между двумя вершинами в плоскости 2d-xy.

Это пример запуска моей программы:

The original adjacency matrix:
0 1 1.41 1
1 0 1 1.41
1.41 1 0 1
1 1.41 1 0The coordinates which can satisfy the given input adjacency matrix with edge weight   denoting distance are :
[24.327,0.40545]
[25.5472,0.425787]
[25.5306,1.42551]
[24.3103,1.40517]The calculated adjacency matrix from the solution we got from CrossEntropy Method is :
0 1.10473 1.25607 0.999931
1.10473 0 0.999931 1.25607
1.25607 0.999931 0 1.10473
0.999931 1.25607 1.10473 0

Теперь я вижу, что это дает приблизительное решение. Или я мог бы сказать, что пытается. Но это не удовлетворительно. Когда я смотрел на пригодность каждой итерации, она была почти постоянной после нескольких первых шагов. Это означает, что фитнес не сильно улучшается.

Предположения
1. моя программа генерирует эту матрицу смежности случайным образом.
2. фитнес-переменная противоположна своему значению в коде. Чем выше ценность фитнеса, тем ниже качество решения

МОЙ ВОПРОС: >> Как настроить эту программу так, чтобы она давала лучшие результаты (я пытался изменить скорость обучения и количество выборок, но без особого успеха). Что я делаю неправильно и Как сделать его более точным. Есть ли какой-то другой простой способ сделать это, я имею в виду всю проблему получения координат из матрицы смежности?

Этот код такой:

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<iostream>
using namespace std;#define UPPER_LIMIT 20 // this is the upper limit to the distances given in adjacency matrix,
const int SQSZ=  UPPER_LIMIT*3;  // this is half the size of our finite cartesian coordiante system , which will go from 0 to 2*SQSZ in x as well as y
double SQR(double X ) { return  X*X ; }
#define LOWER_BOUND -SQSZ
#define UPPER_BOUND SQSZ
#define num_samples 100 //number of samples we want to generate in every iteration, our population count
#define num_update 5    //number of top members of population we are taking to modify our distribution
#define max_iter 200   //total number of iterations
#define problem_size 4 // number of vertices in graph
#define alpha 0.7 //learning rate

struct sample{
double arr[problem_size];
double cost;
};

typedef struct sample sample;

const int n = problem_size,m = problem_size;

double a[m][n] , b[m];
sample best;
sample samples[num_samples];
sample selected[num_update];
double means[problem_size];
double stdev[problem_size];/* the following function takes the input adjacency , */
int take_input()
{
srand(time(NULL));
/*
for(int i =0; i<  m; i++)
for(int j =0; j<n; j++)
if( i > j ) a[i][j] = a[j][i] = rand()%UPPER_LIMIT;
else a[i][j] = a[j][i] = 0;
*/
cout<<"Input the distance matrix of size "<< problem_size<<"X"<<problem_size<<endl;
for(int i =0 ; i<  m ; i++)
for(int j  =0; j <n  ; j++){
cin >> a[i][j];

}// for(int  i =0; i< m; i++)
//     scanf("%lf",&b[i]);

}void print_matrix()
{

for(int i =0; i<m ; i++,printf("\n"))
for(int j =0 ; j<n; j++)
cout << a[i][j] << " ";
cout<<endl;
}// what I am doing here is treating each value in a single sample as a creator of x,y corrdinate, by using fmod and division.
double dist(double a,double b)
{
// cout<<"dist("<<a<<" "<<b<<")" << endl;
double ax,ay,bx,by;
ax = fmod(a,SQSZ);
ay = a/SQSZ;
bx = fmod(b,SQSZ);
by = b/SQSZ;

return sqrt(hypot((ax-bx), (ay-by) ));
}

// just to decompose the sample value into x and y coordinate and print it
void decom(double a)
{
double x = fmod(a,SQSZ);
double y = a/SQSZ;

cout <<"["<< x<< "," << y << "]" << endl;
}/* simple comparision function to compare cost */
bool cmp( sample   a , sample  b )
{
if( a.cost < b.cost )
return true;
else
return false;

}/* find average of means of best part of population */
double mean_attr(int x )
{
double sum = 0.0;
for(int i=0; i< num_update; i++)
sum += selected[i].arr[x];
return sum / num_update;
}/* find the average standard deviation for best part of population */
double stdev_attr(int x,double mean)
{
double sum = 0.0;

for(int i =0; i<num_update; i++)
sum += (selected[i].arr[x] - mean)*(selected[i].arr[x] - mean);
return sqrt( sum / num_update);
}

/* returns a random number between a to b  */
double random_variable(double a ,double b){

return  a + (( b - a )*((double)rand()/RAND_MAX) );
}/* returns a value depending on mean and stdev according to gaussian distribution fucntion */
double random_gaussian(double mean , double stdev)
{
double u1,u2,w;
do {
u1 = 2*((double)rand()/RAND_MAX) - 1;
u2 = 2*((double)rand()/RAND_MAX) - 1;
w = u1*u1 + u2 * u2;
}   while( w >= 1 );

w = sqrt(( -2.0 * log(w ))/w);
return mean + ( u2* w ) * stdev;
}
/* evaluate our samples , returns the cost of our solution */
double evaluate(int x)
{

double sum = 0.0;

// double delta_array[m];

for(int i =0; i<m ; i++)
for(int j =0; j< n; j++)
{
double y = 0.0;
y =  a[i][j] - dist( samples[x].arr[i] +SQSZ, samples[x].arr[j] + SQSZ );
sum += y*y;

//         cout << "hii there" << y*y << endl;
//         fflush(stdout);
//         system("sleep 0.1");
}

/*
for( int i =0; i< m; i++)
{

delta_array[i] = 0.0;
for(int j =0; j<n; j++)
delta_array[i] = ( delta_array[i] + ( (a[i][j]) *samples[x].arr[j] ));
delta_array[i] =delta_array[i] - b[i];
sum += delta_array[i] * delta_array[i];

}
*/
return sum;
}int main()
{take_input();best.cost = -1; // intially we don't have any best , so its initial value is -1

//  cout<<"Given random adjacency matrix"<<endl;
// print_matrix();for(int i =0; i< problem_size; i++){
means[i] = random_variable(LOWER_BOUND,UPPER_BOUND);
stdev[i] = UPPER_BOUND - LOWER_BOUND;
}for(int iter =0; iter < max_iter ; iter++ )
{for(int  i =0; i< num_samples; i++)
{

for(int j=0; j< problem_size; j++)
{

samples[i].arr[j] = random_gaussian(means[j],stdev[j]);

if( samples[i].arr[j] < LOWER_BOUND ) samples[i].arr[j] = LOWER_BOUND;
if( samples[i].arr[j] > UPPER_BOUND ) samples[i].arr[j]  = UPPER_BOUND;
}
samples[i].cost = evaluate(i);
}sort( samples,samples+num_samples,cmp);if( best.cost == -1  || best.cost > samples[0].cost )
{
best.cost = samples[0].cost;
for(int i=0; i<problem_size; i++)
best.arr[i] = samples[0].arr[i];
}for(int j=0; j< num_update;j++){
selected[j].cost = samples[j].cost;
for(int k =0; k< problem_size; k++)
selected[j].arr[k] = samples[j].arr[k];
}
for(int j=0; j< problem_size; j++)
{
means[j] = alpha*means[j] + ( 1.0 - alpha) * mean_attr(j);
stdev[j] = alpha*stdev[j] + ( 1.0 - alpha) * stdev_attr(j,means[j]);
}//  printf(" > iteration = %d , fitness = %lf\n",iter,best.cost );
fflush(stdout);

}//printf("Solution : f = %lf\n",best.cost );cout<<"The original adjacency matrix:"<< endl;
print_matrix();
cout << "The coordinates which can satisfy the given input adjacency matrix with edge weight denoting distance are :"<< endl;
for(int i =0; i< problem_size; i++)
decom(best.arr[i] + SQSZ);

cout<<endl;cout<<"The calculated adjacency matrix from the solution we got from CrossEntropy Method is :"<<endl;
// printing our solutions adjacency matrix
for(int i =0; i<n; i++,printf("\n"))
for(int j =0 ; j<m ;j++)
cout << dist(best.arr[i] +SQSZ, best.arr[j] + SQSZ)<< " ";

cout<<endl;
return 0;
}

Заранее спасибо :).

ОБНОВИТЬ:

Я выставил простую матрицу расстояний, т.е. единичный квадрат на входе, и он дает правильный результат. Но я не знаю, как протестировать свою программу, поскольку создание таких графиков является для меня еще одной проблемой.