在尽可能少的步骤中找到移动目标的算法

问题描述 投票:1回答:3

我有以下问题我正在努力解决:

连续有6个杯子(比如编号1到6)。其中一个杯子下面是一个球(我不知道哪一个)。我可以抬起一个杯子,看看球是否在那里。如果是的话,我赢了。如果不是,则球从其当前位置移动到杯子直到左或右(因此从杯子4到杯子3或5)。从杯子6它只能移动到杯子5)。球必须移动,它不能留在原地。

问题是:如果你使用最佳策略,在你知道球的位置之后会有多少次“杯升”。

目前,我已经解决了最糟糕的6升电梯的策略。请注意,不需要进行最终升力“证明”球的位置。我的问题是:是否有一个更好的“最坏情况”的算法?如果没有,我如何证明这是最好的算法?

我目前的策略。我们假设球在开始时处于均匀的杯子下(所以2,4或6)。我最坏情况的一步一步如下。

升降机1:提升杯编号2.球不在那里。根据我们的假设,球将移动到一个奇数杯,但它不能移动到杯子1(因为它必须来自杯子2,它不在那里)

升降机2:提升杯编号3.球不在那里。我不可能在1(见上文),它不低于3,并且假设它在一个奇怪的杯子下面。这意味着它现在在杯子5下面,因此必须移动到杯子4或6。

升降机3:升降杯4号,球不在那里。这意味着它必须移动到6号杯子,所以在下一步移动时它必须移动到5号杯子

升降机4:升降杯5号,球不在那里。这是剩下的唯一可能性,所以我们错误地猜测它是在一个偶数杯下开始的。结果,它现在处于一些甚至杯子之下,并且将在下一步移动到一个奇数杯。我们现在使用相同的过程,但反过来。

提升5:提升杯号5(再次)。球不存在。根据新的假设,球现在将移动到杯子2或4(同样,它不能移动到杯子6,因为它不低于5)。

升降机6:提升杯编号4.它不在那里,所以它必须在2号杯子下面(它在一个均匀的杯子下面,并且不在6或4下)。因此,我们知道杯子的位置(即使我们没有执行第2号杯子的最终提升)。

algorithm search optimization
3个回答
1
投票

你的算法有一个缺陷。如果球在奇数位置开始,则在偶数次移动后它将在奇数位置结束。您的算法假定它在六次移动后处于偶数位置。那永远不会奏效。此外,您的升降顺序并不能确定球的位置。

例如,假设球在杯子#1下面开始。按照您的升降顺序,可以进行以下操作。

  1. 提升杯2.球移动到杯子2。
  2. 提升杯3.球移动到杯子1。
  3. 提升杯4.球移动到杯子2。
  4. 提升杯5.球移动到杯子1。
  5. 提升杯5(再次)。球移动到杯子2。
  6. 提升杯4.球移动到杯子1。

在步骤6之后,球可以从杯子2移动到杯子1或杯子3.所以你不知道它在哪里。


1
投票

如果你想用一个程序来解决这个问题,可以构建一个图形,其中顶点是球可能存在的位置,边缘是杯子提升,结果是不显示球。然后解决方案是从任何开始状态到任何状态的最短路径,具有2个可能的杯升降机。 (结束于a的终止条件有点混乱,因为它允许“知道”球在移动之前的位置)。

这段代码非常粗糙,但使用DFS查找最短路径,然后漂亮地打印解决方案。它确认在最坏的情况下需要6杯升降机才能找到球,事实上找到了与你完全相同的解决方案。

输出是:

$ python cups.py
the ball can be under cups: 1,2,3,4,5,6
lift cup 2
the ball can be under cups: 2,3,4,5,6
lift cup 3
the ball can be under cups: 1,3,4,5,6
lift cup 4
the ball can be under cups: 2,4,5,6
lift cup 5
the ball can be under cups: 1,3,5
lift cup 5
the ball can be under cups: 2,4
lift cup 2

代码是:

import collections

N = 6
MASK = (1<<N)-1

def bitcount(n):
    if n == 0: return 0
    return 1 + bitcount(n & (n-1))

def shifts(c):
    return ((c << 1) | (c >> 1)) & MASK

def adjacent(c):
    if bitcount(c) == 2:
        yield min(i for i in xrange(N) if (c>>i)&1), 0
        return
    for i in xrange(N):
        if (c>>i)&1:
            yield i, shifts(c & ~(1<<i))

def bfs(edges, start):
    prev = {start: None}
    q = collections.deque([start])
    while q:
        x = q.popleft()
        for y in edges[x]:
            if y in prev: continue
            prev[y] = x
            q.append(y)
    return prev

def path(x, prev):
    if x is None: return []
    return path(prev[x], prev) + [x]

edges = dict((v, [n for _, n in adjacent(v)]) for v in xrange(2**N))
best_path = path(0, bfs(edges, MASK))

for pi, p in enumerate(best_path[:-1]):
    print 'the ball can be under cups: %s' % ','.join(str(i+1) for i in xrange(N) if (p>>i)&1)
    print 'lift cup %d' % list(c+1 for c, n in adjacent(best_path[pi]) if n == best_path[pi+1])[0]

0
投票

我认为this riddle接近你提出的问题。但是,它包含5个盒子而不是6个。无论如何,您仍然可以检查他们提出的解决方案并将其策略与您的策略进行比较。

希望能帮助到你。

© www.soinside.com 2019 - 2024. All rights reserved.