人狼羊菜过河 -- Leo Jay[2004-12-17 22:05:01]
1. 广度优先搜索 by Leo Jay
狂汗，完全乱了……
好像这里不支持C++的Highlight，而小弟的Python是刚刚才学的…… 
- 改好格式了,很简单的,你看一下帮助就好了! -- Dreamingk
小弟我认为，这题至少有以下三种不同的解法：
- 广度优先搜索方法: 优点是找出的一定是使用的步数小的解，缺点是占用存储空间较多，一般只用于找最优解，不会用于找所有解。
- 深度优先搜索：优点是程序(相对来说)写起来超……简单，占用空间小，可以找出所有的解，缺点是一般只用于搜索规模较小的问题，得出的结果不能保证是最优解(除非把所有的可能都搜索一遍)
- 图论：这个……，基本上没有什么大的优点，如果说有，那么就是通用。很多问题都能转化为图论的形式来做。缺点是，怎么转化要花些心思，而且写程序实在很难，写出高效易懂的程序就更难了……
这里显示有问题，等我搞明白怎么整wiki再说。这是我第一次wiki……
#include <iostream>
using namespace std;
const int VEGET = 1;
const int SHEEP = VEGET << 1;
const int WOLF = SHEEP << 1;
const int FARMER = WOLF << 1;
bool used[20]; // 状态是否到达过的标志
int bfs[1000]; // 广度优先搜索时存放状态
int pre[1000]; // 父结点
inline int SetBit( int x, int pos )
{
return x | pos;
}
inline int DelBit( int x, int pos )
{
return x & ~pos;
}
// 检查状态x是否合法
inline bool IsLegal( int x )
{
if ( x & FARMER ) // 如果农夫在的话
{
// 菜和羊都不在，或是羊和狼都不在是不可以的
if ( ((x&(VEGET|SHEEP))==0) || ((x&(SHEEP|WOLF))==0) )
{
return false;
}
} else // 如果农夫不在的话
{
// 菜和羊都在，或是羊和狼都在是不可以的
if ( ((x&(VEGET|SHEEP))==(VEGET|SHEEP)) || ((x&(SHEEP|WOLF))==(SHEEP|WOLF)) )
{
return false;
}
}
// 否则，是合法的状态
return true;
}
// 广度优先搜索
int BFSSearch()
{
int i;
int x;
int iLeft = -1;
int iRight = 1;
bfs[0] = FARMER|WOLF|SHEEP|VEGET;
used[ bfs[0] ] = true;
while( ++iLeft<iRight ) // 只要状态没有结束
{
if ( bfs[iLeft] & FARMER ) // 这里有农夫
{
x = DelBit(bfs[iLeft],FARMER);
if ( !used[x] && IsLegal(x) ) // 农夫什么都不带过去
{
pre[iRight] = iLeft;
bfs[iRight] = x;
used[x] = true;
iRight++;
}
for ( i=0; i<3; i++ ) // 带一样东西过去
{
if ( (bfs[iLeft]&(1<<i)) == 0 ) // 如果要带过去的不在这边
{
continue;
}
x = DelBit(bfs[iLeft],FARMER|(1<<i) );
if ( !used[x] && IsLegal(x) ) // 状态不存在且可行
{
pre[iRight] = iLeft;
bfs[iRight] = x;
used[x] = true;
if( x == 0 ) // 如果找到目标，返回
{
return iRight;
}
iRight++;
}
}
} else
{
x = SetBit(bfs[iLeft],FARMER);
if ( !used[x] && IsLegal(x) ) // 农夫什么都不带回来
{
pre[iRight] = iLeft;
bfs[iRight] = x;
used[x] = true;
iRight++;
}
for ( i=0; i<3; i++ ) // 带一样东西回来
{
if ( bfs[iLeft]&(1<<i) ) // 如果要带回来的已经在这边
{
continue;
}
x = SetBit(bfs[iLeft],FARMER|(1<<i) );
if ( !used[x] && IsLegal(x) ) // 状态不存在且可行
{
pre[iRight] = iLeft;
bfs[iRight] = x;
used[x] = true;
if( x == 0 )
{
return iRight;
}
iRight++;
}
}
}
}
return -1;
}
// 递归输出结果
void OutputSolution( int iRet )
{
if ( pre[iRet] != -1 )
{
OutputSolution( pre[iRet] );
}
cout << " --> ";
if ( bfs[iRet]&FARMER )
{
cout << "Farmer ";
} else
{
cout << " ";
}
if ( bfs[iRet]&WOLF )
{
cout << "Wolf ";
} else
{
cout << " ";
}
if ( bfs[iRet]&SHEEP )
{
cout << "Sheep ";
} else
{
cout << " ";
}
if ( bfs[iRet]&VEGET )
{
cout << "Vegetable ";
} else
{
cout << " ";
}
cout << endl;
}
int main(int argc, char* argv[])
{
memset( used, 0, sizeof(used) );
memset( pre, 0xff, sizeof(pre) );
int iRet = BFSSearch();
if ( iRet == -1 )
{
cout << "No solution!" << endl;
} else
{
OutputSolution( iRet );
}
return 0;
}
2. 深度优先搜索 by Leo Jay
这一题的第二种解法:) 这段时间没什么时间写文章，我想先把我知道的三种解法程序写出来， 再把文章写出来吧。(程序员嘛，写文章是最头大的……)
PS,谢谢Dreamingk兄及Zoom Quiet兄。小弟刚玩wiki，谢谢指点。
#include <iostream>
using namespace std;
const int VEGET = 1;
const int SHEEP = VEGET << 1;
const int WOLF = SHEEP << 1;
const int FARMER = WOLF << 1;
bool used[20]; // 状态是否到达过的标志
int step[100];
inline int SetBit( int x, int pos )
{
return x | pos;
}
inline int DelBit( int x, int pos )
{
return x & ~pos;
}
// 检查状态x是否合法
/*
注：由农夫，狼，羊，菜四者的真值表转成卡诺图后化简可得一逻辑函数式：
所以IsLegal函数也可写为：
bool IsLegal( bool bFarmer, bool bWolf, bool bSheep, bool bVeget )
{
return !( (!bFarmer&!bSheep) | bFarmer&(bSheep|bWolf&bVeget) | (!bWolf&bSheep&!bVeget) );
}
设当前状态为status，则调用方法是
IsLegal( status&FARMER, status&WOLF, status&SHEEP, status&VEGET )
注意，这个逻辑函数式形式简单，但可读性极差。
*/
inline bool IsLegal( int x )
{
if ( x & FARMER ) // 如果农夫在的话
{
// 菜和羊都不在，或是羊和狼都不在是不可以的
if ( ((x&(VEGET|SHEEP))==0) || ((x&(SHEEP|WOLF))==0) )
{
return false;
}
} else // 如果农夫不在的话
{
// 菜和羊都在，或是羊和狼都在是不可以的
if ( ((x&(VEGET|SHEEP))==(VEGET|SHEEP)) || ((x&(SHEEP|WOLF))==(SHEEP|WOLF)) )
{
return false;
}
}
// 否则，是合法的状态
return true;
}
// 输出状态iStatus
void OutputStatus( int iStatus )
{
if ( iStatus&FARMER )
{
cout << "Farmer ";
} else
{
cout << " ";
}
if ( iStatus&WOLF )
{
cout << "Wolf ";
} else
{
cout << " ";
}
if ( iStatus&SHEEP )
{
cout << "Sheep ";
} else
{
cout << " ";
}
if ( iStatus&VEGET )
{
cout << "Vegetable ";
} else
{
cout << " ";
}
cout << endl;
}
// 输出解
void OutputSolution( int iSteps )
{
int i;
for( i=0; i<=iSteps; i++ )
{
cout << "--> ";
OutputStatus( step[i] );
}
cout << "-------------------------" << endl;
cout << endl;
}
// 深度优先搜索
void DFSSearch( int iStatus, int iStep )
{
int i;
int iNewStatus;
step[iStep] = iStatus;
if( iStatus == 0 ) // 如果找到目标，输出并返回
{
OutputSolution( iStep );
return;
}
used[iStatus] = true;
if ( iStatus & FARMER ) // 这里有农夫
{
iNewStatus = DelBit(iStatus,FARMER);
if ( !used[iNewStatus] && IsLegal(iNewStatus) ) // 农夫什么都不带过去
{
// 如果可以的话，搜索下一步
DFSSearch(iNewStatus, iStep+1);
}
for ( i=0; i<3; i++ ) // 带一样东西过去
{
if ( (iStatus&(1<<i)) == 0 ) // 如果要带过去的不在这边
{
continue;
}
iNewStatus = DelBit(iStatus,FARMER|(1<<i) );
if ( !used[iNewStatus] && IsLegal(iNewStatus) ) // 状态不存在且可行
{
// 如果可以的话，搜索下一步
DFSSearch(iNewStatus, iStep+1);
}
}
} else
{
iNewStatus = SetBit(iStatus,FARMER);
if ( !used[iNewStatus] && IsLegal(iNewStatus) ) // 农夫什么都不带回来
{
// 如果可以的话，搜索下一步
DFSSearch(iNewStatus, iStep+1);
}
for ( i=0; i<3; i++ ) // 带一样东西回来
{
if ( iStatus&(1<<i) ) // 如果要带回来的已经在这边
{
continue;
}
iNewStatus = SetBit(iStatus,FARMER|(1<<i) );
if ( !used[iNewStatus] && IsLegal(iNewStatus) ) // 状态不存在且可行
{
// 如果可以的话，搜索下一步
DFSSearch(iNewStatus, iStep+1);
}
}
}
used[iStatus] = false;
}
int main()
{
memset( used, 0, sizeof(used) );
DFSSearch( FARMER|WOLF|SHEEP|VEGET, 0 );
return 0;
}
3. 反馈
好！谢谢，分享！不过注释要有哪！特别是算法的解释…… ZoomQuiet