Я хочу изучить проблему оптимизации автобусной остановки. Однако теперь я застрял в том, как преобразовать матрицу расстояний в реальные координаты точек.
Я просмотрел много ресурсов и знаю, используя формулу: M(i, j) = 0,5(D(1, j)^2 + D(i, 1)^2 - D (i, j)^2)* для решения задачи введите здесь описание ссылки. Я плохо разбираюсь в математике, и я просто хочу реализовать ее.
Во-первых, я пытаюсь понять принцип математики, и вот мое решение. введите здесь описание ссылки.
Затем я хочу реализовать алгоритм с использованием python для следующего примера. Вот моя матрица, которая представляет разное расстояние для каждой автобусной станции. Я хочу перевести его в координаты точек.
Вот мой код для реализации:
import csv
import numpy as np
import math
class csv_util():
def generate_coordinate_point(self):
'''transfer the distance matrix to the real coordinate points'''
sqrt_result = 2*math.sqrt(2)
matrix = np.array([[0,2,2,sqrt_result],[2,0,sqrt_result,2],[2,sqrt_result,0,2],[sqrt_result,2,2,0]])
gram_matrix = self.calculate_gram_matrix(matrix)
a, b = np.linalg.eig(gram_matrix)
#b = b.astype(np.int16)
a = a.astype(np.int16)
eigen_vector = format(b)
length = a.size
tmp_matrix = np.zeros(length * length)
random_point_matrix = tmp_matrix.reshape(length, length)
for item1 in range(length):
random_point_matrix[item1][item1] = a[item1]
print("the eigen-value is: " + format(random_point_matrix))
print("the eigen-vector is: " + eigen_vector)
new_matrix = (np.sqrt(random_point_matrix))*b
print("the coordinate points: "+format(new_matrix))
def calculate_gram_matrix(self,matrix):
'''get the gram matrix for transfer to the coordinate points'''
length = matrix[0].size
tmp_matrix = np.zeros(length*length)
gram_matrix = tmp_matrix.reshape(length,length)
for item1 in range(length):
for item2 in range(length):
gram_matrix[item1][item2] = (math.pow(matrix[0][item2],2)+math.pow(matrix[0][item1],2)-math.pow(matrix[item1][item2],2))/2
if gram_matrix[item1][item2]<0.1 and gram_matrix[item1][item2]>-0.1:
gram_matrix[item1][item2] = 0
return gram_matrix
Однако результат окончательной матрицы неверен. Результат такой:
the eigen-value is: [[12. 0. 0. 0.]
[ 0. 0. 0. 0.]
[ 0. 0. 4. 0.]
[ 0. 0. 0. 0.]]
-------------
the eigen-vector is: [[ 0.00000000e+00 0.00000000e+00 0.00000000e+00 1.00000000e+00]
[ 4.08248290e-01 -5.77350269e-01 -7.07106781e-01 0.00000000e+00]
[ 4.08248290e-01 -5.77350269e-01 7.07106781e-01 0.00000000e+00]
[ 8.16496581e-01 5.77350269e-01 1.57009246e-16 0.00000000e+00]]
-------------
the coordinate points: [[ 0. 0. 0. 0. ]
[ 0. -0. -0. 0. ]
[ 0. -0. 1.41421356 0. ]
[ 0. 0. 0. 0. ]]
Конечные точки выглядят следующим образом: [0,0],[-0,0,-0,0],[-0,0,1,414421],[0,0,0,0]. В этом примере они не могут быть удовлетворены матрицей расстояний. Помогите, пожалуйста, как получить правильные баллы. Спасибо!