停车场搜索算法 [英] Parking Lot Search Algorithm

问题描述

我有一条无限长的街道，上面停着汽车。但是，我在任何地方都看不到免费停车场，但我知道在可以停车的地方肯定有一个免费停车位。目的是走最短的路，我只能向左或向右走。

假设我知道免费停车场在哪个方向，我会直接开车去那儿方向，这样我就可以通过 A停车场了。

现在，我需要一种算法，该算法需要通过不超过10 * A的停车场才能找到免费的停车场。然后我从我家门前开始... A不为人所知。

我首先将街道视为一个阵列，而停放的汽车是其中的元素的数组。真表示空白，假表示已被占用。搜索完成，直到发现布尔值为true。那将是我的基本想法。但是最重​​要的是搜索是如何完成的。

我可能会选择一种方法，然后再进行两倍的循环，所以我得到了类似的结果：1，-2，4，-8，16，...直到找到空位。

但是我不确定是否可以解决小于10 * A ...

解决方案

让我们应用您指定的一种算法，并持续到空找不到停车场：

1. 向左行驶，直到起点左侧的停车场1，然后返回起点；


2. 向右转到起点右侧的第2个停车场，然后回到起点；


3. 向左行驶，直到左侧的第4个停车场起点，然后回到起点；


4. 右转到起点右边的第8号停车场，然后回到起点；

因此，在步骤 n ，您将首先转到 2 < sup> n-1 距离起点很远，并且向后移动相同的距离，因此在这一步中，您总共走了 2 ⁿ

考虑上一步中的行驶距离，使得在步骤 n 之后，总距离为Σ< sub> i = 1..n （2 ⁱ ），即 2 ^{n + 1} -2 。

因此，如果免费停车场距离起点 A 很多，那么将在步骤 ceil中访问该停车场。 （logA）+1 ，如果我们对这一面感到幸运的话，或者是一步之后，即在步骤 ceil（logA）+2 中。

因此，在最坏的情况下（第二个），总行进距离是步骤 ceil（logA）+1 的行距，再加上剩下的步骤来获得批次 A 从最后一步的起点开始（会被打断）。这就是 2 ^{（ceil（logA）+1）+1} -2 ，（这是 4A-2 和 8A-3 ）和 A 。小于 9A-2 ，因此可以满足要求。

I got a street with an infinite length which is parked with cars. However I cannot see a free parking lot anywhere but I know that there must be exactly one free spot somewhere where I can park my car. The aim is to take the shortest way and I can only go left or right.

Assuming I knew in which direction the free parking lot is, I would directly drive to that direction and thereby I would pass "A" taken parking lots.

Now I need an algorithm that needs to pass no more than 10*A parking lots to find a free parking lot. And I start in front of my home... "A" is not known.

I would begin by seeing the street as an array and the parked cars are the elements of the array. True signifies an empty spot and false means it is occupied. The search is done till that boolean value is found to be true. That would be my basic idea. But what's more important than that is how is the search done.

I would maybe go one way, then twice as far the other way, loop, so I got something like: 1, -2, 4, -8, 16,... till I found the empty spot.

But I'm not sure if it would be solved in less than 10*A...

解决方案

Let's apply a kind of algorithm as you indicated and continue for as long as the empty parking lot has not been found:

1. Go left until parking lot 1 at the left of the starting point and go back to starting point;
2. Go right until parking lot 2 at the right of the starting point and go back to starting point;
3. Go left until parking lot 4 at the left of the starting point and go back to starting point;
4. Go right until parking lot 8 at the right of the starting point and go back to starting point;

So at step n, you will first go 2^n-1 lots away from the starting point, and travel the same distance back, so in that step you travel a total of 2ⁿ lots.

Taking the distance travelled during the previous steps, that makes that after step n that total distance is Σ_i=1..n (2ⁱ), which is 2ⁿ⁺¹ - 2.

So if the free parking lot is A lots away from the starting point, then that lot will be visited in step ceil(logA)+1 if we are lucky about the side, or else one step later, i.e. in step ceil(logA)+2.

So taking the worst case (the second), the total travelled distance is the one for step ceil(logA)+1, plus the remaining steps to get to lot A from the starting point during the last step (which gets interrupted). That comes to 2^{(ceil(logA)+1)+1} - 2, (which is a value between 4A-2 and 8A-3) plus A. That is less than 9A-2, and thus meets the requirement.

这篇关于停车场搜索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！