Greedy算法的探究

小蓝 • 2024-12-22 08:07 • 编程

在计算机科学中，贪心算法（Greedy Algorithm）也叫贪婪算法，是指在对问题求解时，总是做出在当前看来最好的选择，不追求最优解，快速高效完成问题求解。在有些情况下，贪心算法能得到全局最优解或者是局部最优解。

一、算法基础

贪心算法是一种基于贪心思想的算法策略，在每个阶段选择最优解，从而达到全局最优解的策略。贪心算法是一种较为简单的算法设计策略，具有易于理解、简单、易于证明其正确性等优点。贪心算法与动态规划算法、回溯算法等常用算法比较类似。

具体地说，应用贪心算法的问题分为以下几步：

1. 定义最优解的结构，并递归地定义其最优性。

2. 构造一个包含所求问题的所有可行解的集合。

3. 证明这个集合为空，或者这个集合只是某些最优解的子集而非最优解集合。

4. 设计一个算法，在可行解集合中选择和最优解有关的解，并递归地构造最优解。

5. 证明算法构造的最优解是最优解。

二、应用场景

贪心算法通常适用于满足贪心选择属性的问题，并且贪心选择属性能够推导出全局最优解的问题，例如最小生成树、最短路径问题等。在一些特殊情况下，贪心算法也能得到全局最优解，例如哈夫曼编码等。

三、代码实现

贪心算法在Prim最小生成树问题中的应用

#include 
using namespace std;
typedef long long ll;
typedef pair pii;

const int MAXN = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m, s;
ll dis[MAXN];
bool vis[MAXN];
vector g[MAXN];

void prim(int s)
{
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    priority_queue<pii, vector, greater> q;
    q.push({ 0, s });
    ll ans = 0;
    while (!q.empty())
    {
        pii t = q.top();
        q.pop();
        int u = t.second;
        vis[u] = true;
        if (dis[u] != t.first)
            continue;
        ans += dis[u];
        for (auto& e : g[u])
        {
            int v = e.first, w = e.second;
            if (!vis[v] && w < dis[v])
            {
                dis[v] = w;
                q.push({ dis[v], v });
            }
        }
    }
    cout << ans <> n >> m >> s;
    for (int i = 0; i > u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    prim(s);
    return 0;
}

贪心算法在Dijkstra最短路径问题中的应用

#include 
using namespace std;
typedef long long ll;
typedef pair pli;

const int MAXN = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m, s;
ll dis[MAXN];
bool vis[MAXN];
vector g[MAXN];

void dijkstra(int s)
{
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    priority_queue<pli, vector, greater> q;
    q.push({ 0, s });
    while (!q.empty())
    {
        pli t = q.top();
        q.pop();
        int u = t.second;
        vis[u] = true;
        if (dis[u] != t.first)
            continue;
        for (auto& e : g[u])
        {
            int v = e.second;
            ll w = e.first;
            if (!vis[v] && dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                q.push({ dis[v], v });
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    cout <> n >> m >> s;
    for (int i = 0; i > u >> v >> w;
        g[u].emplace_back(w, v);
    }
    dijkstra(s);
    return 0;
}

四、结语

贪心算法作为一种基本的算法策略，具有易于理解、易于实现和快速高效的特点，在实际的算法设计和问题求解中都有广泛的应用。但是，贪心算法存在一些问题，例如贪心选择并不总能推导出全局最优解等。

综上所述，贪心算法在实际应用中需要结合具体问题，进行适当的分析和考虑，并利用必要的技巧和策略才能够更好地解决问题。通过不断地学习和实践，才能不断提升自己的算法设计和问题求解能力。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/283143.html