算法设计期末复习

文章目录

- - 1. 什么是算法，算法有哪些特征，算法设计的基本步骤，算法的时间复杂度的确定
  - 2. 什么是算法分析，算法分析的主要内容是什么？怎么确定算法的时间复杂度？
  - 3. 什么是分治算法，分治算法通常用哪些步骤来实现？常用什么数据结构和对应的算法
  - 4. 什么是蛮力法，有哪些应用，能解决什么问题，要写出对应策略、算法
  - 5. 什么是回溯法，有哪些应用，能解决什么问题，要写出对应策略、算法
  - 6. 什么是分枝限界法，有哪些应用，能解决什么问题，要写出对应策略、算法
  - 7. 分枝限界法和回溯的区别？
  - 8. 01背包问题的各种解决方案
  - 9. 最优装载问题方案及相关算法
  - 10. 最优活动安排方案及相关算法
  - 11. 动态规划问题的完成最短路径及路径长度
  - 12. 什么是概率算法、有哪些分类

1. 什么是算法，算法有哪些特征，算法设计的基本步骤，算法的时间复杂度的确定

什么是算法？
算法：求解问题的一系列计算步骤，用来将输入数据转换成输出结果。

算法的特征：

有穷性：算法必须在有限步骤内结束。
确定性：每一步骤都有明确的定义，不会产生歧义。
输入：算法有零个或多个输入。
输出：算法有一个或多个输出。
可行性：算法中的每一步骤都可以通过基本操作实现。

算法设计的基本步骤：

理解问题。
确定输入和输出。
设计解决问题的步骤。
验证算法的正确性。
分析算法的时间和空间复杂度。
优化算法（如果需要）。

算法的时间复杂度的确定：
时间复杂度是算法运行时间的增长率，通常用大O符号表示。它反映了算法执行时间随输入规模增长的变化趋势。例如：

常数时间：O(1)
线性时间：O(n)
对数时间：O(log n)
平方时间：O(n²)

2. 什么是算法分析，算法分析的主要内容是什么？怎么确定算法的时间复杂度？

什么是算法分析？
算法分析是对算法的时间复杂度、空间复杂度以及正确性进行评估的过程。

算法分析的主要内容：

时间复杂度：算法执行所需的时间。
空间复杂度：算法执行所需的内存空间。
正确性：算法是否能正确解决问题。
优化性：算法是否高效。

怎么确定算法的时间复杂度？

分析算法中每一步的基本操作次数。
找出最坏情况下的操作次数。
用大O符号表示时间复杂度。

例如，对于一个简单的循环：

for (int i = 0; i < n; i++) {
    cout << i << endl;
}

时间复杂度为O(n)。

3. 什么是分治算法，分治算法通常用哪些步骤来实现？常用什么数据结构和对应的算法

什么是分治算法？
分治算法是一种将问题分解为若干个子问题，分别解决后再合并结果的算法。

分治算法的步骤：

分解：将问题分解为若干个子问题。
解决：递归地解决子问题。
合并：将子问题的解合并为原问题的解。

常用的数据结构和算法：

归并排序：将数组分成两部分，分别排序后再合并。
快速排序：选择一个基准元素，将数组分为两部分，分别排序。
二分查找：在有序数组中查找元素。

4. 什么是蛮力法，有哪些应用，能解决什么问题，要写出对应策略、算法

什么是蛮力法？
蛮力法是一种直接解决问题的方法，通常通过穷举所有可能的解来找到答案。

应用：

排序（如选择排序、冒泡排序）。
查找（如线性查找）。
字符串匹配（如朴素字符串匹配算法）。

能解决的问题：

简单问题或规模较小的问题。
需要找到所有可能解的问题。

策略和算法：

选择排序：

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        swap(arr[i], arr[min_idx]);
    }
}

5. 什么是回溯法，有哪些应用，能解决什么问题，要写出对应策略、算法

什么是回溯法？
回溯法是一种通过尝试所有可能的解来解决问题的算法，当发现当前解不可行时，回退并尝试其他路径。

应用：

八皇后问题。
数独问题。
图的遍历。

能解决的问题：

组合优化问题。
路径搜索问题。

策略和算法：

八皇后问题：

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));
        backtrack(result, board, 0, n);
        return result;
    }

    void backtrack(vector<vector<string>>& result, vector<string>& board, int row, int n) {
        if (row == n) {
            result.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (is_safe(board, row, col, n)) {
                board[row][col] = 'Q';
                backtrack(result, board, row + 1, n);
                board[row][col] = '.';
            }
        }
    }

    bool is_safe(vector<string>& board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        return true;
    }
};

6. 什么是分枝限界法，有哪些应用，能解决什么问题，要写出对应策略、算法

什么是分枝限界法？
分枝限界法是一种通过剪枝来减少搜索空间的算法，通常用于解决组合优化问题。

应用：

旅行商问题。
0/1背包问题。
图的最短路径问题。

能解决的问题：

需要找到最优解的问题。
组合优化问题。

策略和算法：

0/1背包问题：

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Node {
    int level;
    int profit;
    int weight;
};

struct Item {
    int value;
    int weight;
};

int bound(Node node, int capacity, vector<Item>& items) {
    if (node.weight >= capacity) {
        return 0;
    }
    int profit_bound = node.profit;
    int j = node.level + 1;
    int totweight = node.weight;
    while (j < items.size() && totweight + items[j].weight <= capacity) {
        totweight += items[j].weight;
        profit_bound += items[j].value;
        j++;
    }
    if (j < items.size()) {
        profit_bound += (capacity - totweight) * items[j].value / items[j].weight;
    }
    return profit_bound;
}

int branch_and_bound(vector<Item>& items, int capacity) {
    queue<Node> q;
    Node root = {-1, 0, 0};
    q.push(root);
    int max_profit = 0;
    while (!q.empty()) {
        Node node = q.front();
        q.pop();
        if (node.level == items.size() - 1) {
            continue;
        }
        Node next_node = {node.level + 1, node.profit + items[node.level + 1].value, node.weight + items[node.level + 1].weight};
        if (next_node.weight <= capacity && next_node.profit > max_profit) {
            max_profit = next_node.profit;
        }
        if (bound(next_node, capacity, items) > max_profit) {
            q.push(next_node);
        }
        next_node = {node.level + 1, node.profit, node.weight};
        if (bound(next_node, capacity, items) > max_profit) {
            q.push(next_node);
        }
    }
    return max_profit;
}

7. 分枝限界法和回溯的区别？

回溯法：通过尝试所有可能的解来解决问题，当发现当前解不可行时，回退并尝试其他路径。
分枝限界法：通过剪枝来减少搜索空间，通常用于解决需要找到最优解的问题。

8. 01背包问题的各种解决方案

蛮力法：穷举所有可能的组合。
动态规划：

#include <vector>
#include <algorithm>
using namespace std;

int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; 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][capacity];
}

9. 最优装载问题方案及相关算法

贪心算法：

#include <vector>
#include <algorithm>
using namespace std;

int optimal_loading(vector<int>& weights, int capacity) {
    sort(weights.begin(), weights.end());
    int total_weight = 0;
    int count = 0;
    for (int weight : weights) {
        if (total_weight + weight <= capacity) {
            total_weight += weight;
            count++;
        }
    }
    return count;
}

10. 最优活动安排方案及相关算法

贪心算法：

#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> activity_selection(vector<int>& start, vector<int>& finish) {
    vector<pair<int, int>> activities;
    for (int i = 0; i < start.size(); i++) {
        activities.push_back({start[i], finish[i]});
    }
    sort(activities.begin(), activities.end(), [](pair<int, int>& a, pair<int, int>& b) {
        return a.second < b.second;
    });
    vector<pair<int, int>> selected = {activities[0]};
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].first >= selected.back().second) {
            selected.push_back(activities[i]);
        }
    }
    return selected;
}

11. 动态规划问题的完成最短路径及路径长度

Floyd-Warshall算法：

#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> floyd_warshall(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> dist = graph;
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    return dist;
}