精华内容
下载资源
问答
  • 基于蚁群算法寻求最短路径matlab仿真
  • 最短路径matlab

    2018-05-25 09:29:19
    首先在m脚本文件canshuo.m中输入节点个数和路径权重 在命令窗口中输入canshu 用s=12,e=10的格式输入要求的起止点,再输入main即可得到两点之间的路径和长度。
  • 【路径规划】基于遗传算法求最短路径matlab源码.md
  • 【路径规划】基于蚁群算法求解最短路径matlab
  • 最短路径matlab代码实现,适合于数学建模的同学拿来参考与学习
  • 【路径规划】蚁群算法求解两点最短路径matlab源码.md
  • 【路径规划】基于A星算法之求解最短路径matlab GUI.md
  • 【路径规划】基于 D星算法求解栅格地图最短路径matlab源码含 GUI.md
  • 求K条最短路径的必要性最短路径问题分为:单源最短路径所有顶点对间的最短路径共同的缺陷:这里的最短路径指两点间最短的那一条路径,不包括次短、再次短等路径。这样的最短路径问题比较狭义。在实际情况中,例如:...

    一、问题介绍

    1.求K条最短路径的必要性

    最短路径问题分为:

    单源最短路径

    所有顶点对间的最短路径

    共同的缺陷:

    这里的最短路径指两点间最短的那一条路径,不包括次短、再次短等路径。这样的最短路径问题比较狭义。

    在实际情况中,例如:用户在使用咨询系统或决策支持系统时,希望得到最优的决策参考外,还希望得到次优、再次优等决策参考,这同样反映在最短路径问题上。因此有必要将最短路径问题予以扩展和延伸,称为K条最短路径问题,即不但要求得最短路径,还要求得次短、再次短等路径。

    2.KSP问题定义

    KSP问题是对最短路径问题的推广,它除了要确定最短路径之外,还要确定次短路径、第三短路径,...,知道找到第K短路径。用Pi表示从起点s到终点t的第i短路径,KSP问题是确定路径集合Pk={p1,p2,p3,...,pk},使得满足以下3个条件:

    1)K条路径是按次序产生的,即对于所有的i(i=1,2,...,K-1),pi是在pi+1之前确定;

    2)K条路径是按长度从小到大排列的,即对于所有的i(i=1,2,...,K-1),都有c(pi)

    3)这K条路径是最短的,即对于所有的p∈Pst-PK,都有c(pk)

    ea0e6894259b

    3.相关概念

    ea0e6894259b

    用于说明偏离概念的图

    设起点为 1 ,终点为 5 。p1、p2、p3 分别表示起点到终点间最短路径、第二短路径、第三短路径。

    1)偏离点

    p3相对于p1的偏离节点为节点 2

    2)偏离边

    p3相对于p1的偏离边为(2,4)

    3)偏离路径

    p3相对于p1的(2,4,5)

    4.KSP算法分类

    1) 一般KSP问题

    对路径没有任何限制

    2) 限定无环KSP问题

    要求所有路径都是简单路径,不能有环

    当路径中所有节点都不同时,称为无环路径

    两类KSP问题具有不同的特征,分别提出了不同的求解算法,分别称之为

    一般的KSP算法

    限定无环KSP算法

    ea0e6894259b

    K最短路径算法分类

    二、思路

    下面列出用Yen's算法求KSP的代码。该算法是Yen在1971年提出的以其名字命名的Yen算法。算法采用了递推法中的偏离路径算法思想,适用于非负权边的有向无环图。

    1.流程图

    ea0e6894259b

    Q:将什么样的点做为偏离点

    在pk的基础上求pk+1时,将pk的路径上除终点d之外的节点分别作为偏离点

    Q:求Vi到终点d的最短路径

    设起点为s,终点为t,偏离点为Vi。求偏离点到终点的最短路径时要注意两个问题

    防止从起点到终点的整体路径有环

    从Vi到t的最短路径不能包含s到Vi的路径上的任何节点

    避免与已经在结果列表中的路径重复

    从Vi发出的边不能与结果列表中的路径p1,p2,...pk,上从Vi发出边的相同

    这个体现在代码上就是:在用Dijkstra算法算最短路径时对数组的初始化要进行特别处理

    // 不能走的边

    if (unavailableEdges != null && unavailableEdges.size() != 0) {

    for (MyPath p: unavailableEdges) {

    int index = p.path.indexOf(startIndex);

    if (index >= 0 && (index + 1) >= 0) {

    dist[index + 1] = Double.MAX_VALUE;

    path[index + 1] = -1;

    }

    }

    }

    // 不能走的点

    if (unavailableNodeIndexs != null && unavailableNodeIndexs.size() != 0) {

    for (Integer point: unavailableNodeIndexs) {

    set[point] = 1;

    }

    }

    Q:每次找到新的最短路径时,需将该路径从候选链列表中移除,并加入到结果列表中

    Q:候选列表中的路径不能重复

    所以选择用Set来存储候选路径,去重

    Q:如何从候选列表中选出合适的路径

    如果只有一条路径权值和最小的路:将该路径返回;

    如果路径权值和最小的路有多条:从其中选出节点数最少的路径。

    2.手工模拟求K最短路径流程

    求C到H的10条最短路径

    ea0e6894259b

    节点加载内存后存储在Node[] nodes数组中,各个节点在数组中的存储位置如下,下面用各个点的数组下标进行说明。表格中括号中备注为路径权重。

    ea0e6894259b

    1)通过最短路径算法Dijkstra得到C到H的最短路径

    p1=C-E-F-H,即0-2-3-5

    2)在p1的基础上求p2

    ea0e6894259b

    遍历完各个偏离点后的情况:

    ea0e6894259b

    从集合B中选出路径0->2->4->5(7)移除,并加入到集合A中,作为p2

    ea0e6894259b

    3)在p2的基础上求p3

    ea0e6894259b

    遍历完各个偏离点后的情况:

    ea0e6894259b

    从集合B中选出路径0->1->3->5(8)移除,并加入到集合A中,作为p3

    ea0e6894259b

    4)在p3的基础上求p4

    ea0e6894259b

    遍历完各个偏离点后的情况:

    ea0e6894259b

    从集合B中选出路径0->1->3->5(8)移除,并加入到集合A中,作为p4

    ea0e6894259b

    5)在p4的基础上求p5

    ea0e6894259b

    遍历完各个偏离点后的情况:

    ea0e6894259b

    从集合B中选出路径0->2->3->4->5(8)移除,并加入到集合A中,作为p5`

    ea0e6894259b

    6)在p5的基础上求p6

    ea0e6894259b

    遍历完各个偏离点后,没有新的候选路径加入集合B中

    ea0e6894259b

    从集合B中选出路径0->1->3->4->5(11)移除,并加入到集合A中,作为p6

    ea0e6894259b

    7)在p6的基础上求p7

    遍历各个偏离点时求最短路径均不存在,故遍历完各个偏离点后,没有新的候选路径加入集合B中,从集合B中选出路径0->2->1->3->4->5(11)移除,并加入到集合A中,作为p7

    ea0e6894259b

    8)在p7的基础上求p8

    遍历各个偏离点时求最短路径均不存在,故遍历完各个偏离点后,没有新的候选路径加入集合B中,候选集合为空,不能再继续向下寻找。故从C到H共有7条路径。

    三、代码

    1.输入上述图

    6 9

    11 C

    12 D

    13 E

    14 F

    15 G

    16 H

    11 12 3

    11 13 2

    12 14 4

    13 12 1

    13 14 2

    13 15 3

    14 15 2

    14 16 1

    15 16 2

    11 16 10

    2.代码

    package road;

    import util.NavigationUtil;

    import java.util.*;

    /**

    *

    
     

    * author : 杨丽金

    * time : 2018/11/14

    * desc : 有关于图的最短路径

    * version: 1.0

    *

    */

    public class ShortestPath {

    public static class MyPath {

    // 路径上的各个节点对应的数组下标(从起点到终点)

    public List < Integer > path;

    // 路径总权值

    public double weight;

    // 路径上节点个数:通过path.size()得到

    public MyPath() {}

    public MyPath(List < Integer > path, double weight) {

    this.path = path;

    this.weight = weight;

    }

    @Override

    public String toString() {

    return "MyPath{" +

    "path=" + path +

    ", weight=" + weight +

    '}';

    }

    @Override

    public boolean equals(Object o) {

    if (this == o) return true;

    if (o == null || getClass() != o.getClass()) return false;

    MyPath path1 = (MyPath) o;

    return path != null ? path.equals(path1.path) : path1.path == null;

    }

    @Override

    public int hashCode() {

    int result;

    long temp;

    result = path != null ? path.hashCode() : 0;

    temp = Double.doubleToLongBits(weight);

    result = 31 * result + (int)(temp ^ (temp >>> 32));

    return result;

    }

    }

    /**

    * 用Yen's KSP算法从图中找出从startIndex到endIndex的K条最短路径

    *

    * @param g

    * @param startIndex:起始节点的数组下标

    * @param endIndex:终止节点的数组下标

    * @param K:要求的最短路径数目

    * @return

    */

    public List < MyPath > KSP_Yen(MyGraph g, int startIndex, int endIndex, int K) {

    // 结果列表

    List < MyPath > result = new ArrayList < > ();

    // 候选路径列表

    Set < MyPath > candidatePaths = new HashSet < > ();

    // 候选路径列表中权值最小的路径,及其对应的节点个数

    // 第一条最短路径

    MyPath p1 = getSingleShortestPath_dijkstra(g, startIndex, endIndex, null, null);

    result.add(p1);

    int k = 1;

    List < Integer > pk = p1.path;

    while (k < K) {

    /*

    求第k+1条最短路径

    */

    // 遍历每一个偏离点

    for (int i = 0; i <= pk.size() - 2; i++) {

    // 1,pk路径中起点到偏离点Vi的路径权值

    double w1 = 0;

    for (int j = 0; j <= i - 1; j++) {

    w1 += NavigationUtil.getEdgeWight(g, pk.get(j), pk.get(j + 1));

    }

    // 2,偏离点到终点的最短路径

    MyPath viToDestinationSP = getSingleShortestPath_dijkstra(g,

    pk.get(i), endIndex, pk.subList(0, i), result);

    if (viToDestinationSP != null) {

    // 说明从这个偏离点可以到达终点

    MyPath temp = new MyPath();

    List < Integer > tempPath = new ArrayList < > (pk.subList(0, i));

    tempPath.addAll(viToDestinationSP.path);

    temp.path = tempPath;

    temp.weight = w1 + viToDestinationSP.weight;

    // 加入候选列表

    if (!candidatePaths.contains(temp)) {

    candidatePaths.add(temp);

    }

    }

    }

    if (candidatePaths == null || candidatePaths.size() == 0) {

    // 没有候选路径,则无需再继续向下求解

    break;

    } else {

    // 从候选路径中选出最合适的一条,移除并加入到结果列表

    MyPath fitPath = getFitPathFromCandidate(candidatePaths);

    candidatePaths.remove(fitPath);

    result.add(fitPath);

    k++;

    pk = fitPath.path;

    }

    }

    return result;

    }

    /**

    * 从候选列表中得到一条路径作为pk+1

    * 要求:1)该路径的权值和最小;2)路径经过节点数最少

    * @param candidatePaths:候选列表

    * @return

    */

    private MyPath getFitPathFromCandidate(Set < MyPath > candidatePaths) {

    MyPath result = new MyPath(null, Double.MAX_VALUE);

    for (MyPath p: candidatePaths) {

    // 对于每一条路径

    if (p.weight < result.weight) {

    result = p;

    }

    if (p.weight == result.weight && p.path.size() < result.path.size()) {

    result = p;

    }

    }

    return result;

    }

    /**

    * 用Dijkstra算法得到从startIndex到endIndex的一条最短路径

    *

    * @param g

    * @param startIndex 起始节点的数组下标

    * @param endIndex 终止节点的数组下标

    * @param unavailableNodeIndexs:求最短路径时不可用的节点(数组下标)

    * @param unavailableEdges:求最短路径时不可用的边

    * @return

    */

    public MyPath getSingleShortestPath_dijkstra(MyGraph g, int startIndex, int endIndex,

    List < Integer > unavailableNodeIndexs, List < MyPath > unavailableEdges) {

    if (startIndex == -1) {

    // throw new Exception("getSingleShortestPath_dijkstra()起始点编号输入错误");

    }

    if (endIndex == -1) {

    // throw new Exception("getSingleShortestPath_dijkstra()终止点编号输入错误");

    }

    int[] set = new int[g.n]; // 是否已并入集合,该点是否已找到最短路径

    // s到i的最短路径长度

    double[] dist = new double[g.n];

    // s到i的最短路径上i的前一个节点编号

    int[] path = new int[g.n];

    // 初始化数组

    set[startIndex] = 1;

    for (int i = 0; i < g.n; i++) {

    if (i == startIndex) { // 源点

    dist[i] = 0;

    path[i] = -1;

    } else {

    if (NavigationUtil.isConnected(g, startIndex, i)) {

    dist[i] = NavigationUtil.getEdgeWight(g, startIndex, i);

    path[i] = startIndex;

    } else {

    dist[i] = Double.MAX_VALUE;

    path[i] = -1;

    }

    }

    }

    // 不能走的边

    if (unavailableEdges != null && unavailableEdges.size() != 0) {

    for (MyPath p: unavailableEdges) {

    int index = p.path.indexOf(startIndex);

    if (index >= 0 && (index + 1) >= 0) {

    dist[p.path.get(index + 1)] = Double.MAX_VALUE;

    path[p.path.get(index + 1)] = -1;

    }

    }

    }

    // 不能走的点

    if (unavailableNodeIndexs != null && unavailableNodeIndexs.size() != 0) {

    for (Integer point: unavailableNodeIndexs) {

    set[point] = 1;

    }

    }

    // 需进行n-2轮循环

    for (int i = 0; i < g.n - 2; i++) {

    int k = -1;

    double min = Double.MAX_VALUE;

    // 找出dist[]中最小的(太贪心了)

    for (int j = 0; j < g.n; j++) {

    if (set[j] == 1) {

    continue;

    }

    if (dist[j] < min) {

    min = dist[j];

    k = j;

    }

    }

    if (k == -1) {

    // 说明从源点出发与其余节点不连通,无法再向下进行扩展

    break;

    }

    set[k] = 1; // 把节点k并入

    // 修改dist[]、path[]

    for (int j = 0; j < g.n; j++) {

    if (set[j] == 1) {

    continue;

    }

    if (NavigationUtil.isConnected(g, k, j)) {

    double temp = dist[k] + NavigationUtil.getEdgeWight(g, k, j);

    if (temp < dist[j]) {

    dist[j] = temp;

    path[j] = k;

    }

    }

    }

    }

    System.out.println("运行Dijkstra算法后的数组情况为:");

    System.out.print("set[]:");

    for (int i = 0; i < g.n; i++) {

    System.out.print(set[i] + "\t");

    }

    System.out.println();

    System.out.print("dist[]:");

    for (int i = 0; i < g.n; i++) {

    System.out.print(dist[i] + "\t");

    }

    System.out.println();

    System.out.print("path[]:");

    for (int i = 0; i < g.n; i++) {

    System.out.print(path[i] + "\t");

    }

    System.out.println();

    // 输出

    if (dist[endIndex] == Double.MAX_VALUE) {

    // 说明没有最短路径,两点不连通

    System.out.println("两点之间不连通");

    return null;

    } else {

    System.out.println("节点" + g.nodes[startIndex].nodeId + "到节点" +

    g.nodes[endIndex].nodeId + "的最短路径长度为:" + dist[endIndex] + ",具体路径是:");

    MyPath result = new MyPath();

    result.path = getMinimumPath(g, startIndex, endIndex, path);

    result.weight = dist[endIndex];

    return result;

    }

    }

    /**

    * 输出从节点S到节点T的最短路径

    *

    * @param sIndex:起始节点在数组中下标

    * @param tIndex:终止节点在数组中下标

    */

    private List < Integer > getMinimumPath(MyGraph g, int sIndex, int tIndex, int[] path) {

    List < Integer > result = new ArrayList < > ();

    Stack < Integer > stack = new Stack < > ();

    stack.push(tIndex);

    int i = path[tIndex];

    while (i != -1) {

    stack.push(i);

    i = path[i];

    }

    while (!stack.isEmpty()) {

    System.out.print(g.nodes[stack.peek()].nodeId + ":" + g.nodes[stack.peek()].nodeName + "-->");

    result.add(NavigationUtil.getIndex(g, g.nodes[stack.pop()].nodeId));

    }

    System.out.println();

    return result;

    }

    }

    3.输出

    sps: [MyPath {

    path = [0, 2, 3, 5], weight = 5.0

    }, MyPath {

    path = [0, 2, 4, 5], weight = 7.0

    }, MyPath {

    path = [0, 1, 3, 5], weight = 8.0

    }, MyPath {

    path = [0, 2, 1, 3, 5], weight = 8.0

    }, MyPath {

    path = [0, 2, 3, 4, 5], weight = 8.0

    }, MyPath {

    path = [0, 1, 3, 4, 5], weight = 11.0

    }, MyPath {

    path = [0, 2, 1, 3, 4, 5], weight = 11.0

    }]

    参考文献

    [1]K条最短路径问题综述

    [2]韩海玲. 基于城市路网的最短路径算法研究与应用[D]. 中北大学, 2017.

    [3]徐涛, 丁晓璐, 李建伏. K最短路径算法综述[J]. 计算机工程与设计, 2013, 34(11):3900-3906.

    [4]K条最短路径算法(KSP, k-shortest pathes):Yen's Algorithm

    展开全文
  • 蚁群算法最短路径matlab程序,还是很不错的
  • 该程序是matlab编写的,已知起点和终端,找到在指定的步数下,能到达的最短路径
  • 复杂网络最短路径代码,可以学习,可以直接用。能很好的计算出网络的最短路径
  • 给定所有点的坐标,通过遗传算法给出最短路径选择及最短路程
  • 关于遗传算法的一个简单例子,在MATLAB中实现搜寻最短路径(最优化)的目的,仅供大家参考学习,谢谢
  • 蚁群算法最短路径MATLAB代码实现,比较完整,需要的可以下载试一下
  • 算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离,该算法可以用来找到两个城市之间的最短路径
  • DQN最短路径MATLAB.zip

    2020-05-26 21:25:03
    不用强化学习工具箱的DQN算法案例与matlab代码,方便大家学习使用。可以在此基础上直接更改编写自己的项目
  • 两点间所有最短路径寻找 This is an implementation of the dijkstra algorithm, wich finds the minimal cost path between two nodes.
  • 障碍物鼠标路径matlab代码地面机器人 这个 repo 包含 Ground Robots 的代码。 介绍 该项目旨在使地面机器人能够自主覆盖指定区域。 地面机器人有望在不遗漏任何部件的情况下生成覆盖指定室外区域的最佳路径,同时...
  • % (1) file1.m function [mydistance,mypath]=mydijkstra(a,sb,db); % 输入:a—邻接矩阵,a(i,j)...% 输出:mydistance—最短路的距离, mypath—最短路的路径 n=size(a,1); visited(1:n) = 0; distance(1...

    %dijkstra最短路径
    (1)
    file1.m

    function [mydistance,mypath]=mydijkstra(a,sb,db);
    % 输入:a—邻接矩阵,a(i,j)是指i到j之间的距离,可以是有向的
    % sb—起点的标号, db—终点的标号
    % 输出:mydistance—最短路的距离, mypath—最短路的路径
    n=size(a,1); visited(1:n) = 0;
    distance(1:n) = inf; distance(sb) = 0; %起点到各顶点距离的初始化
    visited(sb)=1; u=sb;  %u为最新的P标号顶点
    parent(1:n) = 0; %前驱顶点的初始化
    for i = 1: n-1
         id=find(visited==0); 	%查找未标号的顶点
         for v = id           
             if  a(u, v) + distance(u) < distance(v)
                 distance(v) = distance(u) + a(u, v);  %修改标号值 
                 parent(v) = u;                                    
             end            
         end
         temp=distance;
         temp(visited ==1)=inf;  %已标号点的距离换成无穷
         [t, u] = min(temp);  %找标号值最小的顶点 
         visited(u) = 1;       %标记已经标号的顶点
     end
    mypath = [];
    if parent(db) ~= 0   %如果存在路!
        t = db; mypath = [db];
        while t ~= sb
            p = parent(t);
            mypath = [p mypath];
            t = p;      
        end
    end
    mydistance = distance(db);
    

    (2)file2.m

    clc,clear,
    a = [0 121.66 inf 117.41 inf inf inf inf;
    inf 0 75.50 inf 65.4 inf inf inf;
    inf inf 0 inf inf 113.10 inf inf;
    inf inf inf 0 156.9 inf 93.59 inf;
    inf inf inf inf 0 73.2 inf inf;
    inf inf inf inf inf 0 inf 50.6;
    inf inf inf inf inf inf 0 198.74;
    inf inf inf inf inf inf inf 0];
    [mydistance,mypath] = mydijkstra(a, 1, 8)
    
    展开全文
  • 用dijstra算法,寻求由起始点s到其他各点的最短路径树及其最短距离
  • Bus=[1,0,0 ; 2,100, 60; 3,90,40; 4,120,80; 5,60,30; 6,60,20; 7, 200, 100 ; 8,200, 100 ; 9, 60, 20; 10,60, 20; 11,45,30; 12,60, 35; 13,60, 35; 14,120,80; 15,60, 10; 16,60, 20; 17,60, 20;... 19
  • A算法是一种典型的启发式搜索算法,建立在Dijkstra算法的基础之上,广泛应用于游戏地图、现实世界中,用来寻找两点之间的最短路径。A算法最主要的是维护了一个启发式估价函数,如式(1)所示。 f(n)=g(n)+h(n)(1) 其中...

    一、简介

     

    A算法
    A算法是一种典型的启发式搜索算法,建立在Dijkstra算法的基础之上,广泛应用于游戏地图、现实世界中,用来寻找两点之间的最短路径。A算法最主要的是维护了一个启发式估价函数,如式(1)所示。
    f(n)=g(n)+h(n)(1)
    其中,f(n)是算法在搜索到每个节点时,其对应的启发函数。它由两部分组成,第一部分g(n)是起始节点到当前节点实际的通行代价,第二部分h(n)是当前节点到终点的通行代价的估计值。算法每次在扩展时,都选取f(n)值最小的那个节点作为最优路径上的下一个节点。
    在实际应用中,若以最短路程为优化目标,h(n)常取作当前点到终点的欧几里得距离(Euclidean Distance)或曼哈顿距离(Manhattan Distance)等。若令h(n)=0,表示没有利用任何当前节点与终点的信息,A
    算法就退化为非启发的Dijkstra算法,算法搜索空间随之变大,搜索时间变长。
    A*算法步骤如下,算法维护两个集合:P表与Q表。P表存放那些已经搜索到、但还没加入最优路径树上的节点;Q表维护那些已加入最优路径树上的节点。
    (1)P表、Q表置空,将起点S加入P表,其g值置0,父节点为空,路网中其他节点g值置为无穷大。
    (2)若P表为空,则算法失败。否则选取P表中f值最小的那个节点,记为BT,将其加入Q表中。判断BT是否为终点T,若是,转到步骤(3);否则根据路网拓扑属性和交通规则找到BT的每个邻接节点NT,进行下列步骤:

    ①计算NT的启发值
    f(NT)=g(NT)+h(NT)(2)
    g(NT)=g(BT)+cost(BT, NT)(3)
    其中,cost(BT, NT)是BT到NT的通行代价。
    ②如果NT在P表中,且通过式(3)计算的g值比NT原先的g值小,则将NT的g值更新为式(3)结果,并将NT的父节点设为BT。
    ③如果NT在Q表中,且通过式(3)计算的g值比NT原先的g值小,则将NT的g值更新为式(3)结果,将NT的父节点设为BT,并将NT移出到P表中。
    ④若NT既不在P表,也不在Q表中,则将NT的父节点设为BT,并将NT移到P表中。
    ⑤转到步骤(2)继续执行。
    (3)从终点T回溯,依次找到父节点,并加入优化路径中,直到起点S,即可得出优化路径。



    二、源代码

    function varargout = A_GUI(varargin)
    % A_GUI MATLAB code for A_GUI.fig
    %      A_GUI, by itself, creates a new A_GUI or raises the existing
    %      singleton*.
    %
    %      H = A_GUI returns the handle to a new A_GUI or the handle to
    %      the existing singleton*.
    %
    %      A_GUI('CALLBACK',hObject,eventData,handles,...) calls the local
    %      function named CALLBACK in A_GUI.M with the given input arguments.
    %
    %      A_GUI('Property','Value',...) creates a new A_GUI or raises the
    %      existing singleton*.  Starting from the left, property value pairs are
    %      applied to the GUI before A_GUI_OpeningFcn gets called.  An
    %      unrecognized property name or invalid value makes property application
    %      stop.  All inputs are passed to A_GUI_OpeningFcn via varargin.
    %
    %      *See GUI Options on GUIDE's Tools menu.  Choose "GUI allows only one
    %      instance to run (singleton)".
    %
    % See also: GUIDE, GUIDATA, GUIHANDLES
     
    % Edit the above text to modify the response to help A_GUI
     
    % Last Modified by GUIDE v2.5 21-Oct-2018 17:10:48
     
    % Begin initialization code - DO NOT EDIT
    gui_Singleton = 1;
    gui_State = struct('gui_Name',       mfilename, ...
                       'gui_Singleton',  gui_Singleton, ...
                       'gui_OpeningFcn', @A_GUI_OpeningFcn, ...
                       'gui_OutputFcn',  @A_GUI_OutputFcn, ...
                       'gui_LayoutFcn',  [] , ...
                       'gui_Callback',   []);
    if nargin && ischar(varargin{1})
        gui_State.gui_Callback = str2func(varargin{1});
    end
     
    if nargout
        [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
    else
        gui_mainfcn(gui_State, varargin{:});
    end
    % End initialization code - DO NOT EDIT
     
     
    % --- Executes just before A_GUI is made visible.
    function A_GUI_OpeningFcn(hObject, eventdata, handles, varargin)
    % This function has no output args, see OutputFcn.
    % hObject    handle to figure
    % eventdata  reserved - to be defined in a future version of MATLAB
    % handles    structure with handles and user data (see GUIDATA)
    % varargin   command line arguments to A_GUI (see VARARGIN)
     
    % Choose default command line output for A_GUI
    handles.output = hObject;
     
    % Update handles structure
    guidata(hObject, handles);
     
    % UIWAIT makes A_GUI wait for user response (see UIRESUME)
    % uiwait(handles.figure1);
     
     
    % --- Outputs from this function are returned to the command line.
    function varargout = A_GUI_OutputFcn(hObject, eventdata, handles) 
    % varargout  cell array for returning output args (see VARARGOUT);
    % hObject    handle to figure
    % eventdata  reserved - to be defined in a future version of MATLAB
    % handles    structure with handles and user data (see GUIDATA)
     
    % Get default command line output from handles structure
    varargout{1} = handles.output;
     
     
    % --- Executes on button press in pushbutton1.
    function pushbutton1_Callback(hObject, eventdata, handles)
    % hObject    handle to pushbutton1 (see GCBO)
    % eventdata  reserved - to be defined in a future version of MATLAB
    % handles    structure with handles and user data (see GUIDATA)
     
    % set up color map for display 生成彩色地图 
    global cmap;
    global map;
    global n_r;
    global n_c;
    global state;
     
    cmap = [1 1 1; ...% 1 -白色-无障碍
            0 0 0; ...% 2 -黑色-有障碍
            0 0.8 0; ...% 3 -绿色-已搜索
            0 0.4 0; ...% 4 -粉色-正在搜索
            0 1 1; ...% 5 -浅蓝色-起始点
            1 1 0; ...% 6 -黄色-目标点
            0 0 1];   % 7 -蓝色-最终路径
    colormap(cmap); 
    %生成随机地图
    map = zeros(n_r,n_c);
    randmap = rand(n_r,n_c);
    for i = 2:(sub2ind(size(randmap),n_r,n_c)-1)
        if (randmap(i) >= 0.75)
            map(i) = 2;
        end
    end
     
    map(1, 1) = 5; % start_coords 起点坐标
    map(n_r, n_c) = 6; % dest_coords 终点坐标
    image(1.5,1.5,map); 
    grid on; 
    axis image; 
    set(handles.text5,'string','随机地图生成完毕');
     
     
    % --- Executes on button press in pushbutton2.
    function pushbutton2_Callback(hObject, eventdata, handles)
    % hObject    handle to pushbutton2 (see GCBO)
    % eventdata  reserved - to be defined in a future version of MATLAB
    % handles    structure with handles and user data (see GUIDATA)
     
    %搜索最佳路径
    global n_r;
    global n_c;
    global cmap;
    global map;
    global state;
     
    nrows = n_r; 
    ncols = n_c; 
    start_node = sub2ind(size(map), 1, 1); 
    %sub2ind()函数将矩阵中的某个元素的线性序号计算出来
    %线性索引号例子:2*2矩阵[1 3;中,1是第一个,5是第二个
    %                       5 7]  ,3是第三个,7是第四个
    %(matlab是列优先,不是我们通常习惯的行优先)
    dest_node = sub2ind(size(map), n_r, n_c); 
    % Initialize distance array 初始化距离数组
    distanceFromStart = Inf(nrows,ncols); 
    distanceFromStart(start_node) = 0 ;
     
    [X, Y] = meshgrid (1:ncols, 1:nrows);
    H = abs(Y - n_r) + abs(X - n_c);
    f = Inf(nrows,ncols); 
    f(start_node) = H(start_node); 
     
    % For each grid cell this array holds the index of its parent 对于每个网格单元,该数组都保存其父单元的索引
    parent = zeros(nrows,ncols); 
     % Main Loop 
    while true 
      % Draw current map 
      map(start_node) = 5; 
      map(dest_node) = 6; 
      image(1.5, 1.5, map); 
      grid on; %网格
      axis image; %显示坐标
      drawnow; %刷新屏幕
      % Find the node with the minimum distance 找到距离最短的节点
    %   [min_dist, current] = min(distanceFromStart(:));
    [~, current] = min(f(:)); [min_dist, ~] = min(distanceFromStart(:));
      if ((current == dest_node) || isinf(min_dist)) %TF = isinf(A)  返回一个和A尺寸一样的数组, 如果A中某个元素是inf  (无穷), 则对应TF中元素是1, 否则TF中对应元素是0。 
           break; 
      end; 
      %搜索中心的索引坐标:current,
      %搜索中心与起始点的路程:min_dist
      % 这两个值后面会用。
     
      map(current) = 3; 
    %   distanceFromStart(current) = Inf; 
    f(current) = Inf; 
      [i, j] = ind2sub(size(distanceFromStart), current); %索引号变为坐标
      neighbor = [i-1,j; 
                  i+1,j; 
                  i,j+1; 
                  i,j-1]; 
        outRangetest = (neighbor(:,1)<1) + (neighbor(:,1)>nrows)+(neighbor(:,2)<1) + (neighbor(:,2)>ncols); 
        locate = find(outRangetest>0);  %返回outRangetest中大于0的元素的相对应的线性索引值。
        neighbor(locate,:)=[]; 
        neighborIndex = sub2ind(size(map),neighbor(:,1),neighbor(:,2));
    for i=1:length(neighborIndex) 
     if (map(neighborIndex(i))~=2) && (map(neighborIndex(i))~=3 && map(neighborIndex(i))~= 5) 
         map(neighborIndex(i)) = 4; 
       if (distanceFromStart(neighborIndex(i))>= min_dist + 1 )     
           distanceFromStart(neighborIndex(i)) = min_dist+1;
             parent(neighborIndex(i)) = current;   
             f(neighborIndex(i)) = H(neighborIndex(i)); 
            % pause(0.02); 
       end 
      end 
     end 
     end
    % %%
     if (isinf(distanceFromStart(dest_node))) 
         %route = [];
         disp('路径搜索失败');
         set(handles.text5,'string','路径搜索失败');
     else 
         %提取路线坐标
         set(handles.text5,'string','路径搜索成功');
     
         route = [dest_node];
           while (parent(route(1)) ~= 0) 
                   route(1);
                   parent(route(1))
                   route = [parent(route(1)), route] ;
            end 

    三、运行结果

    在这里插入图片描述



     

    展开全文
  • 障碍物鼠标路径matlab代码未来餐厅 2.0 抽象的 这个想法是让机器人能够为顾客提供菜肴。 订单将通过位于餐桌上的移动设备发出,该设备将发送到接待处进行计费,并发送到厨师和机器人的厨房菜单。 准备好食物后,它将...
  • 1.关于旅行商(TSP)问题及衍化...旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径...

    1.关于旅行商(TSP)问题及衍化

      旅行商问题(Traveling Saleman Problem,TSP)是车辆路径调度问题(VRP)的特例,由于数学家已证明TSP问题是NP难题,因此,VRP也属于NP难题。旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。——旅行商问题百科

      很明显,当节点数很少时,大多数人都会想到,问题很简单,直接穷举就OK了,但实际问题中,节点数往往很大,变得不可能。例如:对于一个仅有16个城市的旅行商问题,如果用穷举法来求问题的最优解,需比较的可行解有:15!/2=653,837,184,000个。在1993年,使用当时的工作站用穷举法求解此问题需时92小时。即使现在计算机速度快,但是面对复杂的问题,仍然不够。这就是所谓的“组合爆炸”,指数级的增长,所以科学家逐步寻找近似算法或者启发式算法,目的是在合理的时间范围内找到可接受的最优解。

      TSP问题解决算法的发展可以分为3个部分:

    1).经典精确算法:穷举法、线性规划算法、动态规划算法、分支定界算法等运筹学中的传统算法,这些算法复杂度一般都很大,只适用于求解小规模问题。

    2).近似算法:当问题规模较大时,其所需的时间成级数增长,这是我们无法接受的,算法求解问题的规模受到了很大的限制,一个很自然的想法就是牺牲精确解法中的最优性,去寻找一个好的时间复杂度我们可以容忍的,同时解的质量我们可以接受的算法.基于这一思想所设计出的算法统称为近似算法。如插入算法,最邻近算法等。

    3).智能算法:随着科学技术和生产的不断发展,许多实际问题不可能在合理的时间范围内找到全局最优解,这就促使了近代最优化问题求解方法的产生。随着各种不同搜索机制的启发式算法相继出现,如禁忌搜索、遗传算法、模拟退火算法、人工神经网络、进化策略、进化编程、粒子群优化算法、蚁群优化算法和免疫计算等,掀起了研究启发式算法的高潮。

      具体每一种算法不再详细描述,大家可以针对性的寻找相应资料进行了解。

      TSP问题在实际的生产生活中,更加实际环境不同,有很多衍生的经典问题。车辆路径调度(VRP)扩展问题是经典VRP加入各种约束条件后而形成的。例如需求约束形成的需求随机的车辆路径问题(SVRP);加入时间约束得到的带时间窗的车辆路径题(VRPTW);加入距离约束的距离约束车辆路径问题(DVRP);根据其它条件的不同,还有多配送中心车辆路径问题(MDVRP)、可切分的车辆路径问题(SDVRP);先配送再收集车辆路径问题(VRPB)、配送收集车辆路径问题(VRPPD);信息不完全的模糊车辆路径问题(FVRP)[3]。

    回到目录

    2.群蚁算法基本原理

    2.1 算法综述

      对于VRP问题,求解算法大致可分为精确算法和人工智能算法两大类。精确性算法基于严格的数学手段,在可以求解的情况下,解的质量较好。但是由于算法严格,运算量大,特别是大规模的问题几乎无法求解。所以其应用只能是小规模的确定性问题,面对中小规模问题,人工智能算法在精度上不占优势。但规模变大时,人工智能方法基本能在可接受时间里,找到可接受的满意解,这是精确算法难以做到的。由于的实际问题,各种约束错综复杂,人工智能算法显示出了巨大的优越性,也正因为如此,实际应用中,人工智能算法要更广泛。求解车辆路径调度问题的精确算法有动态规划法、分枝定界法等。并开始寻求所得结果可接受的启发式算法,以处理大规模实际问题,一些其他学科的新一代优化算法相继出现,如禁忌搜索算法,遗传算法,人工神经网络算法,以及现在研究较多的蚁群算法等。

    2.2 群蚁算法的原理

      蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出。生物学研究表明:一群相互协作的蚂蚁能够找到食物和巢穴之间的最短路径,而单只蚂蚁则不能。生物学家经过大量细致观察研究发现,蚂蚁个体之间的行为是相互作用相互影响的。蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为信息素的物质,而此物质恰恰是蚂蚁个体之间信息传递交流的载体。蚂蚁在运动时能够感知这种物质,并且习惯于追踪此物质爬行,当然爬行过程中还会释放信息素。一条路上的信息素踪迹越浓,其它蚂蚁将以越高的概率跟随爬行此路径,从而该路径上的信息素踪迹会被加强,因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象。某一路径上走过的蚂蚁越多,则后来者选择该路径的可能性就越大。蚂蚁个体之间就是通过这种间接的通信机制实现协同搜索最短路径的目标的。我们举例简单说明蚂蚁觅食行为:

        

        如上图a,b,c的示意图:

        a图是原始状态,蚂蚁起始点为A,要到达E,中途有障碍物,要绕过才能到达。BC和BH是绕过障碍物的2条路径(假设只有2条)。各个路径的距离d已经标定。

        b图是t=0时刻蚂蚁状态,各个边上有相等的信息素浓度,假设为15;

        c图是t=1时刻蚂蚁经过后的状态,各个边的信息素浓度,有变化;因为大量蚂蚁的选择概率会不一样,而选择概率是和路径长度相关的。所以越短路径的浓度会越来越大,经过此短路径达到目的地的蚂蚁也会比其他路径多。这样大量的蚂蚁实践之后就找到了最短路径。所以这个过程本质可以概括为以下几点:

        1.路径概率选择机制信息素踪迹越浓的路径,被选中的概率越大

        2.信息素更新机制路径越短,路径上的信息素踪迹增长得越快

        3.协同工作机制蚂蚁个体通过信息素进行信息交流。

        从蚂蚁觅食的原理可见,单个个体的行为非常简单蚂蚁只知道跟踪信息素爬行并释放信息素,但组合后的群体智能又非常高蚂蚁群能在复杂的地理分布的清况下,轻松找到蚁穴与食物源之间的最短路径。这种特点恰恰与元启发算法的特点相一致,蚁群优化算法正是受到这种生态学现象的启发后加以模仿并改进而来,觅食的蚂蚁由人工蚁替代,蚂蚁释放的信息素变成了人工信息素,蚂蚁爬行和信息素的蒸发不再是连续不断的,而是在离散的时空中进行。

      上述例子如果不好理解,我在这里贴几张PPT,个人感觉非常不错,也是我找了很多资料觉得最好理解的【来源是大连理工大学谷俊峰】,点击这里提供下载:蚁群算法基本知识.rar

        从深层意义上来讲,蚁群算法作为优化的方法之一,属于人工群集智能领域。人工群集智能,大都受自然群集智能如昆虫群和动物群等的启发而来。除了具有独特的强有力的合作搜索能力外,还可以利用一系列的计算代理对问题进行分布式处理,从而大大提高搜索效率。

    回到目录

    3.群蚁算法的基本流程

      我们还是采用大连理工大学谷俊峰的PPT来说明问题,重要公式进行截图计算和解释,对PPT难以理解的地方进行单独解释:

    3.1 基本数学模型

      首先看看基本TSP问题的基本数学模型:

      问题其实很简单,目标函数就是各个走过路径的总长度,注意的就是距离矩阵根据实际的问题不一样,长度是不一样的。

    3.2 群蚁算法说明

      在说明群蚁算法流程之前,我们对算法原理和几个注意点进行描述:

    1.TSP问题的人工蚁群算法中,假设m只蚂蚁在图的相邻节点间移动,从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定:1. 信息素值也称信息素痕迹。2.可见度,即先验值。\ 2.信息素的更新方式有2种,一是挥发,也就是所有路径上的信息素以一定的比率进行减少,模拟自然蚁群的信息素随时间挥发的过程;二是增强,给评价值“好”(有蚂蚁走过)的边增加信息素。\ 3.蚂蚁向下一个目标的运动是通过一个随机原则来实现的,也就是运用当前所在节点存储的信息,计算出下一步可达节点的概率,并按此概率实现一步移动,逐此往复,越来越接近最优解。\ 4.蚂蚁在寻找过程中,或者找到一个解后,会评估该解或解的一部分的优化程度,并把评价信息保存在相关连接的信息素中。 

    3.3 群蚁算法核心步骤

      更加我们前面的原理和上述说明,群蚁算法的2个核心步骤是 路径构建 和 信息素更新。我们将重点对这2个步骤进行说明。

    3.3.1 路径构建

      每个蚂蚁都随机选择一个城市作为其出发城市,并维护一个路径记忆向量,用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中,按照一个随机比例规则选 择下一个要到达的城市。随机概率是按照下列公式来进行计算的:

      上述公式就是计算 当前点 到 每一个可能的下一个节点 的概率。分子是 信息素强度 和 能见度 的幂乘积,而分母则是所有 分子的和值。这个刚开始是很不容易理解的,我们在最后实例计算的时候,可以看得很清楚,再反过来理解公式。注意每次选择好节点后,就要从可用节点中移除选择的节点。

    3.3.2 信息素更新

      信息素更新是群蚁算法的核心。也是整个算法的核心所在。算法在初始期间有一个固定的浓度值,在每一次迭代完成之后,所有出去的蚂蚁回来后,会对所走过的路线进行计算,然后更新相应的边的信息素浓度。很明显,这个数值肯定是和蚂蚁所走的长度有关系的,经过一次次的迭代, 近距离的线路的浓度会很高,从而得到近似最优解。那我们看看信息素更新的过程。

      初始化信息素浓度C(0),如果太小,算法容易早熟,蚂蚁会很快集中到一条局部最优路径上来,因为可以想想,太小C值,使得和每次挥发和增强的值都差不多,那么 随机情况下,一些小概率的事件发生就会增加非最优路径的信息素浓度;如果C太大,信息素对搜索方向的指导性作用减低,影响算法性能。一般情况下,我们可以使用贪婪算法获取一个路径值Cnn,然后根据蚂蚁个数来计算C(0) = m/Cnn ,m为蚂蚁个数

      每一轮过后,问题空间中的所有路径上的信息素都会发生蒸发,然后,所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素,公式如下: 

      信息素更新的作用:\ 1.信息素挥发(evaporation)信息素痕迹的挥发过程是每个连接上的 信息素痕迹的浓度自动逐渐减弱的过程,这个挥发过程主要用于避 免算法过快地向局部最优区域集中,有助于搜索区域的扩展。\ 2.信息素增强(reinforcement)增强过程是蚁群优化算法中可选的部 分,称为离线更新方式(还有在线更新方式)。这种方式可以实现 由单个蚂蚁无法实现的集中行动。基本蚁群算法的离线更新方式是 在蚁群中的m只蚂蚁全部完成n城市的访问后,统一对残留信息进行 更新处理。

    3.3.3 迭代与停止

      迭代停止的条件可以选择合适的迭代次数后停止,输出最优路径,也可以看是否满足指定最优条件,找到满足的解后停止。最重要的是,我刚开始理解这个算法的时候,以为每一只蚂蚁走一条边就是一次迭代,其实是错的。这里算法每一次迭代的意义是:每次迭代的m只蚂蚁都完成了自己的路径过程,回到原点后的整个过程。

    回到目录

    4.群蚁算法计算实例

      使用PPT中的一个案例,非常直观,对几个符号错误进行了修改,主要是计算概率的乘号,结果没有错误:

      过程总体还是比较简单的,注意理解公式,然后把公式和实例结合起来看,最好是拿笔自己手动画一画,容易理解。下面我们来看看如何编程实现TSP问题的群蚁算法代码。

    ``` % Ant main program

    clear all; close all; clc;

    tic; Ant=25;%蚂蚁数量 Ger=120;%迭代次数 firstaddress = [ 100,10 150,10 180,30 200,10 200,200 200,220 180,240 180,270 150,270 100,240 80,240 50,270 200,300 10,300 10,270 10,240 10,200 10,10 50,30 100,10 ];%firstaddress表示测试数据中的节点坐标

    SumOfCity = size(firstaddress,1);%节点个数 lengthaddress =10000.*ones(SumOfCity,SumOfCity);%lengthaddress表示两两节点间的距离,初始设定10000,可以设定无穷大,表示不相连 lengthaddress(1,2)=377;%表示节点1和节点2的距离 lengthaddress(2,4)=190; lengthaddress(2,3)=100; lengthaddress(3,4)=101; lengthaddress(4,5)=240; lengthaddress(5,17)=1932; lengthaddress(5,6)=70; lengthaddress(6,13)=200; lengthaddress(6,7)=63.1;

    lengthaddress(7,10)=377; lengthaddress(7,8)=87.5; lengthaddress(8,9)=100; lengthaddress(10,11)=8; lengthaddress(9,10)=170.8; lengthaddress(9,12)=332.9; lengthaddress(11,12)=168.8; lengthaddress(11,16)=375.2; length_address(12,15)=135.1;

    lengthaddress(13,14)=458; lengthaddress(14,15)=100; lengthaddress(15,16)=86.7; lengthaddress(16,17)=187.5; length_address(17,18)=639.8;

    lengthaddress(18,20)=510.5; lengthaddress(18,19)=200.1; lengthaddress(19,20)=246.8; for n=1:size(firstaddress) for m=1:size(firstaddress) if lengthaddress(n,m)~=10000 lengthaddress(m,n)=lengthaddress(n,m); %对称矩阵 end end end

    power=lengthaddress;%距离 [PM PN]=size(power);%距离矩阵大小,行列个数 % %% 画出节点分布图形 % figure(1); % grid on; % hold on; % scatter(firstaddress(:,1),firstaddress(:,2)); % for i=1:PN % for j=1:PN % if(lengthaddress(i,j)~=10000) % line([firstaddress(i,1),firstaddress(j,1)],[firstaddress(i,2),firstaddress(j,2)],'Color','g');%划线 % text((firstaddress(i,1)+firstaddress(j,1))/2,(firstaddress(i,2)+firstaddress(j,2))/2,num2str(length_address(i,j)));%标注线段距离 % end % end % end

    % 初始化蚂蚁位置 v=init_population(Ant,PN); v(:,1)=1;%起点 v(:,PN)=1;%终点

    fit=shortroadfun(v,power);%求每条路径的距离 T0 = max(fit)-fit;

    % 初始化 vmfit=[]; vx=[]; P0=0.2; % P0----全局转移选择因子 P=0.8; % P ----信息素蒸发系数 %C=[]; % 开始寻优 for iger=1:Ger lamda=1/iger; % 转移步长参数 [TBest(iger),BestIndex]=max(T0); for jg=1:Ant % 求取全局转移概率 r=T0(BestIndex)-T0(jg); Prob(iger,jg)=r/T0(BestIndex); end %对100只蚂蚁进行路径的转变 for jgtr=1:Ant %路径进行改变,该路径存放到temp变量,1表示经过该列所在的节点数 if Prob(iger,jgtr) g tr,:)-2.*(v(jg tr,:).*M)+M; else M=rand(1,PN) g tr,:)-2.*(v(jg tr,:).*M)+M; end temp(:,1)=1;%起点和终点必须有蚂蚁存在 temp(:,end)=1; %判转变后的临时路径距离是否小于原来的路径,是的话就将该蚂蚁的路径进行转换成temp中存放的路径 if shortroad fun(temp,power) road fun(v(jg tr,:),power) v(jg_tr,:)=temp; end end

    %信息素更新
    
       [sol,indb]=min(fit);
    v(1,:)=v(indb,:);%第一只蚂蚁的路径保存最小路径
    media=mean(fit);
    vx=[vx sol];%存放每一代最小的距离
    %     vmfit=[vmfit media];

    end

    % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %%%% 最后结果 % 显示最优解及最优值 % v(indb,:) disp(sprintf('Code of shortroad is: %s',num2str(v(indb,:)))); disp(sprintf('\n')); %空一行 disp(sprintf('Shortroad is: %s',num2str(find(v(indb,:))))); disp(sprintf('Mininum is: %d',sol)); route=find(v(indb,:)); % 画出节点分布图形 figure(2); grid on; hold on; for i=1:PN-1 plot(firstaddress(i,1),firstaddress(i,2),'bo','MarkerSize',10); str=num2str(i); text(firstaddress(i,1)-10,firstaddress(i,2)+10,str,'Color','red','FontSize',15); end m=length(route); for i=1:m plot(firstaddress(route(i),1),firstaddress(route(i),2),'MarkerSize',10,'MarkerEdgeColor','k','MarkerFaceColor',[0.5,0.5,0.5]) ; hold on; end for i=1:PN for j=1:PN if(lengthaddress(i,j)~=10000) line([firstaddress(i,1),firstaddress(j,1)],[firstaddress(i,2),firstaddress(j,2)],'Color','g','LineWidth',5);%划线 text((firstaddress(i,1)+firstaddress(j,1))/2,(firstaddress(i,2)+firstaddress(j,2))/2,num2str(lengthaddress(i,j)));%标注线段距离 end end end %% 最短路径 for p=1:m-1 if(route(p+1)~=20) line([firstaddress(route(p),1),firstaddress(route(p+1),1)],[firstaddress(route(p),2),firstaddress(route(p+1),2)],'Color','r','LineWidth',5);%划线 text((firstaddress(route(p),1)+firstaddress(route(p+1),1))/2,(firstaddress(route(p),2)+firstaddress(route(p+1),2))/2,num2str(lengthaddress(route(p),route(p+1))));%标注线段距离 else line([firstaddress(route(p),1),firstaddress(1,1)],[firstaddress(route(p),2),firstaddress(1,2)],'Color','r','LineWidth',5);%划线 text((firstaddress(route(p),1)+firstaddress(1,1))/2,(firstaddress(route(p),2)+firstaddress(1,2))/2,num2str(lengthaddress(route(p),route(p+1))));%标注线段距离 end end axis([0 250 0 400]) % 图形显示最优及平均函数值变化趋势 % figure(3); % plot(vx); % title('最优,平均函数值变化趋势'); % xlabel('Generations'); % ylabel('f(x)'); % hold on; % plot(vmfit,'r'); % hold off;

    runtime=toc ```

    展开全文
  • % A_GUI MATLAB code for A_GUI.fig % A_GUI, by itself, creates a new A_GUI or raises the existing % singleton*. % % H = A_GUI returns the handle to a new A_GUI or the handle to % the ...
  • 最短路径及其最短路径大小 matlab 图论 [P u]=f_path(W) W是邻接矩阵 P是最短路径 u是最短路径大小
  • Dijkstra算法找最短路径代码,dijkstra算法求最短路径,matlab源码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,025
精华内容 1,610
关键字:

最短路径matlab

matlab 订阅