C++ 深度优先搜索算法实现矩阵最大乘积之和

#include #include using namespace std;

int ans = -1; // 用于保存最大乘积之和的全局变量

// 深度优先搜索函数 void dfs(int i, vector<vector>& p, vector<vector>& q, vector& vis, vector& step) { int n = p.size();

// 如果搜索到达最后一层，则计算乘积之和并更新最大值
if (i == n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += p[i][step[i]] * q[step[i]][i];
    if (sum > ans)
        ans = sum;
    return;
}

// 遍历当前层次的所有可能选择
for (int j = 0; j < n; j++) {
    if (vis[j] == 0) { // 如果该选择未被访问过
        vis[j] = 1; // 标记该选择为已访问
        step[i] = j; // 保存该选择到步长数组中的第 i 个位置
        dfs(i + 1, p, q, vis, step); // 递归调用进行下一层次的搜索
        step[i] = 0; // 回溯时重置步长数组中的第 i 个位置为 0
        vis[j] = 0; // 取消对该选择的访问标记
    }
}

}

int main() { int n; cin >> n; // 读取矩阵的维度

// 创建大小为 n × n 的二维向量 p 和 q 作为输入矩阵
vector<vector<int>> p(n, vector<int>(n, 0));
vector<vector<int>> q(n, vector<int>(n, 0));

// 创建访问标记数组和步长数组，初始值为全 0
vector<int> vis(n, 0);
vector<int> step(n, 0);

// 读取矩阵 p 的元素值
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cin >> p[i][j];
    }
}

// 读取矩阵 q 的元素值
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cin >> q[i][j];
    }
}

// 调用深度优先搜索函数进行搜索
dfs(0, p, q, vis, step);

// 输出最大乘积之和
cout << ans << endl;

return 0;

} 流程图如下：

这段代码实现了一个深度优先搜索（DFS）算法，用于找到给定矩阵对 'p' 和 'q' 的最大乘积之和。

首先，代码读取输入的矩阵维度 'n'，然后创建了两个大小为 'n' × 'n' 的二维向量 'p' 和 'q' 作为输入矩阵。

接下来，定义了一个全局变量 'ans' 用于保存最大的乘积之和。

'dfs' 函数是核心函数，它采用递归的方式进行深度优先搜索。它的参数包括当前搜索的层次 'i'、矩阵 'p'、矩阵 'q'、访问标记数组 'vis' 和步长数组 'step'。

在 'dfs' 函数中，如果搜索到达最后一层（即 'i' 等于 'n'），则计算当前步长数组 'step' 对应的矩阵元素乘积之和，并与 'ans' 比较更新最大值。

否则，对于当前层次 'i'，遍历所有可能的选择（即 'j' 取值范围为 0 到 'n-1'），如果该选择未被访问过（即 'vis[j]' 等于 0），则将该选择标记为已访问（'vis[j]' 设为 1），将该选择保存到步长数组 'step' 的第 'i' 个位置，然后递归调用 'dfs' 函数进行下一层次的搜索。

在回溯时，需要将步长数组 'step' 的第 'i' 个位置重置为 0，同时取消对该选择的访问标记。

在 'main' 函数中，首先读取矩阵 'p' 的元素值，然后读取矩阵 'q' 的元素值。

接下来，调用 'dfs' 函数进行搜索，初始时层次 'i' 为 0，访问标记数组 'vis' 和步长数组 'step' 初始化为全 0。

最后，输出最大乘积之和 'ans'。