algorithm - 检查矩阵中元素邻居的最佳方法

Question

我有一个矩阵 M，其维度为 n x n。

我必须编写一个算法来返回一对 x,y 使得 Mx,y < min(Mx+1,y, Mx,y+1, Mx−1y, Mx,y−1).

您可以想到的第一个想法当然是获取每个元素，然后一个一个地检查邻居，看看这种关系是否真实。但是，从时间复杂度的角度来看，该算法必须是最优的。在这里我不确定如何优化。

有谁知道我可以搜索的算法的名称，或者可以提供一些关于如何优化该算法的指示？

我仔细考虑了一下，我认为也许可以分解此算法以找到矩阵中的最小值？那一定满足上面的关系吗？

Answer 1

您正在寻找局部最小值。通过从矩阵中的某个条目开始并转到具有较小值的相邻条目，可以很容易地找到它。

例如，如果您从 (x, y) 开始和 M[x+1, y] < M[x, y] , 然后继续 (x+1, y) .那么如果M[x+1, y-1] < M[x+1, y] , 然后继续 (x+1, y-1) .重复直到当前值是局部最小值，这意味着您不能再移动到相邻的较小值。