代码之家 › 专栏 › 技术社区 › noman pouigt

算术运算BFS

breadth-first-search algorithm python

noman pouigt · 技术社区 · 10 年前

用最小运算将数字m转换为n。允许的操作是1减2乘。

例如:4和6。答案是2。第一次操作:-1->4-1 = 3. 第二次操作:*->3 * 2 =6.

我使用BFS方法处理一个特定的输入(src=26,dst=5),这需要很长时间。我做错什么了吗?

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)

3 回复 | 直到 10 年前

LeartS 10 年前

您的算法是指数型的,在每增加一个“宽度级别”,您将为前一级别中的每个值添加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个“宽度级别”=21个操作。在该级别,您的队列和 seen_list 将包含~2^20个值;对队列中的每个值进行线性搜索,以查看它是否存在于列表中,因此该级别将由2^20*2^20个比较=2^40~1000亿个比较组成。这需要时间,这只是最后一关。

你应该想一个更好的算法。对于初学者来说,如果您的当前值高于目标值,那么将其加倍是没有意义的,因为它肯定只会增加额外的步骤。。仅此考虑就可以将这种情况下的步骤数从数百万减少到21(您只需减去1,直到达到目标值,通常情况下 src > dest )

user4668606 user4668606 10 年前

由于指数增长,BFS在这里并不完全是一个选项( 2 ^ (n - 1) to 2^n 其中n是所需步骤的数量)。相反,尝试找到生成所需数字的逻辑规则。

允许 a 为输入编号 b 应该产生的数字。

有三种情况:

a == b ,本例很简单,仅列出完整性
a > b ,解决方案是 a - b 乘以 -1
a < 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 .

在上面的java实现中测试运行将产生以下输出:

(((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,那么需要两次减法才能达到4,然后你从4爬到26。如果A是12,那么需要五次减法才可以达到7,以此类推。显然,如果A大于B,那么你所做的就是减一直到你达到B

Razorbolt 10 年前

该代码有望实现上述非常有效的算法。

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),然后你就在最佳的轨道上,到达你的目的地。更多信息:请参考mr.paul解决方案中的解释,上面的解释更好地解释了这一点。