Heuristic for shingles problem
The idea is to move all the right elements left and left to the right with white space in the middle. Elements can jump over one or two pieces into empty space.
LLL[ ]RRR
I am trying to come up with a heuristic for this task. Is a heuristic to aid in finding a possible solution, or is it actually returning multiple moves as a solution? How can I express such a heuristic?
It sounds like you are a little confused about what a heuristic is.
Rough definition is "oversimplification" or "worthy guess"
For example, let's say you have to put together a basketball team and you have fact sheets about people who want to play this list of their contact details, date of birth, and height. You can conduct surveys where you test the skills of each candidate; which will require the involvement of all candidates, although this may be time-consuming. You are using a heuristic to narrow your search — only call people who are at least 6'2 inches tall. This may be ignored by some great basketball players, but it's a pretty decent guess.
Another example of a heuristic: you are trying to use the least amount of coins to pay the bill. The heuristic (simplistic) approach is to first collect the coin with the highest value (which is less than the remaining count), subtract the value from the count, and repeat. This does not guarantee that you will be working every time, but in most cases, you will get to the right place.
The heuristic for your problem might be "never move Ls to the right and never move Rs to the left" - this narrows the "search space" of all possible moves, eliminating some of the possibilities from the start.
source to share
A heuristic is usually a "hint" that will usually (but not always) guide your procedure in the right direction. Using heuristics speeds up your routines (your algorithms), again, usually , but not always. It's like "advice" for an algorithm that is right more often than not.
I'm not sure what you are looking for as the description is a bit vague. If you want an algorithm, you will need to study what effect a particular move will have on the current situation, and a way to step forward for all possible moves each time, effectively traversing the state tree (i.e. the states that will develop if you do a certain sequence of moves).
You can also see that it can make a difference how close the current position is to what you want to reach (your desired end position). Instead, to compute all possible paths from your start state while you find the end state, you can direct your algorithm based on the "how close is the current state to the desired state" heuristic and only traverse part of the tree.
source to share