Кратчайший путь через упорядоченные круговые точки

Question

Я пытаюсь реализовать алгоритм, который вычисляет кратчайший путь и связанное с ним расстояние от текущей позиции до цели через упорядоченный список путевых точек в 2d плоскости. Путевая точка определяется координатами ее центра (x, y) и радиусом r. Кратчайший путь должен пересекать окружность каждой путевой точки хотя бы один раз . Это отличается от других проблем оптимизации пути, потому что я уже знаю порядок , в котором путевые точки должны пересекаться.

В простом случае последовательные путевые точки различныи не выровнены, и это может быть решено с помощью последовательных угловых делений. Хитрые случаи:

• , когда три или более последовательных путевых точек имеют один и тот же центр, но разные радиусы
• , когда последовательные путевые точки выровнены так, чточерез них проходит прямая линия

Вот урезанная версия моей реализации Python, которая не обрабатывает выровненные путевые точки и обрабатывает плохо концентрические последовательные путевые точки. Я адаптировал его, потому что он обычно использует широты и долготы, а не точки в евклидовом пространстве.

def optimize(position, waypoints):
    # current position is on the shortest path, cumulative distance starts at zero
    shortest_path = [position.center]
    optimized_distance = 0

    # if only one waypoint left, go in a straight line
    if len(waypoints) == 1:
        shortest_path.append(waypoints[-1].center)
        optimized_distance += distance(position.center, waypoints[-1].center)

    else:
        # consider the last optimized point (one) and the next two waypoints (two, three)
        for two, three in zip(waypoints[:], waypoints[1:]):
            one = fast_waypoints[-1]

            in_heading = get_heading(two.center, one.center)
            in_distance = distance(one.center, two.center)
            out_distance = distance(two.center, three.center)

            # two next waypoints are concentric
            if out_distance == 0:
                next_target, nb_concentric = find_next_not_concentric(two, waypoints)
                out_heading = get_heading(two.center, next_target.center)
                angle = out_heading - in_heading
                leg_distance = two.radius
                leg_heading = in_heading + (0.5/nb_concentric) * angle
            else:
                out_heading = get_heading(two.center, three.center)
                angle = out_heading - in_heading
                leg_heading = in_heading + 0.5 * angle
                leg_distance = (2 * in_distance * out_distance * math.cos(math.radians(angle * 0.5))) / (in_distance + out_distance)


            best_leg_distance = min(leg_distance, two.radius)
            next_best = get_offset(two.center, leg_heading, min_leg_distance)
            shortest_path.append(next_best.center)
            optimized_distance += distance(one.center, next_best.center)

    return optimized_distance, shortest_path

Я могу видеть, как проверить для различных угловых случаев, но я думаю, что этот подход плох, потому что может бытьдругие угловые случаи, о которых я не думал. Другой подход заключается в дискретизации окружностей путевых точек и применении алгоритма кратчайшего пути, такого как A *, но это будет крайне неэффективно.

Итак, вот мой вопрос: Есть ли более краткий подход к этой проблеме?

Answer 1

Для справки, я реализовал решение с использованием квазиньютоновских методов и описал его в этой короткой статье . Основная работа обобщена ниже.

import numpy as np
from scipy.optimize import minimize

# objective function definition
def tasklen(θ, x, y, r):
    x_proj = x + r*np.sin(θ)
    y_proj = y + r*np.cos(θ)

    dists = np.sqrt(np.power(np.diff(x_proj), 2) + np.power(np.diff(y_proj), 2))

    return dists.sum()

# center coordinates and radii of turnpoints
X = np.array([0, 5, 0, 7, 12, 12]).astype(float)
Y = np.array([0, 0, 4, 7, 0, 5]).astype(float)
R = np.array([0, 2, 1, 2, 1, 0]).astype(float)

# first initialization vector is an array of zeros
init_vector = np.zeros(R.shape).astype(float)

# using scipy's solvers to minimize the objective function
result = minimize(tasklen, init_vector, args=(X, Y, R), tol=10e-5)

Answer 2

Я бы сделал это так:

1. Для каждого круга по порядку, выберите любую точку на окружности и проложите путь через эти точки.
2. Для каждого круга,переместите точку вдоль окружности в направлении, которое уменьшает общую длину пути.
3. Повторяйте 2., пока дальнейшее улучшение не может быть выполнено.