六虎

商人过河：如何使用图算法求出所有的解？

作者：

三分梦

在

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动概况。

商人过河问题扩展

昨天评论了商人过河问题的基本解法和算法：
将算法应用于实际——商人过河问题 – ()

3个商人、3个侍从的话商人可以保命，那n个商人，m个侍从呢？

很显然，咱们上期的算法不是专门为3个商人和3个侍从量身定做的。

在上期的代码中，咱们只要给相应的数组扩容，然后再修改mNum,fNum，就能求解恣意数量的商人过河问题。（当然不能超过c++内存限制啦）

比方，在我写的代码中，我将全局变量mNum和fNum改成了4和4，最后程序惋惜地输出了：

无解！

一切的答案？

既然有解，那我为什么不顺便输出一切的解呢？

考虑到咱们用DFS的方法，我选择了树这一数据结构来保存一切的可行途径。

首要树的结点的结构体如下，咱们用vector来保存一切的结点：

struct State
{
   int m;
   int f;
   int b; // 0代表运向左边，1代表运向右边
   vector<int> sons;//贮存在数组中的索引
};
vector<State> trackTree;

咱们来递归的研究这一问题：

假定DFS函数的输入是一个图的结点。

假如该状况不能到达终究状况，则输出0；假如可以到达终究状况，则生成一个途径树，回来树根的索引。

树的结构如下：

咱们进入一个DFS函数后，他先判断自己自身是不是结尾。假如是，那么他直接在vector中生成一个结点并回来索引，因为节点自身便是途径树。

假如不是结尾的话，他会遍历一切的邻接结点，顺次履行DFS。 假如存在一次DFS不回来0，那么他就会生成一个结点，作为回来的结点的父节点。

在把一切的邻接结点都遍历完之后，假如一切的DFS都回来0，那就阐明无解，它自己也可以回来0了。假如存在不为0的回来值，阐明有解，并且已经生成好了一个途径树。 回来索引即可。

留意！请设置一个found[m][f][b]数组，进入DFS时令相应状况的found为1，即将回来时令其为0.不然很简单呈现之后的递归会回到这次递归的结点，然后产生无数个回路！

输出格式

写好代码后，咱们的计算机心爱的帮咱们求出了一切可行的状况途径：

请别离输入商人数、侍从数、船舶容量:
4 2 2
(0 0 0) (0 0 1) 
(0 1 0) (0 1 1)
(0 2 0) (0 2 1)
(1 0 0) (1 0 1)
(1 1 0) (1 1 1)
(2 0 0) (2 0 1)
(2 1 0) (2 1 1)
(2 2 0) (2 2 1)
(3 1 0) (3 1 1)
(3 2 0) (3 2 1)
(4 0 0) (4 0 1)
(4 1 0) (4 1 1)
(4 2 0) (4 2 1)
一切状况的数量：26
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (3,2,1) (1,1,0) (4,1,1) (0,2,0) (4,2,1) 
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (3,2,1) (1,1,0) (4,2,1)
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (3,2,1) (2,0,0) (4,2,1)
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (4,1,1) (0,2,0) (4,2,1) 
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (4,1,1) (1,1,0) (3,2,1) (2,0,0) (4,2,1)
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (4,1,1) (1,1,0) (4,2,1)
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (3,1,0) (3,1,1) (2,1,0) (3,2,1) (1,1,0) (4,1,1) (0,2,0) (4,2,1) 
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (3,1,0) (3,1,1) (2,1,0) (3,2,1) (1,1,0) (4,2,1)
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (3,1,0) (3,1,1) (2,1,0) (3,2,1) (2,0,0) (4,2,1)
...

具体代码如下：

/*
首要解决问题一：最简单的形式，3个商人(m)与3个侍从(f)过河
具有可行的状况，具有状况搬运的方式
从初始状况搬运至终究状况
m指河左边的商人数，f是侍从数，b=0代表船在左边，1在右边
*/
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::string;
using std::vector;
const int maxn = 1000 + 7;
int found[maxn][maxn][2];
int able[maxn][maxn][2];
struct State
{
   int m;
   int f;
   int b; // 0代表运向左边，1代表运向右边
   vector<int> sons;
};
vector<State> trackTree;
vector<int> trackStack;
int mNum, fNum, bCap;
int stateNum;
//留意：在状况搬运时不能搬运回去，不然可能无限递归
//给通过的状况设置符号
// DFS回来0代表没有可行途径，回来正数代表结点在trackTree里的下标
int DFS(int m, int f, int b)
{
   found[m][f][b] = 1;
   int index;
   // trackTree.push_back(State{m, f, b, vector<int>()});
   // index = trackTree.size() - 1;
   if (m == 0 && f == 0 && b == 1)
   {
      found[m][f][b] = 0;
      trackTree.push_back(State{m, f, b, vector<int>()});
      index = trackTree.size() - 1;
      return index;
   }
   int flag = 0;
   for (int d1 = 0; d1 <= bCap; d1++)
   {
      for (int d2 = 0; d2 <= bCap; d2++)
      {
         if (d1 + d2 <= bCap && d1 + d2 > 0)
         {
            int m1, f1, b1;
            if (b == 1)
            {
               m1 = m + d1, f1 = f + d2, b1 = 0;
               if (!(m1 <= mNum && f1 <= fNum && able[m1][f1][b1] && !found[m1][f1][b1]))
                  continue;
            }
            else
            {
               m1 = m - d1, f1 = f - d2, b1 = 1;
               if (!(m1 >= 0 && f1 >= 0 && able[m1][f1][b1] && !found[m1][f1][b1]))
                  continue;
            }
            int ret = 0;
            if (ret = DFS(m1, f1, b1))
            {
               //保证只履行一次
               if (flag == 0)
               {
                  flag = 1;
                  trackTree.push_back(State{m, f, b, vector<int>()});
                  index = trackTree.size() - 1;
               }
               trackTree[index].sons.push_back(ret);
            }
         }
      }
   }
   found[m][f][b] = 0;
   return flag == 1 ? index : 0;
}
void setEnableState()
{
   for (int m = 0; m <= mNum; m++)
   {
      for (int f = 0; f <= fNum; f++)
      {
         int m1 = mNum - m, f1 = fNum - f;
         //任何一边，商人比侍从多或许商人为0为可行状况
         if ((m >= f || m == 0) && (m1 >= f1 || m1 == 0))
         {
            able[m][f][0] = able[m][f][1] = 1;
            printf("(%d %d %d) ", m, f, 0);
            printf("(%d %d %d) \n", m, f, 1);
            stateNum += 2;
         }
      }
   }
}
void Print(int index)
{
   trackStack.push_back(index);
   if (trackTree[index].sons.size() == 0)
   {
      //此刻栈里已经是一条完好的track
      for (auto i : trackStack)
      {
         auto t = trackTree[i];
         printf("(%d,%d,%d) ", t.b == 1 ? mNum - t.m : t.m, t.b == 1 ? fNum - t.f : t.f, t.b);
      }
      putchar('\n');
      trackStack.pop_back();
      return;
   }
   for (auto son : trackTree[index].sons)
   {
      Print(son);
   }
   trackStack.pop_back();
   return;
}
int main()
{
   cout << "请别离输入商人数、侍从数、船舶容量:\n";
   cin >> mNum >> fNum >> bCap;
   setEnableState();
   cout << "一切状况的数量：" << stateNum << '\n';
   trackTree.push_back(State()); //添加一条空数据
   if (DFS(mNum, fNum, 0))
   {
      for (int i = 0; i < trackTree.size(); i++)
         if (trackTree[i].b == 0 && trackTree[i].f == fNum && trackTree[i].m == mNum)
            Print(i);
   }
   else
      cout << "无解！\n";
   return 0;
}

更多文章