matlab解一个点到三十个点的最短距离

Question

三十个点的坐标是
42.37 19.30
54.48 91.96
52.80 28.87
18.51 55.09
8.17 91.93
46.41 9.00
3.06 25.77
43.50 42.70
55.79 57.77
63.88 89.95
3.42 21.82
70.99 96.70
16.93 43.40
59.34 78.48
60.81 52.52
77.24 33.13
5.63 43.16
85.47 71.79
38.43 91.62
39.96 89.00
32.54 13.47
55.54 11.99
29.54 89.35
36.61 65.31
34.90 4.03
63.02 50.47
66.44 89.45
99.21 38.57
94.44 29.21
35.03 23.40
求一个点到他们所有点路径最短并绘图
求解啊

Answer 1

兄弟，你的问题可以归结为所有距离之和的最小值问题。我推导了一下，并且给写了代码

function  ABC
clc;
clear;
close all;
global  R

R=[42.37     19.30
    54.48     91.96
    52.80     28.87
    18.51     55.09
    8.17     91.93
    46.41     9.00
    3.06     25.77
    43.50     42.70
    55.79     57.77
    63.88     89.95
    3.42     21.82
    70.99     96.70
    16.93     43.40
    59.34     78.48
    60.81     52.52
    77.24     33.13
    5.63     43.16
    85.47     71.79
    38.43     91.62
    39.96     89.00
    32.54     13.47
    55.54     11.99
    29.54     89.35
    36.61     65.31
    34.90     4.03
    63.02     50.47
    66.44     89.45
    99.21     38.57
    94.44     29.21
    35.03     23.40  ];


x0 = [-5; -5];  % Make a starting guess at the solution
options = optimoptions('fsolve','Display','iter','Jacobian','on'); % Option to display output
[x,fval] = fsolve(@GetFJ,x0,options) % Call solver

figure;
hold on;
grid on;
N=length(R(:,1));
for i=1:N
    plot([x(1) R(i,1)],[x(2) R(i,2)],'.-');
end

end

function [F J]= GetFJ( Rx )
global  R
F=zeros(2,1);
J=zeros(2,2);
N=length(R(:,1));
for i=1:N
    dist = norm(Rx'-R(i,:),2);
    if( dist < 1E-9 )
        continue;
    end
    F(1) = F(1) + (Rx(1)-R(i,1))/dist;
    F(2) = F(2) + (Rx(2)-R(i,2))/dist;
    
    J(1,1)=J(1,1)-(Rx(1)-R(i,1))*(Rx(1)-R(i,1))/dist^3+1/dist;
    J(1,2)=J(1,2)-(Rx(1)-R(i,1))*(Rx(2)-R(i,2))/dist^3;
    J(2,1)=J(2,1)-(Rx(1)-R(i,1))*(Rx(2)-R(i,2))/dist^3;
    J(2,2)=J(2,2)-(Rx(2)-R(i,2))*(Rx(2)-R(i,2))/dist^3+1/dist;    
end
end

计算结果：

x =

          47.9324808518899
           51.177556034619


fval =

     -1.39904476892383e-10
      1.05504605052431e-10

画图

追问

??? Undefined function or method 'optimoptions' for input arguments of type 'char'.
Error in ==> ABC at 40
options = optimoptions('fsolve','Display','iter','Jacobian','on'); % Option to display output

追答

你什么版本的matlab？把我给你的代码全都贴到一个m文件中

追问

2010

追答

我用的是2013，可能你这个版本还没有雅克比功能，把
options = optimoptions('fsolve','Display','iter','Jacobian','on');

改成
options = optimoptions('fsolve','Display','iter');
应该就可以了

追问

不行

追答

具体什么错误？

Answer 2

这是一个求解“点到多点最短路径”的问题，可以使用图论算法中的Dijkstra算法或者A*算法来解决。由于只有30个点，使用Dijkstra算法就可以得到最短路径。具体实现步骤如下：

定义一个二维数组存储所有点之间的距离，使用无穷大表示两点不连通。

const int INF = 1e9;
double dist[30][30] = {
   {0},
   {INF, 0},
   {INF, INF, 0},    // ... 省略剩下的行和列，初始化为INF};
const int INF = 1e9;
double dist[30][30] = {
   {0},
   {INF, 0},
   {INF, INF, 0},
   // ... 省略剩下的行和列，初始化为INF
};

根据给定的点坐标，计算出所有点之间的距离，更新距离数组。

for (int i = 0; i < 30; i++) {
   for (int j = i+1; j < 30; j++) {
       double dx = points_x[i] - points_x[j];
       double dy = points_y[i] - points_y[j];
       double dz = points_z[i] - points_z[j];
       double dis = sqrt(dx*dx + dy*dy + dz*dz);
       dist[i][j] = dist[j][i] = dis;
   }
}
for (int i = 0; i < 30; i++) {
   for (int j = i+1; j < 30; j++) {
       double dx = points_x[i] - points_x[j];
       double dy = points_y[i] - points_y[j];
       double dz = points_z[i] - points_z[j];
       double dis = sqrt(dx*dx + dy*dy + dz*dz);
       dist[i][j] = dist[j][i] = dis;
   }
}

使用Dijkstra算法求解给定点到其他所有点的最短路径。

int src = 0; // 源点
double shortest_path[30]; // 存储最短路径长度
int predecessor[30]; // 存储路径上前驱结点
bool visited[30] = {false}; // 存储结点是否已经访问
for (int i = 0; i < 30; i++) {
   shortest_path[i] = INF;
}
shortest_path[src] = 0;
for (int i = 0; i < 30; i++) {
   int u = -1;
   double shortest = INF;
   for (int j = 0; j < 30; j++) {
       if (!visited[j] && shortest_path[j] < shortest) {
           u = j;
           shortest = shortest_path[j];
       }
   }
   if (u == -1) {
       break;
   }
   visited[u] = true;
   for (int v = 0; v < 30; v++) {
       if (!visited[v] && dist[u][v] != INF && shortest_path[u] + dist[u][v] < shortest_path[v]) {
           shortest_path[v] = shortest_path[u] + dist[u][v];
           predecessor[v] = u;
       }
   }
}
int src = 0; // 源点
double shortest_path[30]; // 存储最短路径长度
int predecessor[30]; // 存储路径上前驱结点
bool visited[30] = {false}; // 存储结点是否已经访问
for (int i = 0; i < 30; i++) {
   shortest_path[i] = INF;
}
shortest_path[src] = 0;
for (int i = 0; i < 30; i++) {
   int u = -1;
   double shortest = INF;
   for (int j = 0; j < 30; j++) {
       if (!visited[j] && shortest_path[j] < shortest) {
           u = j;
           shortest = shortest_path[j];
       }
   }
   if (u == -1) {
       break;
   }
   visited[u] = true;
   for (int v = 0; v < 30; v++) {
       if (!visited[v] && dist[u][v] != INF && shortest_path[u] + dist[u][v] < shortest_path[v]) {
           shortest_path[v] = shortest_path[u] + dist[u][v];
           predecessor[v] = u;
       }
   }
}

打印出给定点到其他所有点的最短路径长度和前驱结点，并绘制路径图。

for (int i = 0; i < 30; i++) {    if (i != src) {        printf("Shortest path from %d to %d: %.2f\n", src, i, shortest_path[i]);        printf("Path:");        int j = i;        while (j != src) {            printf(" %d", j);
           j = predecessor[j];
       }        printf(" %d\n", src);
   }
}

Answer 3

function y=func(x)

a=[42.37 19.30

54.48 91.96

52.80 28.87

18.51 55.09

8.17 91.93

46.41 9.00

3.06 25.77

43.50 42.70

55.79 57.77

63.88 89.95

3.42 21.82

70.99 96.70

16.93 43.40

59.34 78.48

60.81 52.52

77.24 33.13

5.63 43.16

85.47 71.79

38.43 91.62

39.96 89.00

32.54 13.47

55.54 11.99

29.54 89.35

36.61 65.31

34.90 4.03

63.02 50.47

66.44 89.45

99.21 38.57

94.44 29.21

35.03 23.40];

a=a';

X=repmat(x,1,30);

y=sum(sum((a-X).^2).^0.5);
将以上内容写入m文件。
在命令窗口输入：
fminsearch('func',[16.93;43.40])
后面两项数字随意写，不要太离谱就行，我选的是30组中的一组。
最后输出结果（x，y） =（ 47.9325，51.1775）。
这是近似解，从计算数学的角度来讲，它就是理论解

Answer 4

建议用优化方法解决。这里有一个非常类似例子，可以参考。

“一个点到他们所有点路径最短”有些模糊。例子中是让最远点（因为中心点不可能离所有点一样近，肯定有近有远）的路径最短，而且用的距离是city-block距离。

如果您要求其它的优化目标的话请再提出。

追问

你这等于没答。

追答

我不回答是因为你的问题没有明确。而你不回答我就不知道为什么了。

本回答被网友采纳