欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

贪婪算法

程序员文章站 2022-03-12 15:01:47
...

贪婪算法

在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择,贪心策略使用的前提是局部最优能导致全局最优。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性

由于贪心时可能会用到优先队列,这里再回顾一下优先队列的创建方式:

priority_queue<int> q;//默认降序排列,即大值优先级高

//1. 引入<funcional>库实现升序
priority_queue<int, vector<int>, less<int>> q;//降序排列
priority_queue<int, vector<int>, greater<int>> q;//升序排列

//2. 自定义cmp结构体时,return xx<xx; 表示降序
struct cmp{
    bool operator()(Node* &a, Node* &b)
    {
        return a->value > b->value;
    }
};
priority_queue<Node*,vector<Node*>,cmp> que;

//3. 目标类中直接定义比较方式
class student{
    ...
    friend bool operator < (const student &s1, const student &s2){
       return s1.grade < s2.grade;//降序
    }   
}
priority_queue<student> que;

huffman树

核心就是每次贪婪选择最小的两棵子树(叶子)。

描述
给定一个字符串,求出该字符串的huffman编码的长度和。

思路
1. 用map统计各个字符个数
2. 将个数封装成Node类,放入优先队列中,升序排列。
3. 每次取头两个,加和后再放进优先队列,如果是叶子节点就放进一个vector中(可以通过判断是否有孩子实现)。

代码

#include <vector>
#include <string>
#include <iostream>
#include <functional>
#include <map>
#include <queue>
using namespace std;

class Node{
public:
    int value;
    Node *parent = NULL;
    Node *left = NULL;
    Node *right = NULL;
    Node(int value=0):value(value){}
    Node(const Node &n){
        value = n.value;
        parent = n.parent;
        left = n.left;
        right = n.right;
    }
};
struct cmp{
    bool operator()(Node* &a, Node* &b)
    {
        return a->value > b->value;
    }
};

int main()
{
    string str = "qqweweasq";
    map<char, int> m;
    for (int i = 0; i < str.size(); i++){
        if (m.find(str[i]) == m.end())
            m.insert(pair<char, int>(str[i], 1));
        else
            m[str[i]]++;
    }

    priority_queue<Node*,vector<Node*>,cmp> que;
    for (auto &i : m)
        que.push(new Node(i.second));

    vector<Node*> vec;
    Node *a,*b,*p;
    while (que.size() != 1){
        a = que.top();que.pop();
        b = que.top(); que.pop();
        p = new Node(a->value + b->value);
        p->left = a; a->parent = p;
        p->right = b; b->parent = p;
        que.push(p);
        if (a->left==NULL)
            vec.push_back(a);
        if (b->left==NULL)
            vec.push_back(b);
    }

    int res = 0;
    for (auto n : vec){
        int tmp = 0;
        Node *p = n;
        while (p->parent != NULL){
            tmp++;
            p = p->parent;
        }
        res += tmp;
    }
    cout << endl<<res;
    system("pause");
    return 0;
}

队列里面放指向节点的指针,因为要保证每个节点在内存中的位置不变,否则拷贝来拷贝去容易出现如parent指针指向为空的情况。
可以看到,这里的节点指针都是手动new 内存的,虽然指针可能会释放掉(?),但是指针指向的内存不会自动释放。所以创建的所有节点有且只有一个,没有拷贝的情况。

最短路径算法 dijkstra

核心:每步贪婪选择最短边。

描述
https://vjudge.net/problem/ZOJ-1221
前19行里输入与第i行相邻的城市有n个,以及n个城市的编号,给出一个数m,再每给出两个城市的编号,求最短距离。

思路
其实就是简化版的最短路径算法,其中路径长度都为1(如果存在路径的话)。

贪婪算法
代码

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#define MAX 1000000
using namespace std;
struct node{
    int dis;
    int index;
    node(int index, int dis = 1) :dis(dis), index(index){}
    friend bool operator<(const node &node1, const node &node2){
        return node1.dis < node2.dis;
    }
};
vector<vector<int>> vec;
priority_queue<node> que;

void dijkstra(int from, int to)
{
    vector<int> last(21, -1);
    vector<int> mdis(21, MAX);
    vector<int> visited(21,0);
    last[from] = from;
    visited[from] = 1;
    for (int i = 1; i <= 20; i++){
        mdis[i] = vec[from][i];
        if (i!=from&&mdis[i]!=MAX)
            que.push(node(i));
    }
    while (!que.empty()){
        node n = que.top(); 
        que.pop();
        visited[n.index] = 1;
        for (int i = 1; i <= 20; i++){
            if (!visited[i] && vec[n.index][i] != MAX){
                que.push(node(i));
                if (mdis[i]>mdis[n.index] + vec[n.index][i]){
                    mdis[i] = mdis[n.index] + vec[n.index][i];
                    last[i] = n.index;
                }
            }
        }
    }
    cout << from << " to " << to << ": " << mdis[to] <<endl;

}
int main()
{   
    int num = 1;
    int n, tmp;

    while (cin>>n){
        for (int i = 0; i <= 20; i++)
            vec.push_back(vector<int>(21, MAX));
        for (int i = 0; i < n; i++){//第一行单独操作,
            vec[1][1] = 0;
            cin >> tmp;
            vec[1][tmp] = 1;
            vec[tmp][1] = 1;
        }
        for (int i = 2; i <= 19; i++){
            vec[i][i] = 0;
            cin >> n;
            for (int j = 0; j < n; j++){
                cin >> tmp;
                vec[i][tmp] = 1;
                vec[tmp][i] = 1;
            }
        }
        cin >> n;
        cout << "Test Set#" << num++ << endl;
        int from, to;
        for (int i = 0; i < n; i++){
            cin >> from >> to;
            dijkstra(from, to);
        }
    }

    system("pause");
    return 0;
}