寻找最有效路径的算法

Question

你将看到一只昆虫从原点（0,0）开始在平面上移动。只能向东北、东南、西北和西南移动的昆虫。现在的问题是，昆虫在一个方向上一次只能移动特定数量的步。例如，它只能在东北方向移动3步，在东南方向移动4步，在西北方向移动5步，在西南方向移动2步。你知道吗

如果昆虫在一段时间内向NE方向移动了3步-它必须向NW、SE或SW方向移动-然后再向NE方向移动。你知道吗

在这种情况下，如何获得到达给定点的最有效路径？ 我是编程新手，遇到了这个问题。有谁能告诉我解决这类问题的好方法吗？非常感谢。你知道吗

我的想法：

首先，在东北和东南各走一步，在东边走两步。同样，在北边、南边和西边走两步。现在，找到最短路径。基本上，把这个问题变成一个简单的问题，而不是走对角线。（不是个好方法。但是你可以找到一条路。）

第二种方法的灵感来自于用于寻找三维曲线极小值的迭代方法。如果我取消了一次只能朝一个方向行驶的限制，我们可以朝着（四个方向中的一个方向）行驶，这样我们可以更快地到达目的地。这类似于梯度下降法，但只有四个方向移动。你知道吗

欢迎使用Python代码。

Answer 1

TL；DR:最短路径=>；考虑Dijkstra算法。你知道吗

在这里您可以想到一个节点为(Last Move, Position)的图。 计算四个可能的Last Move的最短路径并取最短路径。你知道吗

注意：如果你只关心移动的次数，而不关心移动的距离，那么广度优先搜索更有效。你知道吗

以下是BFS案例的一些代码：

def neighbor(node):
    last, (x,y) = node
    r = []
    for d in ['NE', 'NW', 'SE', 'SW']:
        if d == last:
            continue
        if d == 'NE':
            p = (x+3, y+3)
        if d == 'NW':
            p = (x-5, y+5)
        if d == 'SE':
            p = (x+4, y-4)
        if d == 'SW':
            p = (x-2, y-2)
        r.append((d, p))
    return r

def find_shortest_path(x,y):
    """
    BFS to find the shortest path between (0,0) and (x,y)
    NB: we consider all moves have the same cost
    """
    predecessor = {(None, (0,0)): None}
    queue = [(None, (0,0))]
    while True:
        if not queue:
            return None
        next_queue = []
        for node in queue:
            for n in neighbor(node):
                if n not in predecessor:
                    predecessor[n] = node
                    last, (u,v) = n
                    if (u,v) == (x,y):
                        backtrack = []
                        while n in predecessor:
                            backtrack.append(n)
                            n = predecessor[n]
                        return list(reversed(backtrack))
                    next_queue.append(n)
        queue = next_queue

如果目标真的很远，你可以使用通常的改进方法：双向搜索，A*算法和一些启发式算法，等等

Answer 2

    """You are given an insect moves in a plane starting from the original point (0,0).
The insect that can only move toward North-East, South-East, North-West, & South-West.
Now the thing is insect can't move more than a specific number of steps at a time in one direction.
For example, it can move only 3 steps in NE, 4 steps in SE, 5 steps in NW and 2 steps in SW.
If the insect moves 3 steps in direction NE at a stretch- it has to move NW, SE, or SW-
before again going in direction NE."""

"""Assumption say the insect moves in the plane from (-100,-100) to (100, 100) size plane
    North is Positive y-cord
    South is Negative y-cord
    East is Positive x-cord
    West is  Negative x-cord """


def walk_ne():
    max_ne = 3
    global x_curr
    global y_curr
    global x_home
    global y_home
    global walked_ne
    global walked_nw
    global walked_se
    global walked_sw
    walked_ne = walked_nw = walked_sw = walked_se = False
    walked_ne = True
    for i in range(max_ne):
        if x_curr < x_home and y_curr < y_home:
            x_curr += 1
            y_curr += 1
        elif x_curr == x_home and (y_curr + 1) < y_home:
            x_curr += 1
            y_curr += 1
            break
        elif y_curr == y_home and (x_curr + 1) < x_home:
            x_curr += 1
            y_curr += 1
            break
        # else:
        #     print("Cond did not meet")


def walk_nw():
    max_nw = 5
    global x_curr
    global y_curr
    global x_home
    global y_home
    global walked_ne
    global walked_nw
    global walked_se
    global walked_sw
    walked_ne = walked_nw = walked_sw = walked_se = False
    walked_nw = True
    for i in range(max_nw):
        if x_curr < x_home and y_curr > y_home:
            x_curr += 1
            y_curr -= 1
        elif x_curr == x_home and (y_curr - 1) > y_home:
            x_curr += 1
            y_curr -= 1
            break
        elif y_curr == y_home and (x_curr + 1) < x_home:
            x_curr += 1
            y_curr -= 1
            break
        # else:
        #     print("Cond did not meet")


def walk_se():
    max_se = 4
    global x_curr
    global y_curr
    global x_home
    global y_home
    global walked_ne
    global walked_nw
    global walked_se
    global walked_sw
    walked_ne = walked_nw = walked_sw = walked_se = False
    walked_se = True
    for i in range(max_se):
        if x_curr > x_home and y_curr < y_home:
            x_curr -= 1
            y_curr += 1
        elif x_curr == x_home and (y_curr + 1) < y_home:
            x_curr -= 1
            y_curr += 1
            break
        elif y_curr == y_home and (x_curr - 1) > x_home:
            x_curr -= 1
            y_curr -= 1
            break
        # else:
        #     print("Cond did not meet")


def walk_sw():
    max_sw = 2
    global x_curr
    global y_curr
    global x_home
    global y_home
    global walked_ne
    global walked_nw
    global walked_se
    global walked_sw
    walked_ne = walked_nw = walked_sw = walked_se = False
    walked_sw = True
    for i in range(max_sw):
        if x_curr > x_home and y_curr > y_home:
            x_curr -= 1
            y_curr -= 1
        elif x_curr == x_home and (y_curr - 1) > y_home:
            x_curr -= 1
            y_curr -= 1
            break
        elif y_curr == y_home and (x_curr - 1) > x_home:
            x_curr -= 1
            y_curr -= 1
            break
        # else:
        #         #     print("Cond did not meet")


x_curr = 0  # Current x location of insect
y_curr = 0  # Current y location of insect

x_home = int(input('home x cordinates (Integer between -100 to 100)'))
y_home = int(input('home y cordinates (Integer between -100 to 100)'))

walked_ne = walked_se = walked_nw = walked_sw = False

if (x_home + y_home) % 2 != 0:
    print('Nearest the insect can go to given coordinates is ({} {}) '
          'Because insect can only move in diagonal'.format(x_home-1, y_home))
    x_home -= 1

while x_home != x_curr and y_home != y_curr:
    if x_curr < x_home:
        if y_curr < y_home:
            if not walked_ne:
                walk_ne()
            else:
                x_curr += 1
                y_curr -= 1
                walked_ne = False
                walked_nw = True

        else:
            if not walked_nw:
                walk_nw()
            else:
                x_curr += 1
                y_curr += 1
                walked_nw = False
                walked_ne = True
    else:
        if y_curr < y_home:
            if not walked_se:
                walk_se()
            else:
                x_curr -= 1
                y_curr -= 1
                walked_se = False
                walked_sw = True
        else:
            if not walked_sw:
                walk_sw()
            else:
                x_curr -= 1
                y_curr += 1
                walked_sw = False
                walked_se = True
    if x_curr == x_home and y_curr != y_home:
        if y_curr < y_home:
            if not walked_ne:
                walk_ne()
            elif not walked_se:
                walk_se()
        else:
            if not walked_nw:
                walk_nw()
            elif not walked_sw:
                walk_sw()
    elif x_curr != x_home and y_curr == y_home:
        if x_curr < x_home:
            if not walked_ne:
                walk_ne()
            elif not walked_nw:
                walk_nw()
        else:
            if not walked_se:
                walk_se()
            elif not walked_sw:
                walk_sw()
    print(x_curr, y_curr)