用于算术运算的 BFS
BFS for arithmetic operations
用最少的操作将数字 m 转换为 n。允许的操作是减1和乘2。
例如：4 和 6。答案是 2。
第一次操作：-1 -> 4-1 = 3。
第二次操作：* -> 3 * 2 =6.
我正在对特定输入（src=26，dst=5）使用 BFS 方法，这需要很长时间。我做错了什么吗？
from queue_class import queue
class node:
def __init__(self, value, level, parent):
self.level = level
self.value = value
self.parent = parent
def get_minimum_distance(src, target, q):
if src == target:
return 0
seen_list = []
data = node(src, 0, -1)
q.enqueue(data)
while not q.isempty():
data = q.dequeue()
if data == "sentinel":
break
if data.value == target:
# let's print what has got me here
while data.parent != -1:
print(data.value)
data = data.parent
return "finally reached"
if data.value in seen_list:
continue
seen_list.append(data.value)
# two operations are allowed i.e. -1 and multiplication by 2
# check if two numbers have opposite sign and if they have
# then check if the current number being subtracted from is a negative
# number. If it is, then there is no point subtracting 1 from that
if ((data.value ^ target) < 0 and data.value > 0) or (data.value ^ target >= 0):
q.enqueue(node(data.value - 1, data.level + 1, data))
q.enqueue(node(data.value * 2, data.level + 1, data))
return -1
q = queue(1 << 20)
print(get_minimum_distance(26, 5, q))
队列实现完成here。
感谢保罗：
下面是我在 python 中提出的代码，它工作得很好。
def get_minimum_operations(src, dst):
step = 0
operations = []
if src == dst:
return 0
if dst < src:
return src-dst
while dst > src:
if dst & 0x01:
step += 1
operations.append("-1")
dst = (dst+1) >> 1
operations.append("*2")
step += 1
for i in range(0, src-dst):
operations.append("-1")
return (((src - dst) + step), operations)
src = 38
dst = 100
output = ""
(steps, operations) = get_minimum_operations(src, dst)
print(steps)
try:
while operations:
i = operations.pop()
if i == "*2":
if output == "":
output += "(" + str(src) + "*2" + ")"
else:
output = "(" + output + "*2" + ")"
if i == "-1":
if output == "":
output += "(" + str(src) + "-1" + ")"
else:
output = "(" + output + "-1" + ")"
except IndexError:
pass
print(output)
您的算法是指数级的，每增加一个 "breadth level"，您就会为前一级别的每个值添加 2 个新值。例如：
26 (breadth = 0)
25, 52 (breadth = 1)
24, 50, 51, 104 (breadth = 2)
23, 48, 49, 100, 50 (skipped because seen), 102, 103, 208 (breadth = 3)
22, 46, 47, 96, 48 (skip), 98, 99, 200 (breadth = 4)
21, 44, 45, 92, 46, 94, 95, 192, 97, 196, 199, 400 (breadth = 5)
src=26,dst=5 的解法是减 1 直到 5，这需要 21 "breadth levels" = 21 次操作。在该级别，您的队列和 seen_list 都将包含 ~2^20 个值；对于队列中的每个值，您都进行线性搜索以查看它是否存在于列表中，因此该级别将包含 2^20 * 2^20 次比较 = 2^40 ~ 1000 亿次比较。这需要时间，而且只是最后一关。
你应该想一个更好的算法。对于初学者来说，如果您的当前值高于目标值，则没有必要将其加倍，因为它肯定只会增加额外的步骤。
仅此考虑就会将这种情况的步骤数从数百万减少到 21（您只需减去 1 直到达到目标值，这通常会在 src > dest)
时发生
BFS 在这里并不是一个正确的选择，因为指数增长（2 ^ (n - 1) to 2^n 次尝试，其中 n 是所需的步骤数）。相反，尝试找到生成所需数字的逻辑规则。
设a为input-number，b为应生成的数字。
分三种情况：
a == b，这个案例很简单，只是为了完整性而列出a > b，解法是a - b次减去-1a < b：这是比较棘手的部分
最少的运算次数要求最少的乘法和减法次数。由于以下事实，减法可以很容易地最小化：(a - 1) * 2 = a * 2 - 2。因此，我们可以通过简单地在乘法之前减法来轻松地将减法次数减少为 2 的幂。
由于我们只会做减法和乘法，所以最少的乘法次数是min n => a * 2 ^ n >= b.
使用这个事实，我们可以确定要减去的数量：s = b - 2 ^ n * a。
伪代码中的实现如下所示（无法提供 python 代码）：
//using the same variable-names as above in the description
minOp(int a , int b)
//find minimum number of multiplications
int n
for(n = 0 ; a << n < b ; n++)
noop
//find amount to substract
int s = (a << n) - b
for(int i = 0 ; i < n ; i++)
print("(")
print(a)
//calculate operations
while(n > 0)
//calculate number of times we need to substract here (minimization of substractions)
while(s >= 1 << n)
print(" - 1")
s -= 1 << n
print(")")
//divide by two
print(" * 2")
n -= 1
while(s >= 1 << n)
print(" - 1")
s -= 1 << n
print(" = ")
print(b)
此实现还涵盖案例 a == b - n = 0 和 s = 0 - 和 a > b - n = 0 和 s = a - b。
A test-run in a java-implementation 以上将产生这个输出：
(((4) * 2 - 1) * 2 - 1) * 2 = 26
上述计算的简化显示了该算法背后的思想：
((4 * 2 - 1) * 2 - 1) * 2 = 26
(4 * 2 * 2 - 2 - 1) * 2 = 26
4 * 2 * 2 * 2 - 3 * 2 = 26
32 - 6 = 26
感谢@user3386109 的解释：
假设起始值为 A，目标值为 B。第一步是创建一个目标值列表，从 B 开始，然后除以 2（必要时四舍五入）。例如，如果 B 是 26，那么目标值列表将是 26、13、7、4、2、1。如果起始值 A 是这些目标值中的任何一个，那么您可以轻松地爬到目标 B (乘以 2 并在必要时减去 1）。如果 A 不是这些值之一，则首先从 A 中减去 1，直到达到这些目标值之一。比如A是6，那么要减2次才能到4，然后你从4爬到26。如果A是12，要减5次才能到7，以此类推。显然，如果 A 大于 B，那么您所做的就是减一，直到达到 B
这段代码有望实现上述非常高效的算法。
private static int solve(int n, int m) {
int steps = 0;
int cur = n;
ArrayList<Integer> arr = new ArrayList<>();
arr.add(m);
for (int i = 0; !arr.contains(1); ++i)
arr.add((int) Math.round((double) arr.get(i) / 2));
while (cur != m) {
if (arr.contains(cur))
cur *= 2;
else
cur--;
steps++;
}
return steps;
}
解释::
想象一个楼梯，从 (n) 开始你必须到达它的顶部（即：数字 m），所以你决定列出所有最好的步骤，然后参考数字你有，看看它是否存在于你为最佳解决方案制定的列表中，如果它存在，那么你只需按照步骤操作即可获得最佳解决方案，如果不存在，则必须使自己与最佳步骤保持一致（比如通过减去 1) 然后你就在最佳轨道上，然后 vooooom 到你的目的地。
有关更多信息：请参阅 mr.paul 解决方案中的解释，那里解释得更好。
用最少的操作将数字 m 转换为 n。允许的操作是减1和乘2。
例如：4 和 6。答案是 2。 第一次操作：-1 -> 4-1 = 3。 第二次操作：* -> 3 * 2 =6.
我正在对特定输入（src=26，dst=5）使用 BFS 方法，这需要很长时间。我做错了什么吗？
from queue_class import queue
class node:
def __init__(self, value, level, parent):
self.level = level
self.value = value
self.parent = parent
def get_minimum_distance(src, target, q):
if src == target:
return 0
seen_list = []
data = node(src, 0, -1)
q.enqueue(data)
while not q.isempty():
data = q.dequeue()
if data == "sentinel":
break
if data.value == target:
# let's print what has got me here
while data.parent != -1:
print(data.value)
data = data.parent
return "finally reached"
if data.value in seen_list:
continue
seen_list.append(data.value)
# two operations are allowed i.e. -1 and multiplication by 2
# check if two numbers have opposite sign and if they have
# then check if the current number being subtracted from is a negative
# number. If it is, then there is no point subtracting 1 from that
if ((data.value ^ target) < 0 and data.value > 0) or (data.value ^ target >= 0):
q.enqueue(node(data.value - 1, data.level + 1, data))
q.enqueue(node(data.value * 2, data.level + 1, data))
return -1
q = queue(1 << 20)
print(get_minimum_distance(26, 5, q))
队列实现完成here。
感谢保罗： 下面是我在 python 中提出的代码，它工作得很好。
def get_minimum_operations(src, dst):
step = 0
operations = []
if src == dst:
return 0
if dst < src:
return src-dst
while dst > src:
if dst & 0x01:
step += 1
operations.append("-1")
dst = (dst+1) >> 1
operations.append("*2")
step += 1
for i in range(0, src-dst):
operations.append("-1")
return (((src - dst) + step), operations)
src = 38
dst = 100
output = ""
(steps, operations) = get_minimum_operations(src, dst)
print(steps)
try:
while operations:
i = operations.pop()
if i == "*2":
if output == "":
output += "(" + str(src) + "*2" + ")"
else:
output = "(" + output + "*2" + ")"
if i == "-1":
if output == "":
output += "(" + str(src) + "-1" + ")"
else:
output = "(" + output + "-1" + ")"
except IndexError:
pass
print(output)
您的算法是指数级的，每增加一个 "breadth level"，您就会为前一级别的每个值添加 2 个新值。例如：
26 (breadth = 0)
25, 52 (breadth = 1)
24, 50, 51, 104 (breadth = 2)
23, 48, 49, 100, 50 (skipped because seen), 102, 103, 208 (breadth = 3)
22, 46, 47, 96, 48 (skip), 98, 99, 200 (breadth = 4)
21, 44, 45, 92, 46, 94, 95, 192, 97, 196, 199, 400 (breadth = 5)
src=26,dst=5 的解法是减 1 直到 5，这需要 21 "breadth levels" = 21 次操作。在该级别，您的队列和 seen_list 都将包含 ~2^20 个值；对于队列中的每个值，您都进行线性搜索以查看它是否存在于列表中，因此该级别将包含 2^20 * 2^20 次比较 = 2^40 ~ 1000 亿次比较。这需要时间，而且只是最后一关。
你应该想一个更好的算法。对于初学者来说，如果您的当前值高于目标值，则没有必要将其加倍，因为它肯定只会增加额外的步骤。
仅此考虑就会将这种情况的步骤数从数百万减少到 21（您只需减去 1 直到达到目标值，这通常会在 src > dest)
BFS 在这里并不是一个正确的选择，因为指数增长（2 ^ (n - 1) to 2^n 次尝试，其中 n 是所需的步骤数）。相反，尝试找到生成所需数字的逻辑规则。
设a为input-number，b为应生成的数字。
分三种情况：
a == b，这个案例很简单，只是为了完整性而列出a > b，解法是a - b次减去-1a < b：这是比较棘手的部分
最少的运算次数要求最少的乘法和减法次数。由于以下事实，减法可以很容易地最小化：(a - 1) * 2 = a * 2 - 2。因此，我们可以通过简单地在乘法之前减法来轻松地将减法次数减少为 2 的幂。
由于我们只会做减法和乘法，所以最少的乘法次数是min n => a * 2 ^ n >= b.
使用这个事实，我们可以确定要减去的数量：s = b - 2 ^ n * a。
伪代码中的实现如下所示（无法提供 python 代码）：
//using the same variable-names as above in the description
minOp(int a , int b)
//find minimum number of multiplications
int n
for(n = 0 ; a << n < b ; n++)
noop
//find amount to substract
int s = (a << n) - b
for(int i = 0 ; i < n ; i++)
print("(")
print(a)
//calculate operations
while(n > 0)
//calculate number of times we need to substract here (minimization of substractions)
while(s >= 1 << n)
print(" - 1")
s -= 1 << n
print(")")
//divide by two
print(" * 2")
n -= 1
while(s >= 1 << n)
print(" - 1")
s -= 1 << n
print(" = ")
print(b)
此实现还涵盖案例 a == b - n = 0 和 s = 0 - 和 a > b - n = 0 和 s = a - b。
A test-run in a java-implementation 以上将产生这个输出：
(((4) * 2 - 1) * 2 - 1) * 2 = 26
上述计算的简化显示了该算法背后的思想：
((4 * 2 - 1) * 2 - 1) * 2 = 26
(4 * 2 * 2 - 2 - 1) * 2 = 26
4 * 2 * 2 * 2 - 3 * 2 = 26
32 - 6 = 26
感谢@user3386109 的解释：
假设起始值为 A，目标值为 B。第一步是创建一个目标值列表，从 B 开始，然后除以 2（必要时四舍五入）。例如，如果 B 是 26，那么目标值列表将是 26、13、7、4、2、1。如果起始值 A 是这些目标值中的任何一个，那么您可以轻松地爬到目标 B (乘以 2 并在必要时减去 1）。如果 A 不是这些值之一，则首先从 A 中减去 1，直到达到这些目标值之一。比如A是6，那么要减2次才能到4，然后你从4爬到26。如果A是12，要减5次才能到7，以此类推。显然，如果 A 大于 B，那么您所做的就是减一，直到达到 B
这段代码有望实现上述非常高效的算法。
private static int solve(int n, int m) {
int steps = 0;
int cur = n;
ArrayList<Integer> arr = new ArrayList<>();
arr.add(m);
for (int i = 0; !arr.contains(1); ++i)
arr.add((int) Math.round((double) arr.get(i) / 2));
while (cur != m) {
if (arr.contains(cur))
cur *= 2;
else
cur--;
steps++;
}
return steps;
}
解释::
想象一个楼梯，从 (n) 开始你必须到达它的顶部（即：数字 m），所以你决定列出所有最好的步骤，然后参考数字你有，看看它是否存在于你为最佳解决方案制定的列表中，如果它存在，那么你只需按照步骤操作即可获得最佳解决方案，如果不存在，则必须使自己与最佳步骤保持一致（比如通过减去 1) 然后你就在最佳轨道上，然后 vooooom 到你的目的地。 有关更多信息：请参阅 mr.paul 解决方案中的解释，那里解释得更好。