旅行商分支限界法.cpp

用来解决旅行商问题 可以直接运行 很好的代码

#include <stack>
#include <iostream>
#include <stdlib.h>
#include <fstream>

using namespace std;

int MaxNumOfNodes = 100;

typedef struct _StackElement
{
  int NodeNum;
  bool ChildChecked;
} StackElement, *LPStameckElent;

bool CheckUnique(stack<StackElement> &s, int val);

int main()
{
  // 输入部分
  // ==============================================================================
  int NodeNum = 0;                          // 节点数目
  int StartNum = 1;                         // 起点
  int* Cost = NULL;                         // 花费
  int i, j;

  cout << "请输入节点数目: ";
  cin >> NodeNum;
  system("cls");

  // 至少2个节点
  if(NodeNum <= 1)
  {
    cout << "输入不正确!" << endl;

    return 1;
  }

  // 最多MaxNumOfNodes个节点
  if(NodeNum > MaxNumOfNodes)
  {
    cout << "节点数目过大, 计算有可能很慢!" << endl;

    return 1;
  }

  // 初始化
  Cost = new int[NodeNum*NodeNum];
  for(i=0; i<NodeNum; ++i)
  {
    for(j=0; j<NodeNum; ++j)
    {
      Cost[i*NodeNum + j] = -1;   // 负数表示无穷大
    }
  }

  char command;
  int fromNode = 1;
  int endNode = 2;
  int cost = -1;
  
  do
  {
		cout << "【请以此输入有向边的权值, 格式: i, node1, node1, value】" << endl;
		cout << "【例如输入i 1 2 12表示节点1到节点2之间的权值为12】" << endl;
		cout << "【直接输入q, 结束输入】" << endl;
		cout << " 输入:";
		cin >> command;
    if(command == 'i')
    {
      cin >> fromNode >> endNode >> cost;

      if(
        fromNode < 1 || fromNode > NodeNum ||
        endNode < 1 || endNode > NodeNum ||
        fromNode == endNode || cost <= 0)
      {
        cout << "\n输入信息不正确, 请重新输入!" << endl;
      }
      else
      {
        Cost[(fromNode-1) * NodeNum + endNode - 1] = cost;
      }
    }
    else
    {
      command = 'q';
    }

    system("cls");
  }
  while(command != 'q');

  bool valid = false;
  do
  {
    cout << "请输入起始节点的编号: ";
    cin >> StartNum;
    system("cls");

    valid = StartNum >= 1 && StartNum <= NodeNum;

    if(!valid)
    {
      cout << "输入超出范围, 请重新输入!" << endl;
    }
  }
  while(!valid);

  // 算法部分
  // ==============================================================================
  stack< stack<StackElement> > ilMaxTraStack;
  int MinCost = -1;
  int CurrCost = 0;
  stack<StackElement> CurrTrailStack;

  StackElement elem;
  elem.NodeNum = StartNum-1;
  elem.ChildChecked = false;
  CurrTrailStack.push(elem);
  do
  {  	
    // 当堆栈满时
    if(CurrTrailStack.size() == NodeNum+1)
    {
      if(MinCost < 0 || MinCost > CurrCost)
      {
        while(!MaxTrailStack.empty())
        {
          MaxTrailStack.pop();
        }
        MaxTrailStack.push(CurrTrailStack);
        CurrTrailStack.pop();
        MinCost = CurrCost;
        CurrCost -= Cost[CurrTrailStack.top().NodeNum * NodeNum + StartNum - 1];

        StackElement elem = CurrTrailStack.top();
        elem.ChildChecked = true;
        CurrTrailStack.pop();
        CurrTrailStack.push(elem);
      }
      else if(MinCost == CurrCost)
      {
        MaxTrailStack.push(CurrTrailStack);
        CurrTrailStack.pop();
        CurrCost -= Cost[CurrTrailStack.top().NodeNum * NodeNum + StartNum - 1];

        StackElement elem = CurrTrailStack.top();
        elem.ChildChecked = true;
        CurrTrailStack.pop();
        CurrTrailStack.push(elem);
      }

      continue;
    }

    StackElement CurrNode = CurrTrailStack.top();
    // 所有子节点已经遍历完毕
    if(CurrNode.ChildChecked)
    {
      if(CurrTrailStack.size() == 1)
      {
        CurrTrailStack.pop();
      }
      else
      {
        CurrNode = CurrTrailStack.top();
        CurrTrailStack.pop();
        CurrCost -= Cost[CurrTrailStack.top().NodeNum * NodeNum + CurrNode.NodeNum];
        bool nextFound = false;
        for(i=(CurrNode.NodeNum+1)%NodeNum; i!=CurrTrailStack.top().NodeNum; i=(i+1)%NodeNum)
        {
          if(i==CurrTrailStack.top().NodeNum)
            continue;

          int cost = Cost[CurrTrailStack.top().NodeNum * NodeNum + i];
          if((cost > 0 && MinCost < 0) || (MinCost > 0 && cost > 0 && MinCost >= CurrCost + cost))
          {
            if((i==StartNum-1 && CurrTrailStack.size()==NodeNum) ||
                (i!=StartNum-1 && CheckUnique(CurrTrailStack, i)))
            {
              CurrCost += cost;
              nextFound = true;
              StackElement elem;
              elem.ChildChecked = false;
              elem.NodeNum = i;
              CurrTrailStack.push(elem);

              break;
            }
          }
        }

        if(!nextFound)
        {
          StackElement tmp = CurrTrailStack.top();
          tmp.ChildChecked = true;
          CurrTrailStack.pop();
          CurrTrailStack.push(tmp);
        }
      }
    }
    // 有可能还有子节点没有遍历
    else
    {
      bool nextFound = false;

      for(i=(CurrTrailStack.top().NodeNum+1)%NodeNum; i!=CurrTrailStack.top().NodeNum; i=(i+1)%NodeNum)
      {
	      int cost = Cost[CurrTrailStack.top().NodeNum * NodeNum + i];

        if((cost > 0 && MinCost < 0) || (cost > 0 && MinCost >= CurrCost + cost))
        {
          if((i==StartNum-1 && CurrTrailStack.size()==NodeNum) ||
              (i!=StartNum-1 && CheckUnique(CurrTrailStack, i)))
          {
            CurrCost += cost;
            StackElement elem;
            elem.ChildChecked = false;
            elem.NodeNum = i;
            CurrTrailStack.push(elem);

            nextFound = true;
            break;
          }
        }
      }

      if(!nextFound)
      {
        StackElement tmp = CurrTrailStack.top();
        tmp.ChildChecked = true;
        CurrTrailStack.pop();
        CurrTrailStack.push(tmp);
      }
    }
  }
  while(!CurrTrailStack.empty());


  // 结果输出
  // ==============================================================================
  int sol_size = MaxTrailStack.size();
  cout << "==============================================" << endl;
  cout << "解的数目: " << sol_size;
  if(sol_size > 0)
  {
    cout << " \t\t最小代价: " << MinCost << endl;
    for(i=0; i<sol_size; ++i)
    {
      cout << "路径" << i+1 << ": \t";
      stack<StackElement> sol = MaxTrailStack.top();
      MaxTrailStack.pop();
      do
      {
        cout << sol.top().NodeNum + 1 << " <- ";
        sol.pop();
      }
      while(sol.size() > 1);
      cout << sol.top().NodeNum + 1 << endl;
    }
  }
  else
  {
    cout << endl;
  }
  cout << "==============================================\n\n" << endl;

  // 释放内存
  // ==============================================================================
  delete [] Cost;

  return 0;
}

bool CheckUnique(stack<StackElement> &s, int val)
{
  stack<StackElement> tmp(s);

  while(!tmp.empty())
  {
    if(tmp.top().NodeNum == val)
    {
      return false;
    }
    else
    {
      tmp.pop();
    }
  }
  
  return true;
}