无限墙算法中的门 [英] Door in an infinite wall algorithm

问题描述

问题：

墙上的门
您正面临着无限延伸的墙在两个方向上。墙上有一扇门，但您既不知道多远，也不知道朝哪个方向。仅在门旁边时，您才能看到门。设计一种算法，使您能够通过最多行走O（n）个步骤来到达门，其中n是初始位置和门之间的（您不知道的）步数。

书中答案：

The此处的主要思想是，每次从初始位置开始以指数方式越远，间歇地向左和向左走。这个想法的简单实现是执行以下操作，直到到达门为止：对于i = 0,1，...，向右移动2 ⁱ 步骤，返回到初始位置，使向左移动2 ⁱ ，然后再次返回到初始位置。令2 ^（k-1）< n≤2 ^k 。此算法需要找到门的步骤数可以按如下估算：

因此，算法执行的步数在O（n）中。 （注意：使用更好的算法来提高乘法常数并不难。

我迷路的地方：

求和时我迷路了。有人可以向我解释总和的工作原理吗？例如为什么他们将2 ^k 和2 < sup> i 分别是4和3？为什么将它与< 7· 2 ^k 进行比较？它等于14· 2 ^（k-1）相比之下是< 14n。我想我得到一个事实，即n = 2 ^（k-1）可以解释总和的末尾但有很多问题。

解决方案

4用于计算代表完整搜索的完整步骤数。因此，假设我们的i = 1。 p>

我们从x = 0开始。我们去2 ^ 1 =2。这是2步。然后回到0。又是2步。然后到-2，然后回到0。总共8步，或 4 x 2 ^ 1

4 x 2 ^ i =不成功的searc中的步骤数h，我们回到原点开始进行较大的搜索，因为我们只能左右移动，而不能传送

kth 迭代是当我们找到门时。最坏的情况是当门位于左侧的 n 处，其中n = 2 ^ k步。

所以

我们从x = 0开始，到右边的2 ^ k，然后回到0，再到左边，我们会发生什么？到-2 ^ k。总共遍历了 3 x 2 ^ k 个步骤。

为什么将其与7 * 2 ^ k进行比较，我们知道 ith 搜索词是 2 ^（k-1）或之前的所有内容。根据先前关于 k-1 vs k

我们也可以在抽象中使用 2 ^ k = 2 x 2 ^（k-1）这一事实。

每个@AbcAeffchen 2 ^（k-1）<应该使用n ，因此您可以用 n 代替 2 ^（k-1）并得到 14 * 2 ^（k−1）< 14n

Question:

Door in a wall You are facing a wall that stretches infinitely in both directions. There is a door in the wall, but you know neither how far away nor in which direction. You can see the door only when you are right next to it. Design an algorithm that enables you to reach the door by walking at most O(n) steps where n is the (unknown to you) number of steps between your initial position and the door.

Answer in book:

The key idea here is to walk intermittently right and left going each time exponentially farther from the initial position. A simple implementation of this idea is to do the following until the door is reached: For i=0,1,..., make 2ⁱ steps to the right, return to the initial position, make 2ⁱ steps to the left, and return to the initial position again. Let 2^(k−1) < n ≤ 2^k. The number of steps this algorithm will need to find the door can be estimated above as follows:

Hence the number of steps made by the algorithm is in O(n). (Note: It is not difficult to improve the multiplicative constant with a better algorithm.

Where I get lost:

I get lost when it gets to the sum. Can someone please explain to me how the sum works?? Like why did they multiply the 2^k and 2ⁱ by 4 and 3? Why are they comparing it to < 7·2^k? How did it equal 14·2^(k-1) which is compared to < 14n. I think I get the fact that n = 2^(k-1) which would explain the last past of the sum but so many questions.

解决方案

The 4 is meant to calculate the number of full steps that represent a full search. So let's says we're at i = 1.

We start at x = 0. We go to 2 ^ 1 = 2. That's 2 steps. Then back to 0. Another 2 steps. Then to -2, then back to 0. A total of 8 steps, or 4 x 2 ^ 1

4 x 2 ^ i = number of steps in an unsuccessful search where we return to the origin to commence a larger search, since we can only traverse left and right, and not teleport

the kth iteration is when we find our door. The worst case is when the door is at n to the left where n = 2^k steps.

So what happens when we get into this iteration?

We start at x = 0, we go to 2^k to the right, then back to 0, then to the left to -2^k. A total traversal of 3 x 2 ^ k steps.

As to why it's compared to 7 * 2 ^ k, we know that the ith search term is 2 ^ (k - 1) or everything before. We can substitute 7*2^k with 7n based on our previous definition regarding k - 1 vs k

And we can also use the fact that 2^k = 2 x 2^(k-1) in our abstractions.

Per @AbcAeffchen 2^(k−1) < n is supposed, so you can substitute 2^(k−1) by n and get 14*2^(k−1) < 14n

这篇关于无限墙算法中的门的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！