当前位置：首页 > article >正文

算法图解（8~10贪心，动态规划，K最近邻算法）

article 2024/9/22 6:30:36

贪心算法

在每一步都选择局部最优解，从而期望最终得到全局最优解。

贪心算法并不总能保证全局最优解，因此需要满足以下两个条件：

贪心选择性质：可以通过局部最优选择构造出全局最优解。
最优子结构：问题的最优解包含其子问题的最优解。

实例：给定面额的硬币，用最少硬币凑出指定金额

int minCoins(vector<int>& coins, int amount) {
    int count = 0;
    for (int i = coins.size() - 1; i >= 0; --i) {
        count += amount / coins[i];
        amount %= coins[i];
    }
    return count;
}

NP完全问题

NP完全问题（NP-Complete Problem）是计算复杂性理论中的一个重要概念，它代表了一类特别难解决的问题。

P类问题:可以在多项式时间内由确定性算法解决。

NP类问题：这些问题的解可以在多项式时间内通过确定性算法验证，尽管找到解的过程可能非常困难。

以下是一些常见的NP完全问题：

旅行商问题（TSP）：给定一组城市和它们之间的距离，找到一条路径，使得旅行商访问每个城市一次且总路程最短。
顶点覆盖问题：在一个图中，选择最小数量的顶点，使得每条边至少有一个端点在这些顶点中。
3-SAT问题：给定一个布尔公式的CNF形式，判断是否存在一个真值赋值使得公式成立。
背包问题：给定一组物品，每个物品有一个价值和重量，选择其中一些物品使得总价值最大并且总重量不超过给定的限制。

解决NP完全问题的常用策略:

由于NP完全问题在一般情况下无法在多项式时间内求解，常用的策略包括：

近似算法：找到一个接近最优解的解。
启发式算法：如贪心算法、局部搜索等，虽然不能保证最优解，但通常能在合理时间内找到一个可行解。
分支定界法：在搜索解空间时，通过剪枝来减少计算量。
动态规划和分治法：在特定情况下，这些方法能有效地解决NP完全问题的某些

动态规划（Dynamic Programming, DP）

将一个复杂的问题分解为更简单的子问题，然后通过求解这些子问题来构建原问题的解。与贪心算法不同，动态规划不仅关注局部最优解，而是通过递归或迭代的方式求解全局最优解。

两个核心性质：最优子结构：重叠子问题

经典问题:

斐波那契数列：F(n)=F(n−1)+F(n−2),
背包问题:定一组物品，每个物品有重量和价值，求如何在不超过背包容量的情况下最大化总价值。
最长公共子序列（LCS）：给定两个序列，求它们的最长公共子序列长度。

实例：0/1 背包问题，循环前i个物品开始，容量为j时最大价值

int knapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (weights[i - 1] <= w) {//《=当前的最大容量，可以选择添加物品
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

实例LCS：第一个序列前i个字符与第二个序列前j个字符的LCS长度


int longestCommonSubsequence(const string& X, const string& Y) {
    int m = X.length();
    int n = Y.length();
    
    // 创建一个二维数组 dp[m+1][n+1]
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 填充 dp 数组
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i - 1] == Y[j - 1]) {//如果当前相等，就可以加入
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {//否则，取上一次的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // 返回 LCS 的长度
    return dp[m][n];
}

递归 VS DP

递归:

自顶向下：递归从原问题出发，逐步分解成更小的子问题，直到遇到基础情况，然后再返回并组合结果。
重复计算：在没有优化的情况下，递归会重复计算许多相同的子问题。例如，在求解斐波那契数列时，递归会多次计算相同的斐波那契值，导致指数级的时间复杂度。

动态规划:

记忆化递归（自顶向下DP）：在递归的基础上添加记忆化（也叫备忘录法），即将每个子问题的结果保存下来，当再次遇到相同子问题时直接返回保存的结果，避免了重复计算。
自底向上DP：动态规划还可以通过自底向上的方式，从最小的子问题开始逐步求解，直到得到原问题的解。这种方式通常使用表格或数组存储中间结果。

K最近邻算法

KNN是一种用于分类（编组）和回归（预测结果）的算法。通过比较样本之间的距离，找到距离目标样本最近的K个邻居，然后根据这些邻居的标签来进行分类。

优点：直观，应用于任意分布的数据，多类别分类问题

缺点：计算复杂度高：对样本的距离计算依赖

实例：用于机器学习领域

// 计算两个点之间的欧几里得距离
double euclideanDistance(vector<double>& point1, vector<double>& point2) {
    double sum = 0.0;
    for (int i = 0; i < point1.size(); ++i) {//测试点到所有点的距离和
        sum += pow(point1[i] - point2[i], 2);
    }
    return sqrt(sum);
}

// KNN分类
int knnClassify(vector<vector<double>>& trainData, vector<int>& trainLabels, vector<double>& testData, int K) {
    vector<pair<double, int>> distances;  // 存储距离和对应的标签
    
    // 计算测试点到所有训练点的距离
    for (int i = 0; i < trainData.size(); ++i) {
        double dist = euclideanDistance(trainData[i], testData);
        distances.push_back({dist, trainLabels[i]});
    }
    
    // 按距离从小到大排序
    sort(distances.begin(), distances.end());
    
    // 投票决定类别
    vector<int> voteCount(10, 0);  // 假设标签的范围是0-9
    for (int i = 0; i < K; ++i) {
        voteCount[distances[i].second]++;
    }
    
    // 返回票数最多的类别
    return max_element(voteCount.begin(), voteCount.end()) - voteCount.begin();
}

查看全文

http://www.kler.cn/news/294070.html