I’m attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a heuristic that does the following:
Given a set S containing N start coordinates and a set G containing N goal coordinates, calculate the minimum number of total unit translations of the start points required to move each start points to a goal point such that each goal point is covered. The difficulty is that it does not matter which goal point each start point ultimately lands on.
Here’s a 2d example: You're given a checkerboard with 8 pieces placed randomly on the board in locations specified in set S. G is defined as the set of 8 squares in the bottom row of the board (y=0). For each move, you're allowed to move one checker piece to an adjacent square. Calculate the minimum number of moves required to cover each spot in G with a piece.
I’ve played around with exhaustive solutions to this problem such as generating all the N! ways to arrange the pieces on the goal nodes and finding the distance for each, and I’ve also tried running a search algorithm to find the optimal paths, but these approaches seem too costly to be used as a good heuristic. It’s not so important that I’m able to calculated the actual correct minimum. If I could estimate it within a small margin of error and that error was relatively consistent regardless of the points in the two sets, that would be perfectly fine.
Is there a more efficient way to calculate this than the exhaustive method I tried? A more mathematical way? Or if not, is it possible to estimate it reliably?
