Heuristic in A* when exact weight of the goal state is unknown

user_10343062 0
Viewed 162

So here is the problem I have been working on: You are given a random nxn grid with weights in each box of the grid and you are also given a set of pegs p<=n. Your goal is to place the pegs on the grid such that the sum of weights on the grid where the pegs are placed is maximized. The constraint is that the peg positions have to follow the non-attacking Queen placements too.

My initial attempt was to start with the max score grid box and follow the n queen placement. However, this doesn't work as it misses the max value in the end.

I have been trying to solve this with A* but have been struggling to find a heuristic.

heuristics search algorithm
1 Answers

Usually A* search is used for finding a shortest path, and not for finding the maximum value, but you can use it for maximizing as well. In the usual minimization version your heuristic has to always be a lower bound for the length. To maximize, the heuristic needs to be an upper bound that isn't too hard to calculate. And you need a max-heap, not a min-heap to produce the next best candidate.

One other issue is that there are many different orders to select the best placement. With an n x n board there will be n! such orders. You will greatly speed your search if you do something like insist on selecting from largest to smallest pin.

I would therefore suggest as a heuristic the sum of the largest pins that are not already under attack, and are no larger than the smallest pin you currently have selected without trying to test for being non-attacking. This is an easily calculated upper bound, and will cause you to initially begin with the obvious greedy choice of trying to grab the biggest available pin.

user_5854110
Related