Java学习者论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

恭喜Java学习者论坛(https://www.javaxxz.com)已经为数万Java学习者服务超过8年了!积累会员资料超过10000G+
成为本站VIP会员,下载本站10000G+会员资源,购买链接:点击进入购买VIP会员
JAVA高级面试进阶视频教程Java架构师系统进阶VIP课程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java架构师3期(课件+源码)

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

深度学习(CNN RNN GAN)算法原理

Java亿级流量电商系统视频教程

互联网架构师视频教程

年薪50万Spark2.0从入门到精通

年薪50万!人工智能学习路线教程

年薪50万!大数据从入门到精通学习路线年薪50万!机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程深度学习数据分析基础到实战最新黑马javaEE2.1就业课程从 0到JVM实战高手教程 MySQL入门到精通教程
查看: 846|回复: 0

[默认分类] 路径规划(最短路径)算法C#实现

[复制链接]
  • TA的每日心情
    开心
    2021-12-13 21:45
  • 签到天数: 15 天

    [LV.4]偶尔看看III

    发表于 2018-5-27 15:26:13 | 显示全部楼层 |阅读模式
        以前空闲的时候用C#实现的路径规划算法,今日贴它出来,看大家有没有更好的实现方案。关于路径规划(最短路径)算法的背景知识,大家可以参考《C++算法--图算法》一书。
        该图算法描述的是这样的场景:图由节点和带有方向的边构成,每条边都有相应的权值,路径规划(最短路径)算法就是要找出从节点A到节点B的累积权值最小的路径。
        首先,我们可以将“有向边”抽象为Edge类:


         
    public
      
    class
      Edge
        {
            
    public
      
    string
      StartNodeID ;
            
    public
      
    string
      EndNodeID   ;
            
    public
      
    double
      Weight      ;
    //
    权值,代价        


         }

        节点则抽象成Node类,一个节点上挂着以此节点作为起点的“出边”表。


          
    public
      
    class
      Node
       

    {
            private string iD ;
            private ArrayList edgeList ;//Edge的集合--出边表

            public Node(string id )
         {
                this.iD = id ;
                this.edgeList = new ArrayList() ;
            }

            property#region property
            public string ID
         {
                get
              {
                    return this.iD ;
                }
            }

            public ArrayList EdgeList
          {
                get
              {
                    return this.edgeList ;
                }
            }
            #endregion
        }

         
        在计算的过程中,我们需要记录到达每一个节点权值最小的路径,这个抽象可以用PassedPath类来表示:


         ///
      
    <summary>

       
    ///
      PassedPath 用于缓存计算过程中的到达某个节点的权值最小的路径
       
    ///
      
    </summary>


         
    public
      
    class
      PassedPath
        {
            
    private
      
    string
          curNodeID ;
            
    private
      
    bool
          beProcessed ;   
    //
    是否已被处理


             
    private
      
    double
          weight ;        
    //
    累积的权值


             
    private
      ArrayList passedIDList ;
    //
    路径



            
    public
      PassedPath(
    string
      ID)
            {
                
    this
    .curNodeID
    =
      ID ;
                
    this
    .weight   
    =
      
    double
    .MaxValue ;
                
    this
    .passedIDList
    =
      
    new
      ArrayList() ;
                
    this
    .beProcessed
    =
      
    false
      ;
            }

            
    #region
      property

            
    public
      
    bool
      BeProcessed
            {
                
    get

                {
                   
    return
      
    this
    .beProcessed ;
                }
                
    set

                {
                   
    this
    .beProcessed
    =
      value ;
                }
            }

            
    public
      
    string
      CurNodeID
            {
                
    get

                {
                   
    return
      
    this
    .curNodeID ;
                }
            }

            
    public
      
    double
      Weight
            {
                
    get

                {
                   
    return
      
    this
    .weight ;
                }
                
    set

                {
                   
    this
    .weight
    =
      value ;
                }
            }

            
    public
      ArrayList PassedIDList
            {
                
    get

                {
                   
    return
      
    this
    .passedIDList ;
                }
            }
            
    #endregion

        }


        另外,还需要一个表PlanCourse来记录规划的中间结果,即它管理了每一个节点的PassedPath。



       
    ///
      
    <summary>

       
    ///
      PlanCourse 缓存从源节点到其它任一节点的最小权值路径=》路径表
       
    ///
      
    </summary>


         
    public
      
    class
      PlanCourse
        {
            
    private
      Hashtable htPassedPath ;   

            
    #region
      ctor

            
    public
      PlanCourse(ArrayList nodeList ,
    string
      originID)
            {
                
    this
    .htPassedPath
    =
      
    new
      Hashtable() ;

                Node originNode
    =
      
    null
      ;
                
    foreach
    (Node node
    in
      nodeList)
                {
                   
    if
    (node.ID
    ==
      originID)
                    {
                        originNode
    =
      node ;
                    }
                   
    else

                    {
                        PassedPath pPath
    =
      
    new
      PassedPath(node.ID) ;
                        
    this
    .htPassedPath.Add(node.ID ,pPath) ;
                    }
                }

                
    if
    (originNode
    ==
      
    null
    )
                {
                   
    throw
      
    new
      Exception(
    "
    The origin node is not exist !
    "
    ) ;
                }        
       
                
    this
    .InitializeWeight(originNode) ;
            }

            
    private
      
    void
      InitializeWeight(Node originNode)
            {
                
    if
    ((originNode.EdgeList
    ==
      
    null
    )
    ||
    (originNode.EdgeList.Count
    ==
      
    0
    ))
                {
                   
    return
      ;
                }

                
    foreach
    (Edge edge
    in
      originNode.EdgeList)
                {
                    PassedPath pPath
    =
      
    this
    [edge.EndNodeID] ;
                   
    if
    (pPath
    ==
      
    null
    )
                    {
                        
    continue
      ;
                    }

                    pPath.PassedIDList.Add(originNode.ID) ;
                    pPath.Weight
    =
      edge.Weight ;
                }
            }
            
    #endregion


            
    public
      PassedPath
    this
    [
    string
      nodeID]
            {
                
    get

                {
                   
    return
      (PassedPath)
    this
    .htPassedPath[nodeID] ;
                }
            }
        }



        在所有的基础构建好后,路径规划算法就很容易实施了,该算法主要步骤如下:
    (1)用一张表(PlanCourse)记录源点到任何其它一节点的最小权值,初始化这张表时,如果源点能直通某节点,则权值设为对应的边的权,否则设为double.MaxValue。
    (2)选取没有被处理并且当前累积权值最小的节点TargetNode,用其边的可达性来更新到达其它节点的路径和权值(如果其它节点   经此节点后权值变小则更新,否则不更新),然后标记TargetNode为已处理。
    (3)重复(2),直至所有的可达节点都被处理一遍。
    (4)从PlanCourse表中获取目的点的PassedPath,即为结果。
       
        下面就来看上述步骤的实现,该实现被封装在RoutePlanner类中:


         ///
      
    <summary>

       
    ///
      RoutePlanner 提供图算法中常用的路径规划功能。
       
    ///
      2005.09.06
       
    ///
      
    </summary>


         
    public
      
    class
      RoutePlanner
        {
            
    public
      RoutePlanner()
            {            
            }

            
    #region
      Paln

            
    //
    获取权值最小的路径


             
    public
      RoutePlanResult Paln(ArrayList nodeList ,
    string
      originID ,
    string
      destID)
            {
                PlanCourse planCourse
    =
      
    new
      PlanCourse(nodeList ,originID) ;

                Node curNode
    =
      
    this
    .GetMinWeightRudeNode(planCourse ,nodeList ,originID) ;

                
    #region
      计算过程

                
    while
    (curNode
    !=
      
    null
    )
                {
                    PassedPath curPath
    =
      planCourse[curNode.ID] ;
                   
    foreach
    (Edge edge
    in
      curNode.EdgeList)
                    {
                        PassedPath targetPath
    =
      planCourse[edge.EndNodeID] ;
                        
    double
      tempWeight
    =
      curPath.Weight
    +
      edge.Weight ;

                        
    if
    (tempWeight
    <
      targetPath.Weight)
                        {
                            targetPath.Weight
    =
      tempWeight ;
                            targetPath.PassedIDList.Clear() ;

                            
    for
    (
    int
      i
    =
    0
      ;i
    <
    curPath.PassedIDList.Count ;i
    ++
    )
                            {
                                targetPath.PassedIDList.Add(curPath.PassedIDList.ToString()) ;
                            }

                            targetPath.PassedIDList.Add(curNode.ID) ;
                        }
                    }

                   
    //
    标志为已处理


                     planCourse[curNode.ID].BeProcessed
    =
      
    true
      ;
                   
    //
    获取下一个未处理节点


                     curNode
    =
      
    this
    .GetMinWeightRudeNode(planCourse ,nodeList ,originID) ;
                }
                
    #endregion

                
                
    //
    表示规划结束


                
    return
      
    this
    .GetResult(planCourse ,destID) ;               
            }
            
    #endregion


            
    #region
      private method

            
    #region
      GetResult

            
    //
    从PlanCourse表中取出目标节点的PassedPath,这个PassedPath即是规划结果


             
    private
      RoutePlanResult GetResult(PlanCourse planCourse ,
    string
      destID)
            {
                PassedPath pPath
    =
      planCourse[destID]  ;            

                
    if
    (pPath.Weight
    ==
      
    int
    .MaxValue)
                {
                    RoutePlanResult result1
    =
      
    new
      RoutePlanResult(
    null
      ,
    int
    .MaxValue) ;
                   
    return
      result1 ;
                }
                
                
    string
    [] passedNodeIDs
    =
      
    new
      
    string
    [pPath.PassedIDList.Count] ;
                
    for
    (
    int
      i
    =
    0
      ;i
    <
    passedNodeIDs.Length ;i
    ++
    )
                {
                    passedNodeIDs
    =
      pPath.PassedIDList.ToString() ;
                }
                RoutePlanResult result
    =
      
    new
      RoutePlanResult(passedNodeIDs ,pPath.Weight) ;

                
    return
      result ;            
            }
            
    #endregion


            
    #region
      GetMinWeightRudeNode

            
    //
    从PlanCourse取出一个当前累积权值最小,并且没有被处理过的节点


             
    private
      Node GetMinWeightRudeNode(PlanCourse planCourse ,ArrayList nodeList ,
    string
      originID)
            {
                
    double
      weight
    =
      
    double
    .MaxValue ;
                Node destNode
    =
      
    null
      ;

                
    foreach
    (Node node
    in
      nodeList)
                {
                   
    if
    (node.ID
    ==
      originID)
                    {
                        
    continue
      ;
                    }

                    PassedPath pPath
    =
      planCourse[node.ID] ;
                   
    if
    (pPath.BeProcessed)
                    {
                        
    continue
      ;
                    }

                   
    if
    (pPath.Weight
    <
      weight)
                    {
                        weight
    =
      pPath.Weight ;
                        destNode
    =
      node ;
                    }
                }

                
    return
      destNode ;
            }
            
    #endregion

            
    #endregion

        }


        2006.05.22 应众多朋友要求,下面给出一个简单示例:
    RoutePlanner.Plan 过程详解:
    (1)用一张表(PlanCourse)记录源点到任何其它一节点的最小权值,初始化这张表时,如果源点能直通某节点,则权值设为对应的
       边的权,否则设为double.MaxValue
    (2)选取没有被处理并且当前累积权值最小的节点TargetNode,用其边的可达性来更新到达其它节点的路径和权值(如果其它节点
       经此节点后权值变小则更新,否则不更新),然后标记TargetNode为已处理
    (3)重复(2),直至所有的可达节点都被处理一遍。
    (4)从PlanCourse表中获取目的点的PassedPath,即为结果。



    [STAThread]
            
    static
      
    void
      Main(
    string
    [] args)
            {
                ArrayList nodeList
    =
      
    new
      ArrayList() ;

                
    //
    ***************** B Node *******************


                 Node aNode  
    =
      
    new
      Node(
    "
    A
    "
    ) ;
                nodeList.Add(aNode) ;
                
    //
    A -> B


                 Edge aEdge1
    =
      
    new
      Edge() ;
                aEdge1.StartNodeID
    =
      aNode.ID ;
                aEdge1.EndNodeID   
    =
      
    "
    B
    "
      ;
                aEdge1.Weight      
    =
      
    10
      ;
                aNode.EdgeList.Add(aEdge1) ;
                
    //
    A -> C


                 Edge aEdge2
    =
      
    new
      Edge() ;
                aEdge2.StartNodeID
    =
      aNode.ID ;
                aEdge2.EndNodeID   
    =
      
    "
    C
    "
      ;
                aEdge2.Weight      
    =
      
    20
      ;
                aNode.EdgeList.Add(aEdge2) ;
                
    //
    A -> E


                 Edge aEdge3
    =
      
    new
      Edge() ;
                aEdge3.StartNodeID
    =
      aNode.ID ;
                aEdge3.EndNodeID   
    =
      
    "
    E
    "
      ;
                aEdge3.Weight      
    =
      
    30
      ;
                aNode.EdgeList.Add(aEdge3) ;

                
    //
    ***************** B Node *******************


                 Node bNode  
    =
      
    new
      Node(
    "
    B
    "
    ) ;
                nodeList.Add(bNode) ;
                
    //
    B -> C


                 Edge bEdge1
    =
      
    new
      Edge() ;
                bEdge1.StartNodeID
    =
      bNode.ID ;
                bEdge1.EndNodeID   
    =
      
    "
    C
    "
      ;
                bEdge1.Weight      
    =
      
    5
      ;
                bNode.EdgeList.Add(bEdge1) ;
                
    //
    B -> E


                 Edge bEdge2
    =
      
    new
      Edge() ;
                bEdge2.StartNodeID
    =
      bNode.ID ;
                bEdge2.EndNodeID   
    =
      
    "
    E
    "
      ;
                bEdge2.Weight      
    =
      
    10
      ;
                bNode.EdgeList.Add(bEdge2) ;

                
    //
    ***************** C Node *******************


                 Node cNode  
    =
      
    new
      Node(
    "
    C
    "
    ) ;
                nodeList.Add(cNode) ;
                
    //
    C -> D


                 Edge cEdge1        
    =
      
    new
      Edge() ;
                cEdge1.StartNodeID
    =
      cNode.ID ;
                cEdge1.EndNodeID   
    =
      
    "
    D
    "
      ;
                cEdge1.Weight      
    =
      
    30
      ;
                cNode.EdgeList.Add(cEdge1) ;

                
    //
    ***************** D Node *******************


                 Node dNode  
    =
      
    new
      Node(
    "
    D
    "
    ) ;
                nodeList.Add(dNode) ;

                
    //
    ***************** C Node *******************


                 Node eNode  
    =
      
    new
      Node(
    "
    E
    "
    ) ;
                nodeList.Add(eNode) ;
                
    //
    C -> D


                 Edge eEdge1        
    =
      
    new
      Edge() ;
                eEdge1.StartNodeID
    =
      eNode.ID ;
                eEdge1.EndNodeID   
    =
      
    "
    D
    "
      ;
                eEdge1.Weight      
    =
      
    20
      ;
                eNode.EdgeList.Add(eEdge1) ;


                RoutePlanner planner
    =
      
    new
      RoutePlanner() ;
                RoutePlanResult result
    =
      planner.Paln(nodeList ,
    "
    A
    "
      ,
    "
    D
    "
    ) ;

                planner
    =
      
    null
      ;
            }

      
    敬请了解:
      
    ESFramework通信框架     OMCS网络语音视频框架     MFile语音视频录制组件    MCapture语音视频采集组件  StriveEngine轻量级通信引擎    OAUS 自动升级系统  
      
      


    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|手机版|Java学习者论坛 ( 声明:本站资料整理自互联网,用于Java学习者交流学习使用,对资料版权不负任何法律责任,若有侵权请及时联系客服屏蔽删除 )

    GMT+8, 2024-3-29 20:59 , Processed in 0.344315 second(s), 38 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表