Optimizing an utility and penalty score on a 2D neighborhood

Question

My problem is the following.

Consider a large array A(u,v) indexed by (u,v) (e.g. an image) and a given reference position (u0,v0) inside this array. Each position (u,v) in A is associated with an utility score s(u,v), which is positive and arbitrary, and a penalty score p(u,v), which is negative and proportional to the distance between (u,v) and (u0,v0). I want to determine a neighborhood N (i.e. a set of connected indices (u,v)) around (u0,v0) which maximizes the sum of all utility and penalty scores on the neighborhood N.

This is a rather abstract description, but what would be an appropriate algorithm to approach such a problem ?

Answer 1

A quick follow up. I have been working on this problem for some time and I have been able to obtain satisfactory results using a modified version of A* algorithm.

More precisely, I considered the 2D array as a 4-connected graph and the reference position (u0,v0) as a starting position in the graph. I then defined the cost of an edge between two nodes to be a constant cost_edge and the cost of a path in the graph to be the sum of the edge costs along this path. As a heuristic for node (u,v), I used the difference between the maximum utility score on the array and the utility score of the current node: h(u,v) = s_max - s(u,v). I also used one modification to the base A* algorithm: I do not use any destination node, however as nodes are being visited, I maintain the sum of utility scores for all visited nodes (nodes in the closed set, as denoted by the Wikipedia article) and I stop the algorithm when this sum becomes larger than a specified threshold max_total_utility.

This algorithm has two input parameters which I had to tweak according to my own definition of utility score:

• cost_edge, which controls the compromise to be made between the locality of the resulting neighborhood around (u0,v0) and the greediness to maximize the sum of utility scores

• max_total_utility, which controls the area of the final neighborhood

This provides appropriate (though not strictly optimal, in particular the heuristic may not be consistent) solutions to my problem because it minimizes the distance between the selected (i.e. visited) nodes and the input reference point, while being drawn by the heuristic to select first the nodes with high utility scores.

Note that I do not use the penalty score anymore, but since it was proportional to the distance between the current node and the reference position, minimizing the cost of the path from (u0,v0) to (u,v) is a good enough approximation to minimizing the overall penalty score.