一种以尽可能少的步数找到运动目标的算法
我想解决以下问题：
一排有6个杯子(比方说编号1到6)。其中一个杯子下面是一个球(我不知道是哪个)。我可以举起一个杯子，看看球是否在那里。如果是的话我赢了。如果不是，球就会从它当前的位置移动到一个杯子的左边或右边(所以从第4杯移到第3杯或第5杯。从第6杯它只能移动到第5杯)。球必须移动，不能停留在原地。
问题是:如果你使用最优的策略，在多少“杯举”之后，你会知道球的位置。
目前，我已经提出了一个最坏的6起电梯的策略。请注意，最后的升力，“证明”的地方，球，不需要做。我的问题是:有没有更好的“最坏情况”的算法？如果不是，我如何证明这是最好的算法？
我目前的策略。我们假设开始时球在一个平杯下(so _ 2，4或6)。我最坏的情况一步一步的发生如下。
Lift 1：举起杯2号，球不在那里。根据我们的假设，球会移动到一个奇怪的杯子，但它不可能移动到第一杯(因为它必须起源于第二杯，但它没有)
Lift 2：举杯3号。球不在那里。我不可能在1以下(见上面)，它不低于3，并且假设它在一个奇怪的杯子下面。这意味着它现在在杯5下，因此必须移动到杯4或6。
升降机3:升降杯4号，球不在那里。这意味着它一定是移到了6号杯，所以在下一个动作中，它必须移动到第5号杯。
举起4:提升杯5号，球不在那里。这是唯一的可能，所以我们错误地猜测它是从一个平杯开始的。因此，它现在是在一些偶数杯，并将移动到一个奇怪的杯子在下一个移动。我们现在工作的过程是相同的，但反过来。
Lift 5:升降杯号5(再次)。球不在那里。根据新的假设，球现在将移动到杯2或4(同样，它不能移动到第6杯，因为它没有低于5)。
Lift 6:升降杯4号。它不在那里，所以它必须在2号杯下(它在均匀杯下，而不是在6或4下面)。因此，我们知道杯子在哪里(即使我们没有完成第二杯的最后升力)。
回答 3
Stack Overflow用户
发布于 2017-12-22 04:37:08
你的算法有一个缺陷。如果球以一个奇数的位置开始，那么在偶数移动之后，球就会以一个奇数的位置结束。您的算法假设它在六次移动后处于偶数位置。那是行不通的。此外，你的电梯顺序并不能确定球在哪里。
例如，假设球从杯#1下开始，按照您的电梯顺序，下面是可能的。
- 举起杯子2。球移动到杯2。
- 举起杯3。球移到杯1。
- 举起杯子4。球移到第2杯。
- 举起杯子5。球移动到杯1。
- 举起杯子5(再次)。球移到第二杯。
- 举起杯子4。球移动到杯1。
在第6步之后，球可以从杯2移动到杯1或杯3，所以你不知道它在哪里。
Stack Overflow用户
发布于 2017-12-27 09:48:25
如果你想用一个程序来解决这个问题，你可以构造一个图，其中顶点是球可能存在的位置的集合，而边是杯形凸起物，结果不会显示一个球。然后，一个解决方案是一个最短的路径，从你想要的任何开始状态到任何状态，有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]Stack Overflow用户
发布于 2017-12-26 11:49:38
我认为这个谜语已经接近你提出的问题了。然而，它包含5个框而不是6个。无论如何，您仍然可以检查他们提出的解决方案，并将他们的策略与您的策略进行比较。
希望能帮上忙。
https://stackoverflow.com/questions/47929797
复制相似问题
腾讯云开发者
