使用分支界定和动态规划解决最短路径问题(原)

这个我上个学期做算法作业的时候写程序的思路,现在拿出来和大家分享,我也算复习了一下

算法的思想:

分析题目要求，我们可以得知：算法要实现找到一条花费在1500元以下的最短的路径。其中这里面涉及两个变量，一个是路径的长度，要求最短。一个是花费，要求不大于1500元。基于这两个变量的不同的要求，本算法实现了两种分支限定的方法。对于”距离”变量，由于要求其最短，故使用优先级队列的分支限界法，可保证算法沿优先级最高（在这里也就是当前节点到起点距离最短的节点）向前进行搜索，这样就可以保证第一次搜索到达终点的路径，就是最短路径。对于”花费”变量，算法首先计算图中的每一个点到达终点的最少花费(使用的是改进的Floyd算法)。记录在minCost[51]数组中，对于当前正在搜索的节点，如果当前点到达起点的费用+当前点到达终点的费用之和大于1500元，则进行剪枝。除上述两个重要的思想外，本算法还使用动态规划的思想：也就是在搜寻过程中，若我们发现有两条路径可到达同一点，我们便可放弃到达那一点成本较高的路径而对这条路径停止搜寻。

算法中的使用的数据结构:

CArcItem：代表访问的城市，也就是状态空间树中的状态节点

class CArcItem

{

      int m_CityID;                      //当前访问的城市序号[1-50]

       int m_dDisToStart;                    //起始城市到当前访问城市的路径长度

       int m_dCostToStart;                  //起始城市到当前访问城市所需费用

       CArcItem * m_pParentArcItem;       //生成的最短路径树中的父节点

}

CPriorityQueu：优先级队列，采用二叉堆实现，对城市状态空间树中的状态节点(也就是城市)按照当前访问城市到起始城市的距离进行升序排序，使当前访问城市到起始城市的距离最小的节点始终在二叉堆的堆顶，也就是优先级最高。

minCost[51]数组：记录图中所有节点到达终点的最小花费。初始化在Floyd()方法中实现。

哈希表：DomSet：记录当前城市ID和当前城市到达起点城市”最小距离”,这里之所以加引号，是因为这个最小距离是随着搜索的进行而不断的减小的，也就是在搜寻过程中，若我们发现有两条路径可到达同一城市，我们便可放弃到达那一点成本较高的路径而对这条路径停止搜寻。

openTable保存所有已生成而未考察的节点，

closeTable记录已访问过的节点。

算法流程图：

程序主要代码

void CPathPlan::Floyd()

{

       for(int k = 1;k < 51;k++)

       {

              for(int i = 1;i < 51;i++)

              {

                     if(CostMap[i][destination] > CostMap[i][k] + CostMap[k][destination])

                     {

                            minCost[i] = CostMap[i][k] + CostMap[k][destination];

                     }

                     else

                     {

                            minCost[i] = CostMap[i][destination];

                     }

              }

       }

       minCost[destination] = 0;

}

bool CPathPlan::Plan()

{

if(origin == destination)

       {

              this->m_pTailArcItem = pLinkCurItem;

              this->m_pHeadArcItem = pLinkCurItem;

              bFoundPath = true;

              return bFoundPath;

       }

priorityQueue.PushHeap(pLinkCurItem);

       openTable.insert(std::make_pair<int,void*>(origin,pLinkCurItem));

       DomSet.insert(std::make_pair<int,int>(origin,0));

       while(!priorityQueue.isEmpty())

       {

              pLinkCurItem = priorityQueue.PopHeap();

              openTable.erase(pLinkCurItem->m_CityID);

closeTable.insert(std::make_pair<int,void*>(pLinkCurItem->m_CityID,pLinkCurItem));

              curCol = pLinkCurItem->m_CityID;

              if(curCol == destination)

              {

                     m_pTailArcItem = pLinkCurItem;

                     bFoundPath = true;

                     return bFoundPath;

              }

              for(curRow = 1;curRow < 51;curRow++)

              {

                     if(DisMap[curCol][curRow] == NO_ROAD_DIS)

                            continue;

                     else

                     {

                            disToStart = pLinkCurItem->m_dDisToStart + DisMap[curCol][curRow];

                            costToStart = pLinkCurItem->m_dCostToStart + CostMap[curCol][curRow];

                     }

                     if(costToStart + minCost[curRow]<= upCost)

                     {

                            it = DomSet.insert(std::make_pair<int,int>(curRow,disToStart));

                            if(it.second ||it.first->second > disToStart)

                            {

                                   it.first->second = disToStart;

                                   tableIt = closeTable.find(curRow);

                                   if(tableIt == closeTable.end())

                                   {

                                          //不在close表中

                                          tableIt = openTable.find(curRow);

                                          if(tableIt == openTable.end())

                                          {     //不在close表中也不再open表中//作为一个新状态插入

                                                 CArcItem_Ptr  pNewItem = new CArcItem;

                                                 pNewItem->m_CityID = curRow;

                                                 pNewItem->m_pParentArcItem = pLinkCurItem;

                                                 pNewItem->m_dDisToStart = disToStart;

                                                 pNewItem->m_dCostToStart = costToStart;

                                                 priorityQueue.PushHeap(pNewItem);

                            openTable.insert(std::make_pair<int,void*>(pNewItem->m_CityID,pNewItem));

                                          }

                                          else

                                          {

                                                 //不在close表中,但在open表中，如果值比以前小，那么更新

                                                 CArcItem_Ptr pItem = (CArcItem_Ptr)(tableIt->second);

                                                 if(pItem->m_dDisToStart - disToStart > 0)

                                                 {

                                                        //_ASSERT(FALSE);

                                                        pItem->m_pParentArcItem = pLinkCurItem;

                                                        pItem->m_dDisToStart = disToStart;

                                                        pItem->m_dCostToStart = costToStart;

                                                        priorityQueue.EditItem(pItem);

                                                 }

                                          }

                                   }

                            }

                     }

              }

       }

       return bFoundPath;

}