时间戳

首页 > 解决方案 > 机器人可以到达一个点（x，y）吗？

algorithm - 机器人可以到达一个点（x，y）吗？

问题描述

我在一次工作面试中遇到了这个问题，我找不到解决方案的正确算法，所以我在这里发布这个问题：

有一个机器人可以在坐标平面上以两种方式之一移动：

假设机器人当前位置是 (x,y)，如果方向如下，机器人可以移动等于 x 和 y 之和：

(x,y)  ->  (x+y, y)
(x,y)  ->  (x, x+y)

现在给定一个初始点 (x1, y1) 和一个目标点 (x2, y2)，您需要编写一个程序来检查机器人是否可以通过任意数量的移动到达目的地。

注意：x1, y1, x2, y2 > 0

解释：

  1. 假设机器人的初始点是 (2,3)，目的地是 (7,5)

    这种情况下的结果是肯定的，因为机器人可以走这条路：

    (2,3) -> (2, 2+3) => (2, 5)

    (2,5) -> (2+5, 5) => (7,5)

  2. 假设机器人的初始点是 (2,3)，目的地是 (4,5)

    在这种情况下，结果为“否”，因为无论机器人采用何种路径，它都无法到达 (4,5)

标签： algorithmcoordinates

解决方案

一种天真的蛮力方法

一种方法是递归地探索每一个可能的动作，直到你达到目标。

需要考虑的是机器人可以无限期地继续移动（永远不会到达目标），因此您需要一个终端案例才能完成功能。幸运的是，位置总是在x和y轴上增加，所以当 x 坐标或 y 坐标大于目标时，您可以放弃探索该路径。

所以像：

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if pos[0] > target[0] or pos[1] > target[1]: 
        return False
    return can_reach_target((pos[0], sum(pos)), target) or \
           can_reach_target((sum(pos), pos[1]), target)

它有效：

>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False

一个限制是这不适用于负坐标 - 不确定这是否是必需的，请告诉我是否需要，我会调整答案。

回溯

另一方面，如果不允许使用负坐标，那么我们也可以按照Dave 的建议进行处理。这更有效，因为实现是机器人到达每个坐标的方式只有一种。

该方法依赖于能够确定我们步进的方式：增加 x 坐标或 y 坐标。我们可以通过选择两者中的较大者来确定上次更改的坐标。下面的证明保证了这种情况。

状态改变的可能性是：

1. (a, b) => (a+b, b)       a x-coordinate change

和，

2. (a, b) => (a, a+b)       a y-coordinate change

在情况 (1) 中，x 坐标现在更大，因为：

    a > 0
a + b > b  (add b to both sides)

同样，由于bis also > 0，我们可以推断a+bis > a。

现在我们可以从目标开始问：是哪个坐标把我们带到这里的？答案很简单。如果 x 坐标大于 y 坐标，则从 x 坐标中减去 y 坐标，否则从 y 坐标中减去 x 坐标。

也就是说，对于一个坐标，(x,y)，如果x > y，那么我们来自(x-y,y)else (x,y-x)。

第一个代码现在可以适应：

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if target[0] < pos[0] or target[1] < pos[1]: 
        return False
    x, y = target
    return can_reach_target(pos, (x-y,y) if x > y  else (x,y-x))

按预期工作：

>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False

计时

>>> timeit.timeit('brute_force((2,3),(62,3))',globals=locals(),number=10**5)
3.41243960801512
>>> timeit.timeit('backtracker((2,3),(62,3))',globals=locals(),number=10**5)
1.4046142909792252
>>> timeit.timeit('brute_force((2,3),(602,3))',globals=locals(),number=10**4)
3.518286211998202
>>> timeit.timeit('backtracker((2,3),(602,3))',globals=locals(),number=10**4)
1.4182081500184722

所以你可以看到回溯器在这两种情况下都快了近三倍。

推荐阅读