HELP!求交替链怎么求?

Question

要解决一个经典问题,安全渡河问题:三名商人个带一名仆从,要乘一只小船过河,这只小船最多只能容纳两个人,仆从们密约,在河的任一岸,只要他们的人数比商人多,就杀人取货,但,如何乘船的大权操纵在商人的手中,商人们知道了这项密约,请你为商人们制定一个安全过河的方案.
我想到要用到DFS(深度优先策略),可有一个关键问题,我想破脑袋也想不出到底怎么求交替链,向大虾们求救,能不能帮我搞定求交替链的算法,或者告诉我解决这个问题的其他思路,万分感激.

Answer 1

struct INFO
{
int nSavage; // 岸边野人的数量 开始为3 全部到对岸为0
int nBoanerges; // 岸边传教士的数量 开始为3 全部到对岸为0
int nSide; // 船的位置 在此岸为-1 彼岸为1
int nMoveSavage; // 渡河的野人的数量，用于递归时记录操作状态
int nMoveBoanerges; // 渡河的传教士的数量，用于递归时记录操作状态
INFO* pPrevious;
INFO* pNext;
};// 判断是否有下一个满足条件的渡河方案
bool GetNextMove(INFO* pInfo)
{
// 渡船的优先顺序
// 此岸数量多优先，野人优先，彼岸数量少优先，传教士优先。
const int nStoreCount = 5;
struct STORE
{
int nSavage;
int nBoanerges;
}; STORE listStore[nStoreCount];
if (pInfo->nSide == -1)
{
listStore[0].nSavage = 2;
listStore[0].nBoanerges = 0;
listStore[1].nSavage = 1;
listStore[1].nBoanerges = 1;
listStore[2].nSavage = 0;
listStore[2].nBoanerges = 2;
listStore[3].nSavage = 1;
listStore[3].nBoanerges = 0;
listStore[4].nSavage = 0;
listStore[4].nBoanerges = 1;
}
else
{
listStore[0].nSavage = 0;
listStore[0].nBoanerges = 1;
listStore[1].nSavage = 1;
listStore[1].nBoanerges = 0;
listStore[2].nSavage = 0;
listStore[2].nBoanerges = 2;
listStore[3].nSavage = 1;
listStore[3].nBoanerges = 1;
listStore[4].nSavage = 2;
listStore[4].nBoanerges = 0;
} int iStart;
if (pInfo->nMoveSavage == 0 && pInfo->nMoveBoanerges == 0)
{
iStart = 0;
}
else
{
for (iStart=0; iStart<nStoreCount; iStart++)
{
if (pInfo->nMoveSavage == listStore[iStart].nSavage && pInfo->nMoveBoanerges == listStore[iStart].nBoanerges)
break;
}
iStart++;
}

if (iStart < nStoreCount)
{
int i;
for (i=iStart; i<nStoreCount; i++)
{
int nSideSavage = pInfo->nSavage + listStore[i].nSavage * pInfo->nSide;
int nSideBoanerges = pInfo->nBoanerges + listStore[i].nBoanerges * pInfo->nSide;
int nBesideSavage = 3 - nSideSavage;
int nBesideBoanerges = 3 - nSideBoanerges; // 传教士数量大于等于野人或为零
if ((nSideSavage<=nSideBoanerges || nSideBoanerges == 0) &&
(nBesideSavage<=nBesideBoanerges || nBesideBoanerges == 0) &&
nSideSavage>=0 && nSideBoanerges>=0 && nBesideSavage>=0 && nBesideBoanerges>=0)
{
// 如果本此解等于上次，放弃
if (pInfo->pPrevious != NULL)
{
if (pInfo->pPrevious->nMoveBoanerges == listStore[i].nBoanerges &&
pInfo->pPrevious->nMoveSavage == listStore[i].nSavage)
continue;
}
break;
}
}
if (i < nStoreCount)
{
pInfo->nMoveSavage = listStore[i].nSavage;
pInfo->nMoveBoanerges = listStore[i].nBoanerges;
return true;
}
} return false;
}// 递归函数
bool Ship(INFO* pInfo)
{
if (GetNextMove(pInfo))
{
INFO* pNew = new INFO;
pNew->nSavage = pInfo->nSavage + pInfo->nMoveSavage * (pInfo->nSide);
pNew->nBoanerges = pInfo->nBoanerges + pInfo->nMoveBoanerges * (pInfo->nSide);
pNew->nSide = (pInfo->nSide) * (-1);
pNew->pPrevious = pInfo;
pNew->pNext = NULL;
pNew->nMoveSavage = 0;
pNew->nMoveBoanerges = 0;
pInfo->pNext = pNew;
if (pNew->nSavage == 0 && pNew->nBoanerges == 0) return true; // 完成
return Ship(pNew);
}
else
{
INFO* pPre = pInfo->pPrevious;
if (pPre == NULL) return false; // 无解
delete pInfo;
pPre->pNext = NULL;
return Ship(pPre);
}
return true;
}int main(int argc, char* argv[])
{
INFO* pHead = new INFO;
pHead->nSavage = 3;
pHead->nBoanerges = 3;
pHead->nSide = -1;
pHead->pPrevious = NULL;
pHead->pNext = NULL;
pHead->nMoveSavage = 0;
pHead->nMoveBoanerges = 0; if (Ship(pHead))
{
printf("渡河过程如下：\n");
INFO* pInfo = pHead;
while (pInfo->pNext)
{
printf("渡河方向：%s  人数：野人%d - 传教士%d  此岸野人数：%d, 传教士数：%d\n", 
(pInfo->nSide == -1) ? "-->" : "<--", pInfo->nMoveSavage, 
pInfo->nMoveBoanerges, pInfo->nSavage, pInfo->nBoanerges);
pInfo = pInfo->pNext;
}
printf("渡河完成。");
}
else
{
printf("此题无解！");
} // 删除链表
while (pHead)
{
INFO* pTemp = pHead->pNext;
delete pHead;
pHead=pTemp;
}
pHead = NULL; printf("请结束程序。");
return 0;
}程序结果
渡河过程如下：
渡河方向：-->  人数：野人2 - 传教士0  此岸野人数：3, 传教士数：3
渡河方向：<--  人数：野人1 - 传教士0  此岸野人数：1, 传教士数：3
渡河方向：-->  人数：野人2 - 传教士0  此岸野人数：2, 传教士数：3
渡河方向：<--  人数：野人1 - 传教士0  此岸野人数：0, 传教士数：3
渡河方向：-->  人数：野人0 - 传教士2  此岸野人数：1, 传教士数：3
渡河方向：<--  人数：野人1 - 传教士1  此岸野人数：1, 传教士数：1
渡河方向：-->  人数：野人0 - 传教士2  此岸野人数：2, 传教士数：2
渡河方向：<--  人数：野人1 - 传教士0  此岸野人数：2, 传教士数：0
渡河方向：-->  人数：野人2 - 传教士0  此岸野人数：3, 传教士数：0
渡河方向：<--  人数：野人0 - 传教士1  此岸野人数：1, 传教士数：0
渡河方向：-->  人数：野人1 - 传教士1  此岸野人数：1, 传教士数：1
渡河完成。请结束程序。Press any key to continue