Branch and Bound - Transform a into b

Question

I'm trying to design an algorithm which will accept two natural numbers: a and b. Its purpose is to get b from a by making the following operations: *3 and /2. For example, if a = 10 and b = 7, then:

10/2*3/2 = 7

I decided to use branch and bound, since I believe there's no better suitable algorithm for this.

My program works, but I'm having really trouble finding a heuristic.

What could it be?

Thank you.

Answer 1

I don't know of any algorithm that will work for all $a,b$, because of the possibility that you might have to use an intermediate value that is extremely large, and I'm not aware of any reasonable bound on how large of an intermediate value you need to contemplate.

However, here's one heuristic. Suppose we only consider sequences where no intermediate value exceeds some constant $K$. Then you can use dynamic programming to determine whether it's possible to go from $a$ to $b$, without ever exceeding $K$. You build an array $A[1..K]$ where $A[i]=1$ means that it's possible to reach $i$ from $a$, and fill it in via a fixed point computation, as follows:

1. Set $A[a]=1$ and $A[i]=0$ for all $i \ne a$.
2. Repeatedly do the following, until you do an entire iteration without changing the array:
   • For each $i := 1,2,\dots,K/3$, if $A[i]=1$, set $A[3i] := 1$.
   • For each $i := 3,4,\dots,K$, if $A[i]=1$, set $A[\lfloor i/2 \rfloor] := 1$.

Finally, if $A[b]=1$, you know it's possible to go from $a$ to $b$. (If $A[b]=0$, you can conclude nothing; maybe there's a way to get from $a$ to $b$ by going through some intermediate value larger than $K$.)