在单元格不能相邻的正方形网格中查找单元格的最大总和
Finding the max sum of cells in a square grid where cells cannot be adjacent
我正在尝试寻找一种算法来查找 n 大小的正方形网格中非相邻（相邻为 horizontal/vertical 元素）元素的最大总和。
我试过将网格转换成流程图并计算最大流量，但运气不佳。有解决这个问题的算法吗？如果没有，我们将如何制作一个？
有一个算法可以有效地解决这个问题，使用 max-flow min-cut 定理。这涉及对您的问题进行一系列转换——您可能想自己验证为什么每个转换都有效。
首先，让我们先了解一下 positive/negative 数字技术细节。如果你的最大总和允许为空，那么它的最小值可以是 0。如果网格中至少有一个正数，我们永远不必将负数计入我们的总和，因此我们可以完全忽略这些单元格.
但是，如果你的最大和不能为空，而且所有的数都是负数，那么取格子中的单个最大数作为最佳和。
你有一个二维的'grid graph'：每个单元格对应一个顶点，当且仅当它们的单元格水平或垂直相邻时，顶点才相邻。
这是一个二分图（就像棋盘一样）：如果您对行和列进行编号，则单元格 (x, y) 与 (x+1, y)、(x-1, y)、[=13 相邻=]，以及 (x, y-1)。查看 x+y 的奇偶性，一个单元格仅与坐标总和为相反奇偶性的单元格相邻。
现在，您正在寻找此二分图中的最大加权独立集。查找的算法已经完全展开in this SO post, and also in this CS StackExchange post with references，所以我不会在这里重复所有相同的细节第三次。
相反，这里是问题转换的大纲，顺序为：
方形网格中不相邻单元格的最大总和S
二部图中最大加权独立顶点集G
G
中的最小加权顶点覆盖
流图中的最小权重切割 F，其中 F 具有与 G 相同的顶点加上源和汇点顶点
F 中从源到汇的最大流量
在删除所有负单元格并找到最大流量后，您的最大总和问题的答案是：(Sum of all cells) - (Max flow in F)。
我正在尝试寻找一种算法来查找 n 大小的正方形网格中非相邻（相邻为 horizontal/vertical 元素）元素的最大总和。 我试过将网格转换成流程图并计算最大流量，但运气不佳。有解决这个问题的算法吗？如果没有，我们将如何制作一个？
有一个算法可以有效地解决这个问题，使用 max-flow min-cut 定理。这涉及对您的问题进行一系列转换——您可能想自己验证为什么每个转换都有效。
首先，让我们先了解一下 positive/negative 数字技术细节。如果你的最大总和允许为空，那么它的最小值可以是 0。如果网格中至少有一个正数，我们永远不必将负数计入我们的总和，因此我们可以完全忽略这些单元格.
但是，如果你的最大和不能为空，而且所有的数都是负数，那么取格子中的单个最大数作为最佳和。
你有一个二维的'grid graph'：每个单元格对应一个顶点，当且仅当它们的单元格水平或垂直相邻时，顶点才相邻。
这是一个二分图（就像棋盘一样）：如果您对行和列进行编号，则单元格 (x, y) 与 (x+1, y)、(x-1, y)、[=13 相邻=]，以及 (x, y-1)。查看 x+y 的奇偶性，一个单元格仅与坐标总和为相反奇偶性的单元格相邻。
现在，您正在寻找此二分图中的最大加权独立集。查找的算法已经完全展开in this SO post, and also in this CS StackExchange post with references，所以我不会在这里重复所有相同的细节第三次。
相反，这里是问题转换的大纲，顺序为：
方形网格中不相邻单元格的最大总和
S二部图中最大加权独立顶点集
G
中的最小加权顶点覆盖G流图中的最小权重切割
F，其中F具有与G相同的顶点加上源和汇点顶点F中从源到汇的最大流量
在删除所有负单元格并找到最大流量后，您的最大总和问题的答案是：(Sum of all cells) - (Max flow in F)。