算法设计与分析（贪心法）_贪心算法的基本思想

 

目录

一、贪心法的基本思想

二、贪心法的基本要素

1.最优子结构性质

2.贪心选择性质

三、贪心法的解题步骤及算法设计模式

步骤：

1.分解：

2.解决：

3.合并：

设计模式：

四、会场安排问题

 五、最优装载问题

六、单元最短路径问题

---

一、贪心法的基本思想

贪心法是一种稳扎稳打的算法，他从问题的摸一个初始解出发，在每一个阶段都根据贪心策略来做出当前最优决策，逐步逼近给定目标，尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时，算法终止。也可以理解为：以逐步的局部最优，达到最终的全局最优。

二、贪心法的基本要素

1.最优子结构性质

        当一个问题的最优解一定包含其他子问题的最优解时，称此问题具有最优子结构性质。（一个问题能够分解成各个子问题来解决，通过各个子问题的最优解能递推到原问题的最优解，此时原问题的最优解一定包含各个子问题的最优解，这是能够采用贪心法来求解问题的关键）

        在分析问题是否具有最优子结构性质时，通常先设出问题的最优解，给出子问题的解一定是最优的结论。然后，采用反证法证明“子问题的解一定时最优的”结论成立。证明思路是：设原问题的最优解导出子问题的解不是最优的，然后在这个假设下可以构造出比原问题的最优解更好的解，从而导致矛盾。

2.贪心选择性质

        贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择获得，即通过一系列的逐步局部最优选择使得最终的选择方案是全局最优的。其中每次所做的选择，可以依赖于以前的选择，但不依赖于将来所做的选择。

        贪心选择性质所做的是一个非线性的子问题处理流程，即一个子问题并不依赖于另一个子问题，但是子问题间有严格的顺序性。

三、贪心法的解题步骤及算法设计模式

步骤：

1.分解：

将原问题分解为若干个相互独立的阶段。

2.解决：

对于每个阶段依据贪心策略进行贪心选择，求出局部的最优解。

3.合并：

将各个阶段的解合并为原问题的一个可行解。

设计模式：

Greedy(A,n)
{
    //A[0:n-1]包含n个输入，即A是问题的输入集合
    将解集合solution初始化为空;
    for(i=0;i<n;i++)                        //原问题分解为n个阶段
    {
        x=select(A);                        //依据贪心策略做贪心选择，求得局部最优解
        if(x可以包含在solution)              //判断解集合solution在加入x后是否满足约束条件
            solution=union(solution,x);    //部分局部最优解进行合并
    }
    return (解向量solution);                //n个阶段完成后，得到原问题的最优解
}

四、会场安排问题

        此问题的核心思想是：每次从剩下未安排的会议中选择具有最早结束时间且不会与已安排的会议重叠的会议来安排。这样可以使下一个会议尽快开始。

1）实现活动安排问题的贪心算法。

测试数据可选用：

#include <iostream>
using namespace std;
void Select(int n, int A[],int B[], bool C[])
{
	int i, j;
	C[1] = true;
	j = 1, i = 2;
	while (i <= n)
	{
		if (A[i] > B[j]) {
			C[i] = true;
			j = i;
		}
		else {
			C[i] = false;
		}
		i++;
	}
};
 
 
int main()
{
	int A[11] = { 0,1,3,2,5,3,5,6,8,8,2 },
		B[11] = { 0,4,5,6,7,8,9,10,11,12,13 };
	bool C[11];
	Select(11, A, B, C);
	cout << "活动安排如下：" << endl;
	for (int k = 1; k <= 11; k++)
	{
		while (C[k])
		{
			cout << A[k]<<"  "<<B[k] << endl;
			break;
		}
	}
	return 0;
}

运算截图如下：

 五、最优装载问题

2）实现最优装载的贪心算法。

测试数据可选用：

假设轮船限重12kg

#include "TanXin2.h"
#include<iostream>
using namespace std;
#define Max 10
typedef struct {
	int *elem;
	int length;
}SqList;
 
int InitList(SqList &L)//构造并初始化
{
	L.elem = new int[Max];
	if (!L.elem) return 0;
	L.length = 0;
	return 1;
}
 
void InputList(SqList &L,SqList &LB, int n)
{
	L.length = 0;
	if (n<0 || n>Max) return;
	cout << "请输入顺序表" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> L.elem[i];
		L.length++;
	}
	for (int j = 0; j < n; j++)
	{
		LB.elem[j] = L.elem[j];
		LB.length++;
	}
}
 
void OutputList(SqList L)
{
	for (int i = 0; i < L.length; i++)
	{
		cout << L.elem[i] << " ";
 
	}
}
 
void Compare(SqList &L)//冒泡排序
{
	int i, j, e;
	for (i = 1; i <= L.length; i++)
	{
		for (j = 0; j < L.length - i; j++)
		{
			if (L.elem[j] > L.elem[j + 1])
			{
				e = L.elem[j];
				L.elem[j] = L.elem[j + 1];
				L.elem[j + 1] = e;
			}
		}
	}
}
 
int LocateElem(SqList L, int e)//查找数据是否在顺序表内
{
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i] == e) return i + 1;//查找成功，返回序号i+1
	}
	return 0;//查找失败，返回0
}
 
void Select(SqList &L,SqList &LB,int m)
{
	int sum = 0;
	for (int i = 0; i < L.length; i++)
	{
		if ((sum + L.elem[i]) < m)
		{
			sum += L.elem[i];
			cout<< LocateElem(LB, L.elem[i]) <<"  "<< L.elem[i] << endl;
		}
		else {
			break;
		}
	}
}
 
int main()
{
	int n = 5,m=12;
	SqList LA,LB;
	InitList(LA);
	InitList(LB);
	InputList(LA,LB,n);
	Compare(LA);
	cout << "所选择的为：" << endl;
	Select(LA,LB,m);
 
}

代码运行截图如下：

六、单元最短路径问题

3）单源最短路径的贪心算法。

测试数据可选用下图，1为源点：

#include<iostream>
#include<string>
using namespace std;
const int inf = INT_MAX;
 
void Dijkstra(int n, int source, int *dist, int *prev, int c[8][8])
{
	//表示点是否在s集合里
	bool *s=new bool[n];
	for (int i = 0; i < n; i++)
	{
		dist[i] = c[source][i];
		//初始化时，除了source外所有结点都不在s集合
		s[i] = i == source ? true : false;
		//结点可达，前驱结点记作源点
		//结点不可达，前驱结点记作-1
		prev[i] = dist[i] == inf ? -1 : source;
 
	}
	for ( i = 1; i < n; i++)//找n-1个点
	{
		int mindist = inf;
		int newnode;//记录距离source最近的点
		for (int j = 0; j < n; j++)
		{
			//j点不在s集合中,且到soutce的距离小于上一个点到source的距离
			if (!s[j] && dist[j] < mindist)
			{
				newnode = j;
				mindist = dist[newnode];
			}
		}
		s[newnode] = true;
		for ( j = 0;j < n; j++)//当s集合加入新结点时，需要更新dist和prev
		{
			if (!s[j] && c[newnode][j] < inf)
			{
				//点不在s中，且与新节点相邻
				int newdist = dist[newnode]+c[newnode][j];//新结点到source的距离+新结点到j点的距离
				if (newdist < dist[j])
				{
					dist[j] = newdist;
					prev[j] = newnode;//新结点成了前驱结点
				}
			}
 
		}
 
	}
}
 
int main()
{
	int c[8][8] = { 
		{0,2,inf,1,inf,3,inf,inf},
	    {inf,0,6,inf,5,inf,inf,inf},
		{inf,inf,0,inf,inf,inf,inf,6},
		{inf,10,inf,0,inf,inf,2,inf},
		{inf,inf,9,inf,0,inf,inf,4},
		{inf,inf,inf,5,inf,0,4,inf},
		{inf,7,inf,inf,3,inf,0,8},
		{inf,inf,inf,inf,inf,inf,inf,0}
	};
	int n = 8;
	int dist[8];
	int prev[8];
	int source = 0;
	Dijkstra(8, source, dist, prev, c);
	cout << "源点到各点的最短路径为:";
	for (int i = 0; i < n; i++)
	{
		cout << dist[i] << " ";
	}
	return 0;
}

 运行结果如图所示：