在矩阵上找到波中心的最佳算法是什么？

Question

考虑到我有一个像这样的矩阵(mXn):

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 | 1 | 0 | 0 | 0 | 0 | 0
0 | 1 | 1 | 2 | 1 | 1 | 0 | 0 | 0
0 | 1 | 4 | 9 | 4 | 1 | 0 | 0 | 0
1 | 2 | 9 | # | 9 | 2 | 1 | 0 | 0
0 | 1 | 4 | 9 | 4 | 1 | 0 | 0 | 0
0 | 1 | 1 | 2 | 1 | 1 | 0 | 0 | 0
0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0

哪里有#随机设置的点.靠近它的值以波的形式受到影响.距离该点越近,值越接近10.

#假设它将在更大的尺度上使用,哪种算法可以很好地发现？

编辑:我更感兴趣的是如何找到第一个非零数字,而不是找到#它自己,这是目的,但不是真正的问题.想象一个充满零的巨大矩阵和#隐藏的某个地方.该算法的详尽部分是找到第一个非零值.

Answer 1

找到第一个非零值仅在信号对称且不包含旋转时才有效.考虑从Internet借来的以下示例(零=蓝色,最大=红色),注意第一个非零值位于右上角:

http://www.mathworks.com/matlabcentral/fileexchange/screenshots/1134/original.jpg

您可能想要了解渐变下降.通用算法是为连续函数定义的(您的是离散的),但您仍然可以使用它.

它基本上在矩阵的某处初始化,在该点寻找渐变并向该方向移动,然后重复直到它收敛.您可以通过随机采样来初始化它(选择一个随机单元格直到达到非零值,您可以预期这比遍历更快并且平均找到非零值,自然取决于您的矩阵和信号大小)

一些属性:

• 通常比穷举搜索更快(迭代整个矩阵)
• 搜索空间越大(矩阵),与穷举搜索相比就越快.
• 即使信号不对称且居中(首先非零与最大值对齐),您仍然可以处理更复杂的信号!
• 同样的方法可以用于1维信号或缩放到n维(如果你考虑它,这是很酷的,也非常有用:])

限制:

• 它可以永远振荡而不会收敛到某个值,特别是在离散函数上,您需要在代码中处理这种情况.
• 您不能保证找到全局最大值(可以在本地捕获,有解决此问题的方法)
• 你需要插入你的函数(不是全部,只是几个单元格,不是一件困难的事情,我不会使用线性插值)或对算法进行一些调整(计算离散函数中的梯度而不是连续函数)一,不难)

这对你来说可能是一种矫枉过正,这可能是合适的,我不知道,你没有提供更多细节,但看看它可能是值得的.请注意,有一整套算法,有许多变化和优化.先看一下维基百科的文章;)