算法基础06——设计技巧之贪婪算法

求解最优化问题的算法通常需要经过一系列的步骤,在每个步骤都面临多个选择。
对于许多最优化问题,使用动态规划算法来求解有些杀鸡用牛刀了。可以使用更简单,更高效的算法——贪心算法。

贪婪算法(又叫贪心算法)分阶段的工作。在每一个阶段,可以认为所做的决定是最好的,而不考虑将来后果。通常这意味着某个局部最优。这种“眼下能够拿到的就拿”的策略是这类算法名称的由来。

当算法终止时我们希望局部最优等于全局最优。如果是这样的话,那么算法就是正确的;否则这是一个次最优解。如果不要求绝对最佳答案,那么有时使用简单的贪婪算法生成近似的答案,而不是使用通常产生准确答案所需的复杂算法。

贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

所以对所采用的贪心策略一定要仔细分析其是否满足无后效性(前面的结果对后面选择的影响)。

基本思路:

1. 建立数学模型来描述问题。

2. 把求解的问题分成若干个子问题。

3. 对每一子问题求解,得到子问题的局部最优解。

4. 把子问题的解局部最优解合成原来解问题的一个解。

贪心算法适用的问题
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题,要确定它是否具有贪心选择的性质,我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解,是从贪心选择开始的,而且作了贪心选择后,原问题简化为一个规模更小的类似子问题。然后,用数学归纳法证明,通过每一步贪心选择,最终可得到问题的一个整体最优解。

实际上,贪心算法适用的情况很少。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。

  while (目标问题集合 > 0 (或递归)){ 
         求解当前问题的最优解
    }

由所有解元素组合成问题的一个可行解;

背包问题(贪心算法解)

背包问题常用解有两种:1.贪心算法。2.动态规划。这里介绍最简单的贪心算法解示例。

假设你是个贪婪的小偷,背着可装25斤重东西的背包(不考虑尺寸),入室伺机盗窃各种可装入背包的物品。时间紧迫,这个时候来不及做过多的思考。在房间中你找到以下几种物品:
1.重10斤价值4000元的笔记本
2.重5斤价值3000元的相机
3.重20斤价值8000元的智能彩电
4.重100g价值2000元的智能手机
5.重1斤价值300的吉他
6.重1斤价值8元的啤酒
7.重15斤价值1000元的高档音响

请问偷哪些物品更优呢?

最简单的办法就是每次选择能装进背包最贵的物品。然后递归,看能继续装哪些物品,每次选择最贵的,直到装不下。当然这种办法并不是最优解,但是它是一种比最优解更加简单高效的算法。

哈夫曼编码

现在介绍一种算法哈夫曼(霍夫曼,赫夫曼)编码,这种算法用一个字符串中符号的出现频率(即出现概率)作为输入,并产生编码这个字符串的一个前缀码作为输出,在这些符号的所有可能的二又前缓码中,这个编码使用最少的位。这个所谓哈夫曼编码的算法是大卫·哈夫曼于1951年做麻省理工学院的研究生时发表在一篇学期论文中的。(注意,这个算法假定已知字符串中每个符号出现多少次,所以可以计算每个符号的出现频率,方法是用这个符号出现的次数除以这个字符串的长度。)哈夫曼编码是数据压缩中的基本算法,数据压缩的目的在于减少表示信息所需要的位数。哈夫曼编码广泛用于压缩表示文本的位串,并且在压缩视频和图像文件方面也起到重要作用。

给定符号及其频率,目标是构造一个有根的二又树,其中符号是树叶的标记。算法从只含有一个顶点的一些树构成的森林开始,其中每个顶点有一个符号作为标记,并且这个顶点的权就等于所标记符号的频率。在每一步,都把具有最小总权值的两个个树组合成一个单独的树,方法是引入一个新的根,把具有较大的权的树作为左子树,把具有较小的权的树作为右子树。另外,把这个树的两个子树的权之和作为这个树的总权值。(虽然可以规定在具有相同的权的树之间进行选择以打破平局的过程,但是这里将不具体指定这样的过程)当构造出了一个树,即森林缩小为单个树时,算法就停止

霍夫曼编码图解

/**
 * 常用的基本算法思想之 贪心算法 (常见分糖果,找零钱,区间覆盖之类的)
 * 发现形如:针对一组特定的数据,给定限制值和期望值,需要在满足限定值前提下,最大满足期望值。
 * (有限背包大小里面装东西价值最大之类的...每次放性价比最高的)
 * 是否可以用贪心算法解决:每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据。
 * 贪心算法不一定就是最优解,只能说是相对最优解(每步最优), 比如:加权图找到指定点的最短路径。前面的选择会影响后面的选择,不能保证最优
 * 贪心算法的一种基本应用: 霍夫曼编码
 */
public class HuffmanCode {
	// 建立数的节点类
	static class Node {
		int weight;// 频数
		int parent;
		int leftChild;
		int rightChild;

		public Node(int weight, int parent, int leftChild, int rightChild) {
			this.weight = weight;
			this.parent = parent;
			this.leftChild = leftChild;
			this.rightChild = rightChild;
		}

		void setWeight(int weight) {
			this.weight = weight;
		}

		void setParent(int parent) {
			this.parent = parent;
		}

		void setLeftChild(int leftChild) {
			this.leftChild = leftChild;
		}

		void setRightChild(int rightChild) {
			this.rightChild = rightChild;
		}

		int getWeight() {
			return weight;
		}

		int getParent() {
			return parent;
		}

		int getLeftChild() {
			return leftChild;
		}

		int getRightChild() {
			return rightChild;
		}
	}

	// 新建哈夫曼编码
	static class NodeCode {
		String character;
		String code;

		NodeCode(String character, String code) {
			this.character = character;
			this.code = code;
		}

		NodeCode(String code) {
			this.code = code;
		}

		void setCharacter(String character) {
			this.character = character;
		}

		void setCode(String code) {
			this.code = code;
		}

		String getCharacter() {
			return character;
		}

		String getCode() {
			return code;
		}
	}

	// 初始化一个huffuman树
	public static void initHuffmanTree(Node[] huffmanTree, int m) {
		for (int i = 0; i < m; i++) {
			huffmanTree[i] = new Node(0, -1, -1, -1);
		}
	}

	// 初始化一个huffmanCode
	public static void initHuffmanCode(NodeCode[] huffmanCode, int n) {
		for (int i = 0; i < n; i++) {
			huffmanCode[i] = new NodeCode("", "");
		}
	}

	// 获取huffmanCode的符号
	public static void getHuffmanCode(NodeCode[] huffmanCode, int n) {
		Scanner input = new Scanner(System.in);
		for (int i = 0; i < n; i++) {
			String temp = input.next();
			huffmanCode[i] = new NodeCode(temp, "");
		}
	}

	// 获取huffman树节点频数
	public static void getHuffmanWeight(Node[] huffmanTree, int n) {
		Scanner input = new Scanner(System.in);
		for (int i = 0; i < n; i++) {
			int temp = input.nextInt();
			huffmanTree[i] = new Node(temp, -1, -1, -1);
		}
	}

	// 从n个结点中选取最小的两个结点
	public static int[] selectMin(Node[] huffmanTree, int n) {
		int min[] = new int[2];
		class TempNode {
			int newWeight;// 存储权
			int place;// 存储该结点所在的位置

			TempNode(int newWeight, int place) {
				this.newWeight = newWeight;
				this.place = place;
			}

			void setNewWeight(int newWeight) {
				this.newWeight = newWeight;
			}

			void setPlace(int place) {
				this.place = place;
			}

			int getNewWeight() {
				return newWeight;
			}

			int getPlace() {
				return place;
			}
		}

		TempNode[] tempTree = new TempNode[n];

		// 将huffmanTree中没有双亲的结点存储到tempTree中
		int i = 0, j = 0;
		for (i = 0; i < n; i++) {
			if (huffmanTree[i].getParent() == -1 && huffmanTree[i].getWeight() != 0) {
				tempTree[j] = new TempNode(huffmanTree[i].getWeight(), i);
				j++;
			}
		}

		int m1, m2;
		m1 = m2 = 0;
		for (i = 0; i < j; i++) {
			if (tempTree[i].getNewWeight() < tempTree[m1].getNewWeight())// 此处不让取到相等,是因为结点中有相同权值的时候,m1取最前的
				m1 = i;
		}
		for (i = 0; i < j; i++) {
			if (m1 == m2)
				m2++;// 当m1在第一个位置的时候,m2向后移一位
			if (tempTree[i].getNewWeight() <= tempTree[m2].getNewWeight() && i != m1)// 此处取到相等,是让在结点中有相同的权值的时候,

				// m2取最后的那个。
				m2 = i;
		}

		min[0] = tempTree[m1].getPlace();
		min[1] = tempTree[m2].getPlace();
		return min;
	}

	// 创建huffmanTree
	public static void createHaffmanTree(Node[] huffmanTree, int n) {
		if (n <= 1)
			System.out.println("Parameter Error!");
		int m = 2 * n - 1;
		// initHuffmanTree(huffmanTree,m);

		for (int i = n; i < m; i++) {
			int[] min = selectMin(huffmanTree, i);
			int min1 = min[0];
			int min2 = min[1];
			huffmanTree[min1].setParent(i);
			huffmanTree[min2].setParent(i);
			huffmanTree[i].setLeftChild(min1);
			huffmanTree[i].setRightChild(min2);
			huffmanTree[i].setWeight(huffmanTree[min1].getWeight() + huffmanTree[min2].getWeight());
		}
	}

	// 创建huffmanCode
	public static void createHaffmanCode(Node[] huffmanTree, NodeCode[] huffmanCode, int n) {
		Scanner input = new Scanner(System.in);
		char[] code = new char[10];
		int start;
		int c;
		int parent;
		int temp;

		code[n - 1] = '0';
		for (int i = 0; i < n; i++) {
			StringBuffer stringBuffer = new StringBuffer();
			start = n - 1;
			c = i;
			while ((parent = huffmanTree[c].getParent()) >= 0) {
				start--;
				code[start] = ((huffmanTree[parent].getLeftChild() == c) ? '0' : '1');
				c = parent;

			}
			for (; start < n - 1; start++) {
				stringBuffer.append(code[start]);
			}
			huffmanCode[i].setCode(stringBuffer.toString());
		}
	}

	// 输出hufmanCode
	public static void ouputHaffmanCode(NodeCode[] huffmanCode, int n) {
		System.out.println("字符与编码的对应关系如下:");
		for (int i = 0; i < n; i++) {
			System.out.println(huffmanCode[i].getCharacter() + ":" + huffmanCode[i].getCode());
		}
	}

	// 主函数
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n;
		int m;
		System.out.print("请输入字符个数:");
		n = input.nextInt();
		m = 2 * n - 1;
		Node[] huffmanTree = new Node[m];
		NodeCode[] huffmanCode = new NodeCode[n];

		// 初始化huffmanTree,huffmanCode
		initHuffmanTree(huffmanTree, m);
		initHuffmanCode(huffmanCode, n);

		// 获取huffmanCode的符号
		System.out.print("请输入哈夫曼编码的字符:");
		getHuffmanCode(huffmanCode, n);

		// 获取huffmanTree的频数
		System.out.print("请输入哈夫曼编码字符对应的频数:");
		getHuffmanWeight(huffmanTree, n);

		// 创建huffmanTree
		createHaffmanTree(huffmanTree, n);
		// 创建huffmanCode
		createHaffmanCode(huffmanTree, huffmanCode, n);

		// 输出huffmanCode编码
		ouputHaffmanCode(huffmanCode, n);

	}
}

更新时间:2020-02-17 13:55:17

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/算法基础06设计技巧之贪婪算法
最后更新:2020-02-17 13:55:17

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×