我的问题如下。
考虑由（u，v）索引的大数组a（u，v）（例如图像）和该数组中的给定参考位置（u0，v0）A中的每个位置（u，v）都与效用得分s（u，v）相关联，效用得分s（u，v）为正且任意；惩罚得分p（u，v）为负且与（u，v）和（u0，v0）之间的距离成比例我想确定一个邻域N（即一组连接的指数（u，v））（U0，V0），其最大化了所有效用和惩罚分数在邻域n的总和。
这是一个相当抽象的描述，但是什么样的算法才是处理这样一个问题的合适算法呢？
最佳答案
快速跟进我已经研究这个问题有一段时间了，我已经能够使用一个修改版的A* algorithm获得令人满意的结果。
更准确地说，我把2d数组看作一个4连通图，把参考位置（u0，v0）看作图中的起始位置。然后，我将两个节点之间的边的代价定义为常数cost_edge，并将图中的路径代价定义为沿此路径的边代价之和作为节点（u，v）的启发式算法，我使用了数组上的最大效用分数和当前节点的效用分数之间的差值：H（u，v）＝sMAX -s（u，v）。我还对基本的a*算法进行了一个修改：我不使用任何目标节点，但是由于节点正在被访问，我为所有访问的节点（如wikipedia文章所示，在封闭集合中的节点）维护效用得分之和，并且当该值大于指定阈值时停止算法。
这个算法有两个输入参数，我必须根据自己对效用得分的定义进行调整：max_total_utility，它控制在所产生的邻域（U0，V0）的局部性和贪婪性之间的折衷，以最大化效用得分的和。cost_edge，它控制最终邻域的面积
这为我的问题提供了适当的（虽然不是严格最优的，特别是启发式可能不会consistent）解决方案，因为它最小化了所选（即访问）节点和输入参考点之间的距离，同时被启发式绘制以首先选择效用得分高的节点。
注意，我不再使用惩罚得分，但是由于它与当前节点和参考位置之间的距离成比例，因此最小化从（U0，V0）到（U，V）的路径的成本是一个足够好的近似，以最小化总体惩罚得分。
关于algorithm - 优化2D社区的效用和罚分，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22074809/