算法单源最短路径.多级调度实验报告
中 南 大 学
《算法设计与分析》实验报告
姓 名：
专 业 班 级：
学 号： 指导教师：
完成日期：
吴冰 软件1002 3902100216 刘莉平 2011.11
一 实验名称
贪心算法实验
二 实验目的
(1) 了解贪心算法思想
(2) 掌握贪心法典型问题，如背包问题、作业调度问题等。
三、实验内容
(1) 编写一个简单的程序，实现单源最短路径问题。
(2) 编写一段程序，实现找零。
【问题描述】当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）。
(3) 编写程序实现多机调度问题
【问题描述】要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
四、算法思想分析
贪心算法：总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
贪心法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
五、算法源代码及用户屏幕
(1)编写一个简单的程序，实现单源最短路径问题。
#include
#include
using namespace std;
#define MAX 1000000 //充?当Ì¡À"无T穷?大ä¨"
#define LEN sizeof(struct V_sub_S)
#define N 5
#define NULL 0
int s; //输º?入¨?的Ì?源¡ä点Ì?
int D[N]; //记?录?最Á?短¨¬路¡¤径?
int S[N]; //最Á?短¨¬距¨¤离¤?已°?确¨¡¤定¡§的Ì?顶£¤点Ì?集¡¥ const int G[N][N] = { {0, 10, MAX, 30, 100},
{MAX, 0, 50, MAX, MAX}, {MAX, MAX, 0, MAX, 10}, {MAX, MAX, 20, 0, 60},
{MAX, MAX, MAX, MAX, 0} };
typedef struct V_sub_S //V-S链¢¡ä表À¨ª
{
int num;
struct V_sub_S *next;
};
struct V_sub_S *create()
{
struct V_sub_S *head, *p1, *p2;
int n = 0;
head = NULL;
p1 = (V_sub_S *)malloc(LEN);
p1->num = s;
head = p1;
for(int i = 0; i
{
if(i != s)
{
++ n;
if(n == 1)
head = p1;
else
p2->next = p1;
p2 = p1;
p1 = (V_sub_S *)malloc(LEN);
p1->num = i;
p1->next = NULL;
}
}
free(p1);
return head;
}
struct V_sub_S *DelMin(V_sub_S *head, int i) //删¦?除y链¢¡ä表À¨ª中D值¦Ì为a i 的Ì?结¨¢点Ì?
{
V_sub_S *p1, *p2;
p1 = head;
while(i != p1->num && p1->next !=NULL)
{
p2 = p1;
p1 = p1->next;
}
p2->next = p1->next;
return head;
}
void Dijkstra(V_sub_S *head, int s)
{
struct V_sub_S *p;
int min;
S[0] = s;
for(int i = 0; i
{
D[i] = G[s][i];
}
for(int i = 1; i
{
p = head->next;
min = p->num;
while(p->next != NULL)
{
if(D[p->num] > D[(p->next)->num])
min = (p->next)->num;
p = p->next;
}
S[i] = min;
head = DelMin(head, min);
p = head->next;
while(p != NULL)
{
if(D[p->num] > D[min] + G[min][p->num])
{
D[p->num] = D[min] + G[min][p->num];
}
p = p->next;
}
}
}
void Print(struct V_sub_S *head)
{
struct V_sub_S *p;
p = head->next;
while(p != NULL)
{
if(D[p->num] != MAX)
{
cout num num] next;
}
else
{
cout num
p = p->next;
}
}
}
int main()
{
struct V_sub_S *head;
cout
cin >> s;
head = create();
Dijkstra(head, s);
head = create();
Print(head);
system("pause");
return 0;
}
(2)编写一段程序，实现找零。
【问题描述】当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）。
//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分
//输出：找钱方案
#include
using namespace std;
#define NUM 4
void main()
{
int m[NUM]={25,10,5,1};
int meishu[NUM]={0,0,0,0};
int n; //假设n=99
cout
cin>>n;
cout
for(int i=0;i
{
while(n>=m[i]&&n>0)
{ } meishu[i]++; //cout
}
}
(3) 编写程序实现多机调度问题
【问题描述】要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
#include
using namespace std;
#define N 10
#define M 3
void sort(int t[],int n);
int set_work1(int t[],int n);
int max(int t[],int num);
int min(int t[],int m);
int set_work2(int t[],int n);
static int time[N]={2,8,18,32,50,72,98,128,182,200},s[M]={0,0,0};
void main()
{
}
void sort(int t[],int n)
{
} for(int k=0;kt[j]) { } j=i; sort(time,N); if(M>=N) //作业数小于机器数 { } else { } system("PAUSE"); cout
int max(int t[],int num) //max函数求解处理时间总和最长
{
}
int min(int t[],int m)
{
}
int set_work1(int t[],int n)
{
} int m=0; for(int i=0;is[i]) min=i; int min=0; //min记录目前处理作业时间和最小的机器号 for(int i=1;i
int set_work2(int t[],int n)
{
} for(int i=0;i
s[min(s,M)]+=t[i];
六、实验过程分析
对最短路径中红点集蓝点集的算法实例表示不理解，需要仔细思考
注意到贪心算法不一定总能得到整体问题的最优解
贪心法存在的问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围
对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。
但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：
贪心选择性质
最优子结构性质。