2、部落卫队问题--回朔法
算法分析
本问题为组织一支队伍保卫部落,并且卫队中互不为仇敌,因而,实际可考虑在居民
中选择一个最大独立团问题。
构建一个无向图 G<v, e>,居民为图 G 的顶点,而居民间的关系为图 G 中无向边。用 1
表示两个居民的关系良好,而 0 表示两个居民有仇敌。这样最大独立团问题就成了图 G 顶
点集的子集的选取问题,可用子集树表示问题的解空间。设当前考察结点 Z 位于解空间树
的第 i 层。先考虑从顶点 i 到已选入独立团中的所有结点都要相连(即无仇敌关系),然后
进入左子树,否则进入右子树。
算法实现
#include <stdio.h>
#define OVERFLOW -2 //overflow of memory
#define MAX_VECTEX_NUM 50 //the max number of vectex
typedef struct
{
//adjacency matrix--adj[i][j]=1 means i and j are not enemy
int adj[MAX_VECTEX_NUM][MAX_VECTEX_NUM];
int curVector[MAX_VECTEX_NUM]; //current solution vector
int bestVector[MAX_VECTEX_NUM]; //best solution vectex
int curNum; //the vectex num in current solution
int bestNum; //the vectex num int best solution
int vectNum; //the vectex num in graph
}MGraph;
//
void backtrack(MGraph *IndeSet, int i)
{
int j;
//output best solution
if(i >= IndeSet->vectNum)
{
for(j=0;j<IndeSet->vectNum;j++)
IndeSet->bestVector[j] = IndeSet->curVector[j];
IndeSet->bestNum = IndeSet->curNum;
return;
}
//check the node i, whether it can join into current set or not
int ok = 1;
//1. enemy
for(j=0;j<i;j++)
评论3