分派问题的回溯算法与实现.doc

期
末
考
查

设计科目：算法设计与分析
设计名称：分派问题的回溯算法与实现
姓名：
学号：
序号：
班级：

分派问题的回溯算法与实现

一、期末考查题目
分派问题:给n个人分派n件工作,把工作j分派给第i个人的成本cost(i,j),设计、编程、测试回溯算法,在给每个人分派一件不同工作的情况下使得总成本最小。

二、问题分析
回溯法原理分析
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再的技术为回溯法。
可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个HYPERLINK"http://baike.baidu.com/view/3821785.htm"状态空间E={（x1，x2，…，xn）∣xi∈Si，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且|Si|有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
分派问题原理
假设有n个人的成本是w,工作效率p和完成工作的总成本M均为已知正数，这个问题要求选择出成本的一个子集,使得，且极小化，这n个x构成一个取0/1值的向量。
分派问题的表示方案
功能：用回溯法得可行解并选最优解。
树中的节点：求解过程的一个状态
树中的边：标示xi的一个可能的值
解向量：由根节点到任意叶节点的路径定义
解空间：由根节点到所有叶节点的路径定义
答案节点：求出最优解的状态

回溯法求解的基本思想：
基本任务：
1)根据问题特点设计状态空间树
2)逐个地生成问题状态
3)确定问题状态是否是解状态
4)确定解状态是否是答案状态
规范函数：
intFIND(intk)
{inti;
for(i=0;i<k;i++)
if(x[i]==x[k])
return0;
return1;
}
搜索过程：
先深度搜索记录搜索的各节点的成本和s再与os比较如果s比os小，将s赋值给os,并将搜索到的节点赋给y[i]，当深度搜索结束，返回上一个节点继续搜索；如此循环，直到搜索搜索结束。Y[i]即为所求的答案节点。
1、主要数据类型与变量
intsum;//表示在分派任务过程中每成功分派一个累计成本；
intx[n];//记录每成功分派任务给的人员；
inty[n];//记录分派任务时任务分派所给的人员所得最小成本；
intSACNF()；//输入人员和任务表
intPRINTF();//输出人员和任务表
intFIND(intk)//规范函数，判断任务k是否可以分给x[k]号人员。
voidTASK()//用回溯法得可行解并选最优解。
intARRANGE();//输出查找后分配的对应表
2、源程序
#include<stdio.h>
#defineN5
inta[N][N];
intx[N],y[N];
intmin=100;

SCANF()
{inti,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
scanf("%d",&a[i][j]);
}
}
}

PRINTF()
{
inti,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
printf("%d",a[i][j]);
}
printf("\n");
}
}

FIND(k)
{inti;
for(i=0;i<k;i++)
if(x[i]==x[k])return0;
return1;
}

TASK()
{intk=0,sum,i;
x[k]=-1;
while(k>=0)
{x[k]++;
while((x[k]<N)&&(!FIND(k)))
x[k]++;
if(x[k]<N)
{
if(k<N-1)
{
k=k+1;
x[k]=-1;
}
else
{sum=0;
for(i=0;i<N;i++)
{sum+=a[i][x[i]];
}
if(sum<min)
{
min=sum;
for(i=0;i<N;i++)
y[i]=x[i];
}
}
}
elsek--;
}
}

ARRANGE()
{inti;
for(i=0;i<N;i++)
{
printf("序号为%d做任务%d\n",i+1,y[i]+1);
}
}

voidmain()
{inti,j;
printf("输入人和任务对应表：%d行（人序号）%d列（任务）\n",N,N);
SCANF();
printf(