刷量化题中求大神帮忙

先抱歉一下，我太弱了麻烦大家帮忙。正在刷量化题应付面试，但是有道题不会，如下

You are standing in a vast, flat desert on a moonless night. It is foggy, overcast, and raining hard. You are one mile from the only road, which is perfectly straight and infinitely long in both directions. You can’t see the road until you are right on top of it. What is your strategy for finding the road with minimum hiking in the worst case?

怎么感觉这道题限定条件挺少的，都不知道怎么出发。总之先跪谢了！

补充内容 (2023-06-20 22:17 +08:00):

我已经找到解了，大家可以去网上搜这个问题的最原始名字叫Bellman's lost in a forest problem

nyufufu 发表于 2023-6-20 17:44
往任意方向走 1 mile 然后绕原点走一圈吧。

我最开始也是这么想的，但这个应该是最差的方法，我找到解了，你可以搜Bellman's lost in a forest problem

往任意方向走 1 mile 然后绕原点走一圈吧。

Finding the road in the scenario you've described is primarily a navigation problem, and it requires some knowledge of geometry. In a situation like this, where visibility is essentially zero, the best strategy involves a well-defined, systematic search pattern. Here's a potential method you could use:

Pick a direction and start walking straight. It doesn't matter which direction; let's say you walk north.

After walking one mile, if you haven't found the road, turn 90 degrees to your right (which is east).

Walk for one mile in the east direction.

Now, turn 90 degrees to your right again (this will make you face south), and walk for two miles. This will put you one mile south of your original position, and one mile east.

.1point3acresTurn 90 degrees to your right again (you'll be facing west), and walk for three miles.

Turn 90 degrees to your right (facing north), and walk for four miles.

You're essentially following a spiral search pattern, where each leg of your journey is one mile longer than the previous. This method ensures that you'll eventually cross the road. In the worst-case scenario, you'd walk approximately 2 miles because the road could be just to your east or west, but you started by walking north. However, the average distance will be much less than this.

It's also important to note that this method assumes you can maintain a straight line and keep track of the distance you've traveled, which could be challenging in poor visibility conditions. It would be helpful if you had a compass or another method of maintaining your bearing, as well as a pedometer or other way to estimate distance. If you had no tools at all, you would have to rely on other navigation skills, such as recognizing changes in terrain or wind direction, to help you keep a straight line.

微信用户_de75404 发表于 2023-06-20 07:44:14
Finding the road in the scenario you've described is primarily a navigation problem, and it requires

一眼gpt

summeryanxi 发表于 2023-06-20 07:16:08
我最开始也是这么想的，但这个应该是最差的方法，我找到解了，你可以搜Bellman's lost in a forest problem

求解释，Bellman's lost in a forest的简化版本？哪里有解法没找到

补充内容 (2023-06-21 16:35 +08:00):
绕一圈也就3.1mile，真有最坏情况下小于等于4mile的方案？

任意时刻以知区域是曾去过的点的convex hull. 找到这个convex hull 的过当前点的最长边。行进方向应该与之垂直。这样可以得到一个微分方程。解我猜是一个螺线。