m_c.txt

Backtrack_M_C algorithm by AI

//////////////////////////////////////////////////////////////////////////
//																		//
//				 用回溯方法求解传教士和野人问题				//
//																		//
//									//
//																		//
//////////////////////////////////////////////////////////////////////////

#include<stdio.h>
#include<string.h>
#include<fstream.h>

int n , k ;

// 标记状态是否失败
bool g[100][100][2] ;

// 路径链表数据结构
typedef struct Node
{
	int c , s , b ;
	Node *next ;
} Node ;

// 表头节点
Node *path ;

// 链表插入操作
void Insert( int churchman, int savage, int boat )
{
	Node *newnode = new Node() ;
	newnode->c = churchman ;
	newnode->s = savage ;
	newnode->b = boat ;
	newnode->next = path->next ;
	path->next = newnode ;
}

// 递归搜索函数
bool Search(int churchman, int savage, int boat)
{
	// 递归结束条件
	if (churchman == 0 && savage == 0 && boat == 1)	
	{
		Insert(churchman, savage, boat) ;
		return true ;
	}

	// 岸上约束
	if (   (savage < 0 || savage > n) 
		|| (churchman < 0 || churchman > n) 
		|| (churchman > 0 && churchman < savage) 
		|| (n-churchman > 0 && n-churchman < n-savage)
	) return false ;

	// 如果该状态已经被以前的尝试证明为失败状态，则不必再尝试
	if (g[churchman][savage][(boat+1)/2]) return false ;
	else g[churchman][savage][(boat+1)/2] = true ;

	// 对上船策略进行搜索
	// i、j分别是船上的传教士数、野人数
	for (int i = k ; i >= 0 ; i--)
		for (int j = k-i ; j >= 0 ; j--)
		{			
		    if (i + j == 0				// 船不能空载
				|| (i > 0 && i < j) 	// 船上如果有传教士，其数目不能小于野人数
			) continue ;

			// 递归，从这里可以看出boat赋值为+-1的好处
			if (Search(churchman+boat*i,savage+boat*j,-boat))
			{ 
				// 记录路径
				Insert(churchman, savage, boat) ;		        
			    return true ;
			}
		}
	// 记录失败状态
	g[churchman][savage][(boat+1)/2] = false ;
	return false ;
}

void main()
{	
	// 初始化
	path = new Node() ; path->next = NULL ;
	memset(g, false, sizeof(g)) ;
	printf("n,k = ") ; scanf("%d,%d",&n,&k) ;	

	if (true==Search(n,n,-1))
	{
		Node *pt = path->next;
		while ( pt )
		{
			printf( "(%d,%d,%d)\n", pt->c, pt->s, pt->b ) ;	
			pt = pt->next ;
		}
	}
	else printf("No Solution.\n") ;

	char ch ; scanf("%c",&ch); scanf("%c",&ch);
}