Minimum number of moves from a to b

[BiGyElLoWhAt]

Hi, I think this is a topology question, but I'm honestly not 100% sure. Feel free to move.

On a number line, I am trying to find the minimum number of moves to get from one point to another, given certain allowed step sizes. For example, My allowed steps might be +/-2, +/-3, and I want to move from 0 to 1. my shortest number of moves would be 2 in this case, +3->-2 or -2->+3. Now say I want to move from a->b. How would I go about figuring out the shortest number of moves?
My actual problem also has constraints on the moves as well, some places I can't execute more than one of the moves. Think about it as a finite 2D space projected onto a line. So I have an nxm grid numbered 0 through n*m-1 and I'm not allowed to leave the grid. If I'm looking at a position along the left hand side, I can't, for example, use -3. I'm just curious about how I should go about solving this problem, so I'm not giving the actual example, but in case you're curious, it's a 2d space mapped to a 1d space, and the set of moves are +/- (6,10,15,17) with constraints, like position 0 can only move 10 and 17. No negative positions are allowed, however I don't think that is all that important, since there is a symmetric move (3-2 vs -2+3 in the original example).

My guess is that it can be solved using a metric with the proper distance function for each point. However that doesn't feel quite right. If I am not clear, I can attempt to clarify. I'm more looking for the approach to the solution rather than the solution itself, so let's stick with +/-(2,3) for our moves, and arbitrary constraints if that works for whoever is reading this to help.

Thanks in advance.

 

[mfb]

In general this can be a very difficult problem, but if you only have a very limited set of moves you can simply explore all options. Do an A* search or something similar if the problem gets too complex for a simple recursion.

As long as everything is symmetric, let's say b>a. For a given a, if your constraints are not too obscure, there is a largest b, b₀ where the ideal solution does not include a positive step of the largest possible value. You only have to explore the range up to there. Larger b are constructed by simply adding more of the largest possible step and using a solution found previously for smaller b for the rest.

With +-2 and 3, this b₀ is just 4 above a:

• +1 is +3 -2
• +2 is +2
• +3 is +3
• +4 is +2 +2
• everything beyond that is repeated +3 until you get one of the previous three cases.

 

[WWGD]

Does the order of the moves matter, i.e., if I do +3 followed by -2 , is this the same as doing -2 and then +3 ?
EDIT: If this is so and forward- , backward- moves are allowed for all, then it comes down to GCD of the set of moves dividing the number of moves you want to do.

 

[BiGyElLoWhAt]

The order doesn't matter as long as the moves are permitted. I have figured it out for 8x8 and there are 4 spots with 2 moves, 20 with 4, 16 with 6, and 24 with 8.

With regards to mfb's response, perhaps 3 and 2 were bad choices, because that gives you the option of moving 1 space with 2 moves. The issue I'm running into is I'm getting overflow errors, presumably because it can't find a correct set of moves, let alone the minimum set. My current method is recursive, but it's not that good, because I haven't figured out what exactly to program.
I first check to see if I can get from a to b with a move allowed from a. If I can't I check to see if I can get to a spot that is an allowed move from b with a move from a. It's worth mentioning that if a move is allowed from c to d, the negative of that move is allowed from d to c, always

 

[BiGyElLoWhAt]

This works for spaces that are 2 moves apart, I'm just not sure how to handle it from there. With nested recursion, I can only check 1 move at a time (if I follow that move to it's possible moves). I remember something in java class where it was a tree, like a family tree. I can do that, but that doesn't seem like a fast way to do it (order n! If I'm not mistaken.

 

[BiGyElLoWhAt]

One more thing that I've noticed, out of the 8 possible moves, each one takes you +/-(1,3) away from a multiple of 9. So, in my specif case, i have +/-(6,10,15,17) and if we work in Finite field 9 (modular arithmetic), each one of those has an associated +/-(1 or 3) associated with it. That was actually the first thing I noticed. For a different size 2d space, the finite field would be different, as well as the allowed moves, but I think one can be derived from the other, so it's not 2 independant pieces of information. Correct me if I'm wrong, but that shouldn't be useful.

 

[mfb]

With your specific example:
Make a list from 0 to 300. 0 is your starting position and 300 > 15*17 should be well above b₀.

We know how to reach 0 optimally, we don't know it for anything else.
First iteration: Loop over all positions, if you know how to reach them optimally add/subtract each possible step, if you reach a legal position that hasn't been explored yet store how you got there, otherwise do nothing. After this iteration you know how to reach 0,6,10,15,17 optimally.
Second iteration: Same as above. From 0 you don't learn anything new, but from 6 you learn how to reach 12, 16, 21 and 23, from 10 you learn how to reach 4, (16), 20, 25 and 27, from 15 you get 9,5,32, and from 17 you get 11,7,2,34.

You should be done after ~17 iterations, checking 300 numbers each (5100 quick checks), and 300 times you have to add/subtract 4 different values each (2400 quick checks), with 300 updates. A computer can do that in fractions of a second.