从源到目标的最小操作数

Question

我在一次采访中遇到了这个问题-在最少的操作次数中将数字源转换为目标。

允许操作

1. 乘以2
2. 加1
3. 减去1

0<源，目标<=1000.

我试着走简单的递归路线(O(3^n((，即在每个级别上减1、加1和乘2，试图找到一个可以扩展到动态编程的解决方案，但由于存在无限循环，所以无法找到。

//Naive approach Via Recursion 
int minMoves(int source, int target){
if(source <1 || source > target){
return -1;
}
int moves =0;
// Potential infinite loop - consider 3,6-> 2,6- >1,6->(0,6)x (2,6)->1,6->(0,6)x (1,6)->(0,6)x (2,6)->1,6..
int movesLeft  = minMoves(source -1, target) ==-1? Integer.MAX_VALUE:minMoves(source -1, target);
int movesRight  = minMoves(source +1, target) ==-1? Integer.MAX_VALUE:minMoves(source +1, target);
int moves2X  = minMoves(2*source, target) ==-1? Integer.MAX_VALUE:minMoves(2*source, target);
moves = 1+ Math.min(Math.min(movesRight,movesLeft), moves2X);
return moves;
}

关于如何调整我的解决方案，有什么想法吗？或者可能是更好的解决方法？

Answer 1

如果你把你的解决方案看作是一个图遍历，其中每个节点都是你可以产生的中间值，那么你的递归解决方案就像深度优先搜索(DFS(。你必须完全扩展，直到你尝试了搜索空间"分支"的所有解决方案，然后才能去其他地方。如果你有一个无限循环，这意味着即使存在较短的路径，它也永远不会终止。即使你没有无限循环，你仍然必须搜索解决方案空间的其余部分，以确保其最优。

相反，考虑一种类似于广度优先搜索(BFS(的方法。你会均匀地向外扩展，永远不会搜索到比最优解更长的路径。只需使用FIFO队列来安排下一个访问哪个节点。这是我对求解器采取的方法。

from queue import Queue
def solve(source, target):
queue = Queue()
path = [source]
queue.put(path)
while source != target:
queue.put(path + [source * 2])
queue.put(path + [source + 1])
queue.put(path + [source - 1])
path = queue.get()
source = path[-1]
return path
if __name__ == "__main__":
print(solve(4,79))

Answer 2

在维护递归实现的同时，可以加快(并可能修复(此代码的一种方法是使用memoization。

这里的问题是，您要多次重新计算相同的值。相反，您可以使用map来存储已经计算的结果，并在再次需要时重用它们。

Answer 3

这个问题可以建设性地解决。首先，简单的案例。如果s=t，则答案为0。如果s>t，答案是s-t，因为减法1是唯一降低s的运算，而其他两个运算只能增加所需的减法次数。

现在让我们假设s<t.由于给定s>0，加倍将始终是增加的最快方式(如果s为1，则与递增有关(。因此，如果挑战是使s>=t，那么答案总是需要加倍的次数。这个过程可能会过冲t，但第一次加倍大于t和最后一次加倍不大于t必须在t的2倍以内。

让我们来看看当我们做加法或减法时的效果。首先，只看加法：

(((s*2) * 2) * 2) + 1 = 8s + 1

vs：

((((s+1)*2) * 2) * 2) = 8s + 8

在n个加倍之前加一个加法会使最终结果大2^n。因此，考虑s是否为3，t是否为8。最后一个不大于8的倍数是6。这是2分，所以如果我们在最后一个加倍之前加1个加倍，我们就会得到我们想要的：(3+1(*2。或者，我们可以尝试过冲到大于8的第一个倍数，也就是12。这是4次，所以我们需要在最后一次之前减去两次：(3-1(*2*2=8

通常，如果我们的x低于目标，如果x的二进制表示在第n位有1，我们需要在最后一个之前的n个加倍处放置+1。

类似地，如果我们比目标高x，我们对-1的s也一样。

这个过程对x的二进制表示中的1没有帮助，因为它们的位置超过了加倍的数量。例如，如果s＝100，t＝207，则只需要进行1次加倍，但x是7，即111。我们可以先做加法把中间的一个敲出来，剩下的我们必须一个接一个地做(s+1)*2 + 1 + 1 + 1 + 1 + 1。

这里有一个实现，它有一个调试标志，当定义该标志时，它还输出操作列表。运行时间为O(log(t((:

#include <iostream>
#include <string>
#include <sstream>
#define DEBUG_INFO
int MinMoves(int s, int t)
{
int ans = 0;
if (t <= s)
{
return s - t; //Only subtraction will help
}
int firstDoubleGreater = s;
int lastDoubleNotGreater = s;
int nDouble = 0;
while(firstDoubleGreater <= t)
{
nDouble++;
lastDoubleNotGreater = firstDoubleGreater;
firstDoubleGreater *= 2;
}
int d1 = t - lastDoubleNotGreater;
int d2 = firstDoubleGreater - t;
if (d1 == 0)
return nDouble -1;
int strat1 = nDouble -1;        //Double and increment
int strat2 = nDouble;           //Double and decrement

#ifdef DEBUG_INFO
std::cout << "nDouble: " << nDouble << "n";
std::stringstream s1Ops;
std::stringstream s2Ops;
int s1Tmp = s;
int s2Tmp = s;
#endif
int mask = 1<<strat1;
for(int pos = 0; pos < nDouble-1; pos++)
{
#ifdef DEBUG_INFO
if (d1 & mask)
{
s1Ops << s1Tmp << "+1=" << s1Tmp+1 << "n" << s1Tmp+1 << "*2= " << (s1Tmp+1)*2 << "n";
s1Tmp = (s1Tmp + 1) * 2;
}
else
{
s1Ops << s1Tmp << "*2= " << s1Tmp*2 << "n";
s1Tmp = s1Tmp*2;
}
#endif
if(d1 & mask)
strat1++;
d1 = d1 & ~mask;
mask = mask >> 1;
}
strat1 += d1;
#ifdef DEBUG_INFO
if (d1 != 0)
s1Ops << s1Tmp << " +1 " << d1 << " times = " << s1Tmp + d1 << "n";
#endif
mask = 1<<strat2;
for(int pos = 0; pos < nDouble; pos++)
{
#ifdef DEBUG_INFO
if (d2 & mask)
{
s2Ops << s2Tmp << "-1=" << s2Tmp-1 << "n" << s2Tmp-1 << "*2= " << (s2Tmp-1)*2 << "n";
s2Tmp = (s2Tmp-1)*2;
}
else
{
s2Ops << s2Tmp << "*2= " << s2Tmp*2 << "n";
s2Tmp = s2Tmp*2;
}
#endif

if(d2 & mask)
strat2++;
d2 = d2 & ~mask;
mask = mask >> 1;
}
strat2 += d2;
#ifdef DEBUG_INFO
if (d2 != 0)
s2Ops << s2Tmp << " -1 " << d2 << " times = " << s2Tmp - d2 << "n";

std::cout << "Strat1:   "  << strat1 << "n";
std::cout << s1Ops.str() << "n";
std::cout << "nnStrat2:   "  << strat2 << "n";
std::cout << s2Ops.str() << "n";
#endif
if (strat1 < strat2)
{
return strat1;
}
else
{
std::cout << "Strat2n";
return strat2;
}
}


int main()
{
int s = 25;
int t = 193;
std::cout << "s = " << s << "  t = " << t << "n";
std::cout << MinMoves(s, t) << std::endl;
}

Answer 4

短BFS算法。它找到了图中每个顶点x连接到x+1、x-1和x*2的最短路径；O(n(

#include <bits/stdc++.h>
using namespace std;
const int _MAX_DIS = 2020;
const int _MIN_DIS = 0;
int minMoves(int begin, int end){
queue<int> Q;
int dis[_MAX_DIS];
fill(dis, dis + _MAX_DIS, -1);
dis[begin] = 0;
Q.push(begin);
while(!Q.empty()){
int v = Q.front(); Q.pop();
int tab[] = {v + 1, v - 1, v * 2};
for(int i = 0; i < 3; i++){
int w = tab[i];
if(_MIN_DIS <= w && w <= _MAX_DIS && dis[w] == -1){
Q.push(w);
dis[w] = dis[v] + 1;
}
}
}
return dis[end];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout << minMoves(1, 1000);
return 0;
}