梧席
Algorithm Description
Q7nl1s admin
  2024-06-09 22:16:59 2024-06-09 22:16   2024-08-08 20:53:14      6.9k Words  

EN

4.1 Iterative Algorithm

Definition: An iterative algorithm approaches the solution to a problem by repeatedly executing a segment of code.

Explanation: The key to an iterative algorithm is the repeated execution of a specific step until a condition is met. You can think of it like brushing your teeth every morning—you keep brushing until all your teeth are clean.

Applications: Calculating factorials, summing numbers, traversing arrays, etc.

Example: Calculating Factorial

Approach:

  1. Use a loop to gradually calculate the product for the factorial.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

// Calculate the factorial of n
unsigned long long factorial(int n) {
    unsigned long long result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i; // Multiply by each number gradually
    }
    return result; // Return the result
}

int main() {
    int n = 5; // The number for which to calculate the factorial
    printf("Factorial of %d is %llu\n", n, factorial(n)); // Print the result
    return 0;
}

4.2 Brute Force Method

Definition: The brute force method tries all possible solutions until it finds one that satisfies the conditions.

Explanation: The brute force method is straightforward and simple, where you try every possible answer and then find the correct one. It’s like finding the right key to open a door from a bunch of keys—you try each key one by one until you find the right one.

Applications: Finding the maximum value in an array, password cracking, combination problems, etc.

Example: Finding the Maximum Value in an Array

Approach:

  1. Compare each element in the array one by one and keep track of the maximum value.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

// Find the maximum value in an array
int findMax(int arr[], int size) {
    int max = arr[0]; // Assume the first element is the maximum
    for (int i = 1; i < size; ++i) {
        if (arr[i] > max) {
            max = arr[i]; // Update the maximum value
        }
    }
    return max; // Return the maximum value
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0}; // Example array
    int size = sizeof(arr) / sizeof(arr[0]); // Array size
    printf("Maximum value is %d\n", findMax(arr, size)); // Print the maximum value
    return 0;
}

4.3 Divide and Conquer Algorithm

Definition: The divide and conquer algorithm divides a problem into multiple subproblems, solves each subproblem independently, and then combines the solutions to the subproblems to obtain the solution to the original problem.

Explanation: The core idea of the divide and conquer algorithm is to break down a big problem into smaller problems and solve them individually, like when you clean a room by dividing it into several areas and cleaning each one by one. Eventually, the entire room is clean.

Applications: Merge sort, quick sort, binary search, etc.

Example: Merge Sort

Approach:

  1. Divide the array into two halves.
  2. Recursively apply merge sort to each half.
  3. Merge the two sorted halves.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <stdlib.h>

// Merge two sorted subarrays
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temporary arrays
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Merge the temporary arrays back into the original array
    i = 0; // Initial index of left subarray
    j = 0; // Initial index of right subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Merge sort
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // Calculate the middle point

        mergeSort(arr, l, m); // Recursively sort the left half
        mergeSort(arr, m + 1, r); // Recursively sort the right half

        merge(arr, l, m, r); // Merge the two halves
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7}; // Example array
    int arr_size = sizeof(arr) / sizeof(arr[0]); // Array size

    printf("Given array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    mergeSort(arr, 0, arr_size - 1); // Call merge sort

    printf("\nSorted array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

4.4 Greedy Algorithm

Definition: A greedy algorithm makes the locally optimal choice at each step with the hope of finding the global optimum.

Explanation: The strategy of a greedy algorithm is to make the best choice at each step, like when you are walking through a maze and always choose the path that looks closest to the exit. This doesn’t always guarantee the shortest path, but it may lead you to the exit faster.

Applications: Activity selection problem, knapsack problem, minimum spanning tree (Prim’s and Kruskal’s algorithms), etc.

Example: Activity Selection Problem

Approach:

  1. Sort all activities by their end time.
  2. Select the first activity, then select the next activity that starts after the current one ends.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>

typedef struct {
    int start;
    int end;
} Activity;

// Select activities
void activitySelection(Activity activities[], int n) {
    int i, j;

    printf("Selected activities are:\n");

    i = 0; // The first activity is always selected
    printf("(%d, %d) ", activities[i].start, activities[i].end);

    // Select other activities
    for (j = 1; j < n; j++) {
        if (activities[j].start >= activities[i].end) {
            printf("(%d, %d) ", activities[j].start, activities[j].end);
            i = j; // Update the last selected activity
        }
    }
    printf("\n");
}

int main() {
    Activity activities[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}}; // Array of activities
    int n = sizeof(activities) / sizeof(activities[0]); // Number of activities

    activitySelection(activities, n); // Call the activity selection algorithm
    return 0;
}

4.5 Dynamic Programming

Definition: Dynamic programming decomposes a problem into smaller subproblems and uses the solutions to the subproblems to construct the solution to the original problem. It typically avoids recomputation by storing the results of already solved subproblems.

Explanation: The idea behind dynamic programming is to break down a big problem into many smaller problems and save the solution to each subproblem, so each small problem is solved only once. It’s like building a house where each room’s construction plan is recorded, so when you build a similar room later, you don’t have to design it from scratch.

Applications: Fibonacci sequence, longest common subsequence, knapsack problem, etc.

Example: Fibonacci Sequence

Approach:

  1. Break the problem into computing the sum of the two preceding Fibonacci numbers.
  2. Use an array to store already computed Fibonacci numbers to avoid recomputation.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>

// Calculate Fibonacci sequence
unsigned long long fibonacci(int n) {
    if (n <= 1)
        return n;

    unsigned long long fib[n + 1]; // Create storage array
    fib[0] = 0;
    fib[1] = 1;

    // Compute the Fibonacci sequence
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return

 fib[n]; // Return the result
}

int main() {
    int n = 10; // Position in the Fibonacci sequence to compute
    printf("Fibonacci number at position %d is %llu\n", n, fibonacci(n)); // Print the result
    return 0;
}

4.6 Comparison of Algorithm Strategies

Comparison:

  • Iterative Algorithm: Simple and straightforward, suitable for simple repetitive problems but may not be efficient.
  • Brute Force Method: Simple to understand but inefficient, suitable for small-scale problems.
  • Divide and Conquer Algorithm: Solves problems by breaking them down into subproblems, suitable for problems with recursive nature and efficient.
  • Greedy Algorithm: Makes locally optimal choices, suitable for specific problems but does not guarantee global optimality.
  • Dynamic Programming: Suitable for problems with overlapping subproblems and optimal substructure, efficient but requires more storage space.

Iterative Algorithm vs Brute Force Method: The iterative algorithm focuses more on repeated calculations, while the brute force method tries all possible solutions.

Divide and Conquer Algorithm vs Dynamic Programming: The divide and conquer algorithm solves subproblems independently, while dynamic programming records solutions to avoid recomputation. Divide and conquer is suitable for problems with non-overlapping subproblems, while dynamic programming is suitable for problems with overlapping subproblems.

Greedy Algorithm vs Dynamic Programming: The greedy algorithm makes locally optimal choices at each step, while dynamic programming considers the overall problem to guarantee global optimality.

Graph search algorithms are used to traverse or search nodes in a graph. They are mainly divided into Depth-First Search (DFS) and Breadth-First Search (BFS).

5.2 Breadth-First Search (BFS)

Definition: Starts from the initial node and visits nodes layer by layer until the target node is found or all nodes are traversed.

Explanation: BFS is like searching tree nodes level by level, starting from the root. It ensures that all nodes in each layer are visited before moving on to the next layer.

Applications: Shortest path finding, social network friend recommendations, level-order traversal, etc.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Queue structure
typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

// Create a queue
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// Check if the queue is empty
int isEmpty(Queue* q) {
    return q->rear == -1;
}

// Enqueue
void enqueue(Queue* q, int value) {
    if (q->rear == MAX - 1)
        return;
    if (q->front == -1)
        q->front = 0;
    q->items[++q->rear] = value;
}

// Dequeue
int dequeue(Queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        item = q->items[q->front];
        if (q->front >= q->rear) {
            q->front = -1;
            q->rear = -1;
        } else {
            q->front++;
        }
        return item;
    }
}

// Breadth-First Search
void bfs(int graph[][MAX], int startVertex, int numVertices) {
    Queue* q = createQueue();
    int visited[MAX] = {0}; // Initialize the visited array

    printf("BFS traversal starting from vertex %d: ", startVertex);
    visited[startVertex] = 1; // Mark the starting node as visited
    enqueue(q, startVertex);

    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("%d ", currentVertex);

        // Visit all adjacent nodes
        for (int i = 0; i < numVertices; i++) {
            if (graph[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(q, i);
            }
        }
    }
    printf("\n");
}

int main() {
    int numVertices = 6;
    int graph[MAX][MAX] = {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 0, 1, 1, 0},
        {1, 0, 0, 0, 1, 1},
        {0, 1, 0, 0, 0, 0},
        {0, 1, 1, 0, 0, 0},
        {0, 0, 1, 0, 0, 0}
    };

    bfs(graph, 0, numVertices); // Call breadth-first search
    return 0;
}

5.3 Depth-First Search (DFS)

Definition: Starts from the initial node and visits nodes as deeply as possible along each branch until the target node is found or all nodes are traversed.

Explanation: DFS is like starting from the root of a tree and going down as far as possible, then backtracking to the previous node to continue. It’s similar to exploring one direction deeply and backtracking when a dead end is encountered.

Applications: Topological sorting, connectivity checking in graphs, maze solving, etc.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Depth-First Search
void dfs(int graph[][MAX], int vertex, int visited[], int numVertices) {
    visited[vertex] = 1; // Mark the current node as visited
    printf("%d ", vertex);

    // Visit all adjacent nodes
    for (int i = 0; i < numVertices; i++) {
        if (graph[vertex][i] == 1 && !visited[i]) {
            dfs(graph, i, visited, numVertices);
        }
    }
}

int main() {
    int numVertices = 6;
    int graph[MAX][MAX] = {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 0, 1, 1, 0},
        {1, 0, 0, 0, 1, 1},
        {0, 1, 0, 0, 0, 0},
        {0, 1, 1, 0, 0, 0},
        {0, 0, 1, 0, 0, 0}
    };

    int visited[MAX] = {0}; // Initialize the visited array
    printf("DFS traversal starting from vertex 0: ");
    dfs(graph, 0, visited, numVertices); // Call depth-first search
    printf("\n");
    return 0;
}

5.4 Backtracking

Definition: Backtracking is a methodical way of searching through a problem’s solution space by recursively building a solution and abandoning it if it doesn’t meet the problem’s requirements.

Explanation: Backtracking is like navigating a maze—when you hit a dead end, you backtrack to the previous junction and try a different path until you find the exit or determine there is no viable path.

Applications: N-Queens problem, Sudoku solving, generating combinations, etc.

Example: N-Queens Problem

Approach:

  1. Place a queen on the board, trying each column and ensuring no conflicts.
  2. If placing a queen is not possible at a certain step, backtrack to the previous step and try a different position.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <stdio.h>
#define N 8

// Print the board
void printSolution(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf(" %d ", board[i][j]);
        printf("\n");
    }
}

// Check if the current position is safe
int isSafe(int board[N][N], int row, int col) {
    int i, j;

    // Check the current column
    for (i = 0; i < col; i++)
        if (board[row][i])
            return 0;

    // Check the upper diagonal on the left side
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return 0;

    // Check the lower diagonal on the left side
    for (i = row, j = col; j >= 0 && i < N; i++, j--)
        if (board[i][j])
            return 0;

    return 1;
}

// Recursive utility to solve N-Queens problem
int solveNQUtil(int board[N][N], int col) {
    if (col >= N)
        return 1;

    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col)) {
            board[i][col] = 1;

            if (solveNQUtil(board, col + 1))
                return 1;

            board[i][col] = 0; // Backtrack
        }
    }

    return 0;
}

// Solve N-Queens problem


void solveNQ() {
    int board[N][N] = { { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 } };

    if (solveNQUtil(board, 0) == 0) {
        printf("Solution does not exist");
        return;
    }

    printSolution(board); // Print the result
}

int main() {
    solveNQ(); // Call the N-Queens solution
    return 0;
}

5.5 Branch and Bound

Definition: Branch and bound is an optimization search algorithm that improves search efficiency by limiting and pruning the search space of impossible or suboptimal solutions.

Explanation: Branch and bound is like searching through options with some conditions to rule out impossible paths early, avoiding inefficient searches. It’s like filtering out products based on budget and requirements when shopping.

Applications: Traveling salesman problem, 0/1 knapsack problem, maximum clique problem in graphs, etc.

Example: 0/1 Knapsack Problem

Approach:

  1. For each item, consider two cases: including the item in the knapsack and excluding it.
  2. Use a bound function (like remaining capacity, current value) to prune impossible solutions.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>

// Define a structure to represent items
typedef struct {
    int weight; // Item weight
    int value;  // Item value
} Item;

// Return the larger of two numbers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Dynamic programming solution to the 0/1 knapsack problem
int knapsack(Item items[], int n, int W) {
    // Create a one-dimensional array to store the maximum value for different capacities
    int dp[W + 1];
    // Initialize the array with all zeros
    for (int i = 0; i <= W; i++)
        dp[i] = 0;

    // Iterate through each item
    for (int i = 0; i < n; i++) {
        // Iterate through the knapsack capacity from W down to the item's weight
        for (int w = W; w >= items[i].weight; w--) {
            // Update the dp array by taking the maximum value between including the current item and not including it
            dp[w] = max(dp[w], dp[w - items[i].weight] + items[i].value);
        }
    }
    // Return the maximum value for the knapsack with capacity W
    return dp[W];
}

int main() {
    // Define an array of items with their weights and values
    Item items[] = {{2, 3}, {3, 4}, {4, 5}, {5, 6}};
    // Knapsack capacity
    int W = 5;
    // Number of items
    int n = sizeof(items) / sizeof(items[0]);
    // Calculate and print the maximum value for the knapsack with capacity W
    printf("Maximum value in Knapsack = %d\n", knapsack(items, n, W));
    return 0;
}

CN

4.1 迭代算法

定义: 迭代算法通过重复执行一段代码，逐步逼近问题的解。

解释: 迭代算法的关键在于重复执行某个步骤，直到满足某个条件。你可以把它想象成每天早上刷牙的过程，你反复刷牙，直到所有的牙齿都干净为止。

应用: 计算阶乘、求和、遍历数组等。

案例: 计算阶乘

思路:

  1. 使用一个循环逐步计算阶乘的乘积。

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

// 计算n的阶乘
unsigned long long factorial(int n) {
    unsigned long long result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i; // 逐步乘以每个数
    }
    return result; // 返回结果
}

int main() {
    int n = 5; // 要计算阶乘的数
    printf("Factorial of %d is %llu\n", n, factorial(n)); // 打印结果
    return 0;
}

4.2 蛮力法

定义: 蛮力法通过尝试所有可能的解决方案，直到找到一个满足条件的解。

解释: 蛮力法的思路是简单粗暴的，就是把所有可能的答案都试一遍，然后找出正确的那个。就像在一堆钥匙中找到一把可以开门的钥匙，你会一个一个地尝试，直到找到那把正确的钥匙。

应用: 求数组中的最大值、密码破解、组合问题等。

案例: 求数组中的最大值

思路:

  1. 逐个比较数组中的每个元素，记录最大值。

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

// 找到数组中的最大值
int findMax(int arr[], int size) {
    int max = arr[0]; // 假设第一个元素为最大值
    for (int i = 1; i < size; ++i) {
        if (arr[i] > max) {
            max = arr[i]; // 更新最大值
        }
    }
    return max; // 返回最大值
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0}; // 示例数组
    int size = sizeof(arr) / sizeof(arr[0]); // 数组大小
    printf("Maximum value is %d\n", findMax(arr, size)); // 打印最大值
    return 0;
}

4.3 分治算法

定义: 分治算法将一个问题分成多个子问题分别解决，然后合并子问题的解得到原问题的解。

解释: 分治算法的核心思想是把大问题分解成小问题来解决，就像你在清理房间时，把房间分成几个区域，一个一个区域地清理，最后整个房间就干净了。

应用: 归并排序、快速排序、二分搜索等。

案例: 归并排序

思路:

  1. 将数组分成两半。
  2. 递归地对每一半进行归并排序。
  3. 合并两个有序的子数组。

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <stdlib.h>

// 合并两个有序子数组
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // 创建临时数组
    int L[n1], R[n2];

    // 拷贝数据到临时数组
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // 合并临时数组到原数组
    i = 0; // 初始化左边子数组的初始索引
    j = 0; // 初始化右边子数组的初始索引
    k = l; // 初始化合并子数组的初始索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 拷贝剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // 计算中间点

        mergeSort(arr, l, m); // 递归排序左半部分
        mergeSort(arr, m + 1, r); // 递归排序右半部分

        merge(arr, l, m, r); // 合并两半
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7}; // 示例数组
    int arr_size = sizeof(arr) / sizeof(arr[0]); // 数组大小

    printf("Given array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    mergeSort(arr, 0, arr_size - 1); // 调用归并排序

    printf("\nSorted array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

4.4 贪婪算法

定义: 贪婪算法在每一步选择中都采取当前最优解，以期最终能得到全局最优解。

解释: 贪婪算法的策略是每一步都选择当前看起来最好的那个选项，就像你在走迷宫时，每次都选择看起来最近的出口路径，虽然这不一定能保证你找到最短的路，但可能会更快找到出口。

应用: 活动选择问题、背包问题、最小生成树（Prim和Kruskal算法）等。

案例: 活动选择问题

思路:

  1. 将所有活动按照结束时间排序。
  2. 从第一个活动开始选择，每次选择结束时间最早且不与已选择活动冲突的活动。

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>

typedef struct {
    int start;
    int end;
} Activity;

// 选择活动
void activitySelection(Activity activities[], int n) {
    int i, j;

    printf("Selected activities are:\n");

    i = 0; // 第一个活动总是被选择
    printf("(%d, %d) ", activities[i].start, activities[i].end);

    // 选择其他活动
    for (j = 1; j < n; j++) {
        if (activities[j].start >= activities[i].end) {
            printf("(%d, %d) ", activities[j].start, activities[j].end);
            i = j; // 更新最后选择的活动
        }
    }
    printf("\n");
}

int main() {
    Activity activities[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}}; // 活动数组
    int n = sizeof(activities) / sizeof(activities[0]); // 活动数量

    activitySelection(activities, n); // 调用活动选择算法
    return 0;
}

4.5 动态规划

定义: 动态规划通过将问题分解为更小的子问题，并利用子问题的解来构建原问题的解。通常通过记录已解决的子问题的解来避免重复计算。

解释: 动态规划的思路是把一个大问题拆分成许多小问题，并保存每个小问题的解，这样相同的小问题只解决一次，就像在盖房子时，每个房间的建造方案都记录下来，后面盖类似房间时就不用重新设计了。

应用: 斐波那契数列、最长公共子序列、背包问题等。

案例: 斐波那契数列

思路:

  1. 将问题分解为计算前两个斐波那契数的和。
  2. 使用数组存储已经计算的斐波那契数以避免重复计算。

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>

// 计算斐波那契数列
unsigned long long fibonacci(int n) {
    if (n <= 1)
        return n;

    unsigned long long fib[n + 1]; // 创建存储数组
    fib[0] = 0;
    fib[1] = 1;

    // 计算斐波那契数列
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n]; // 返回结果
}

int main() {
    int n = 10; // 要计算的斐波那契数列位置
    printf("Fibonacci number at position %d is %llu\n", n, fibonacci(n)); // 打印结果
    return 0;
}

4.6 算法策略间的比较

比较:

  • 迭代算法: 简单直接，适用于简单重复的问题，但可能效率不高。
  • 蛮力法: 简单易懂，但效率低下，适用于小规模问题。
  • 分治算法: 通过递归分解问题，适用于具有递归性质的问题，效率较高。
  • 贪婪算法: 每一步选择局部最优解，适用于某些特殊问题，但不保证全局最优。
  • 动态规划: 适用于具有重叠子问题和最优子结构的问题，效率高，但需要较多的存储空间。

迭代算法 vs 蛮力法: 迭代算法更注重重复计算，而蛮力法则是尝试所有可能的解决方案。

分治算法 vs 动态规划: 分治算法分解问题并独立解决，动态规划则分解问题并记录解以避免重复计算。分治适合不重叠子问题，动态规划适合重叠子问题。

贪婪算法 vs 动态规划: 贪婪算法每一步都选当前最优，动态规划则整体考虑，保证全局最优。

5.1 图搜索概述

图搜索算法用于遍历或搜索图中的节点。主要分为深度优先搜索（DFS）和广度优先搜索（BFS）。

5.2 广度优先搜索 (BFS)

定义: 从起始节点开始，逐层访问节点，直到找到目标节点或遍历完所有节点。

解释: BFS就像从树根开始逐层找树上的节点，先找离根最近的一层，再找下一层。类似于一圈一圈地向外扩展，确保每层的节点都被访问到。

应用: 最短路径查找、社交网络好友推荐、层次遍历等。

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// 队列结构
typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

// 创建队列
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// 检查队列是否为空
int isEmpty(Queue* q) {
    return q->rear == -1;
}

// 入队
void enqueue(Queue* q, int value) {
    if (q->rear == MAX - 1)
        return;
    if (q->front == -1)
        q->front = 0;
    q->items[++q->rear] = value;
}

// 出队
int dequeue(Queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        item = q->items[q->front];
        if (q->front >= q->rear) {
            q->front = -1;
            q->rear = -1;
        } else {
            q->front++;
        }
        return item;
    }
}

// 广度优先搜索
void bfs(int graph[][MAX], int startVertex, int numVertices) {
    Queue* q = createQueue();
    int visited[MAX] = {0}; // 初始化访问数组

    printf("BFS traversal starting from vertex %d: ", startVertex);
    visited[startVertex] = 1; // 标记起始节点已访问
    enqueue(q, startVertex);

    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("%d ", currentVertex);

        // 访问所有邻接节点
        for (int i = 0; i < numVertices; i++) {
            if (graph[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(q, i);
            }
        }
    }
    printf("\n");
}

int main() {
    int numVertices = 6;
    int graph[MAX][MAX] = {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 0, 1, 1, 0},
        {1, 0, 0, 0, 1, 1},
        {0, 1, 0, 0, 0, 0},
        {0, 1, 1, 0, 0, 0},
        {0, 0, 1, 0, 0, 0}
    };

    bfs(graph, 0, numVertices); // 调用广度优先搜索
    return 0;
}

5.3 深度优先搜索 (DFS)

定义: 从起始节点开始，沿着每一个分支尽可能深入地访问节点，直到找到目标节点或遍历完所有节点。

解释: DFS就像从树根开始一直往下走，直到走不通了才回退到上一个节点再继续，类似于深入探索一个方向，遇到死胡同再回头。

应用: 拓扑排序、图的连通性检测、迷宫求解等。

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// 深度优先搜索
void dfs(int graph[][MAX], int vertex, int visited[], int numVertices) {
    visited[vertex] = 1; // 标记当前节点已访问
    printf("%d ", vertex);

    // 访问所有邻接节点
    for (int i = 0; i < numVertices; i++) {
        if (graph[vertex][i] == 1 && !visited[i]) {
            dfs(graph, i, visited, numVertices);
        }
    }
}

int main() {
    int numVertices = 6;
    int graph[MAX][MAX] = {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 0, 1, 1, 0},
        {1, 0, 0, 0, 1, 1},
        {0, 1, 0, 0, 0, 0},
        {0, 1, 1, 0, 0, 0},
        {0, 0, 1, 0, 0, 0}
    };

    int visited[MAX] = {0}; // 初始化访问数组
    printf("DFS traversal starting from vertex 0: ");
    dfs(graph, 0, visited, numVertices); // 调用深度优先搜索
    printf("\n");
    return 0;
}

5.4 回溯法

定义: 回溯法是一种系统地搜索问题解空间的算法，通过递归地构建解，遇到不满足条件的解时回溯到上一步重新选择。

解释: 回溯法就像走迷宫时，遇到死路就退回到上一个岔路口，再尝试另一条路，直到找到出口或确定没有可行的路。

应用: 八皇后问题、数独求解、组合数生成等。

案例: 八皇后问题

思路:

  1. 在棋盘上放置皇后，尝试每一列，如果不冲突，则递归放置下一行的皇后。
  2. 如果某一步无法放置皇后，则回溯到上一步重新选择。

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#define N 8

// 打印棋盘
void printSolution(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf(" %d ", board[i][j]);
        printf("\n");
    }
}

// 检查当前点是否安全
int isSafe(int board[N][N], int row, int col) {
    int i, j;

    // 检查当前列
    for (i = 0; i < col; i++)
        if (board[row][i])
            return 0;

    // 检查左上对角线
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return 0;

    // 检查左下对角线
    for (i = row, j = col; j >= 0 && i < N; i++, j--)
        if (board[i][j])
            return 0;

    return 1;
}

// 递归解决N皇后问题
int solveNQUtil(int board[N][N], int col) {
    if (col >= N)
        return 1;

    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col)) {
            board[i][col] = 1;

            if (solveNQUtil(board, col + 1))
                return 1;

            board[i][col] = 0; // 回溯
        }
    }

    return 0;
}

// 解决N皇后问题
void solveNQ() {
    int board[N][N] = { { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 0 } };

    if (solveNQUtil(board, 0) == 0) {
        printf("Solution does not exist");
        return;
    }

    printSolution(board); // 打印结果
}

int main() {
    solveNQ(); // 调用N皇后问题解决方案
    return 0;
}

5.5 分枝限界法

定义: 分枝限界法是一种优化搜索算法，通过限制和剪枝不可能或不优的解空间来提高搜索效率。

解释: 分枝限界法就像在搜索过程中，通过一些条件提前排除不可能的路径，避免无效的搜索，就像你在挑选商品时，根据预算和需求提前过滤掉不符合条件的商品。

应用: 旅行商问题、0/1 背包问题、图的最大团问题等。

案例: 0/1 背包问题

思路:

  1. 对每个物品，考虑两种情况：放入背包和不放入背包。
  2. 使用限界函数（如剩余容量、当前价值）剪枝不可能的解。

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>

// 定义一个结构体来表示物品
typedef struct {
    int weight; // 物品重量
    int value;  // 物品价值
} Item;

// 返回两个数中较大的一个
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 动态规划解决0/1背包问题
int knapsack(Item items[], int n, int W) {
    // 创建一个一维数组来存储背包在不同容量下的最大价值
    int dp[W + 1];
    // 初始化数组，所有值都为0
    for (int i = 0; i <= W; i++)
        dp[i] = 0;

    // 遍历每个物品
    for (int i = 0; i < n; i++) {
        // 从背包容量W开始，逐渐减小
        for (int w = W; w >= items[i].weight; w--) {
            // 更新dp数组，取放入当前物品后的价值和不放入当前物品的价值的最大值
            dp[w] = max(dp[w], dp[w - items[i].weight] + items[i].value);
        }
    }
    // 返回容量为W的背包能装下的最大价值
    return dp[W];
}

int main() {
    // 定义物品数组，每个物品有重量和价值
    Item items[] = {{2, 3}, {3, 4}, {4, 5}, {5, 6}};
    // 背包的容量
    int W = 5;
    // 物品的数量
    int n = sizeof(items) / sizeof(items[0]);
    // 计算并打印在背包容量为W的情况下能装下的最大价值
    printf("Maximum value in Knapsack = %d\n", knapsack(items, n, W));
    return 0;
}
 Comments
Comment plugin failed to load
Loading comment plugin
  1. EN
    1. 4.1 Iterative Algorithm
    2. 4.2 Brute Force Method
    3. 4.3 Divide and Conquer Algorithm
    4. 4.4 Greedy Algorithm
    5. 4.5 Dynamic Programming
    6. 4.6 Comparison of Algorithm Strategies
    7. 5.1 Overview of Graph Search
    8. 5.2 Breadth-First Search (BFS)
    9. 5.3 Depth-First Search (DFS)
    10. 5.4 Backtracking
    11. 5.5 Branch and Bound
  • CN
    1. 4.1 迭代算法
    2. 4.2 蛮力法
    3. 4.3 分治算法
    4. 4.4 贪婪算法
    5. 4.5 动态规划
    6. 4.6 算法策略间的比较
    7. 5.1 图搜索概述
    8. 5.2 广度优先搜索 (BFS)
    9. 5.3 深度优先搜索 (DFS)
    10. 5.4 回溯法
    11. 5.5 分枝限界法
    • © 2020 - 2024    Q7nl1s
    Powered by Hexo & Theme Keep
    Unique Visitor Page View
    1. EN
      1. 4.1 Iterative Algorithm
      2. 4.2 Brute Force Method
      3. 4.3 Divide and Conquer Algorithm
      4. 4.4 Greedy Algorithm
      5. 4.5 Dynamic Programming
      6. 4.6 Comparison of Algorithm Strategies
      7. 5.1 Overview of Graph Search
      8. 5.2 Breadth-First Search (BFS)
      9. 5.3 Depth-First Search (DFS)
      10. 5.4 Backtracking
      11. 5.5 Branch and Bound
  • CN
    1. 4.1 迭代算法
    2. 4.2 蛮力法
    3. 4.3 分治算法
    4. 4.4 贪婪算法
    5. 4.5 动态规划
    6. 4.6 算法策略间的比较
    7. 5.1 图搜索概述
    8. 5.2 广度优先搜索 (BFS)
    9. 5.3 深度优先搜索 (DFS)
    10. 5.4 回溯法
    11. 5.5 分枝限界法