Местные оптимумы в электрических заборах - PullRequest
Новая
       42

Местные оптимумы в электрических заборах

2 голосов
/ 13 февраля 2010

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

У меня была идея, что можно было бы сделать холм, и это работало для всех тестовых случаев. В данном анализе использовался аналогичный метод, но он не объяснил, почему это будет работать.

Таким образом, я до сих пор не могу ни доказать, ни опровергнуть существование локальных оптимумов в данных задачах. У меня была идея, что это можно сделать с помощью индукции, но я не смог заставить ее работать. Вы можете мне помочь?

Обновленное определение

По заданному набору (x1, y1, x2, y2) линейных сегментов найдите (x, y) точку P, которая минимизирует функцию: 

def Val(x,y):
    d = 0
    for x1,y1,x2,y2 in LineSegments:
        if triangle (x1,y1,x2,y2,x,y) is not obtuse in (x1,y1) or (x2,y2):
            d += DistPointToLine(x,y,x1,y1,x2,y2)
        else:
            d += min(DistPointToPoint(x,y,x1,y1), DistPointToPoint(x,y,x2,y2))
    return d

По какой-то причине проблема содержит только одну локальную оптимуму, и поэтому для ее решения может быть использована следующая процедура: 

precision = ((-0.1,0), (0.1,0), (0,-0.1), (0,0.1))
def Solve(precision=0.1):
    x = 0; y = 0
    best = Val(x,y)
    while True:
        for dx,dy in precision:
            if Val(x+dx, y+dy) > best:
                x += dx; y += dy
                best = Val(x,y)
                break
        else:
            break
    return (x,y)

Вопросы: Почему это не застревает где-то на пути к глобальному оптимуму? Почему нет местных вершин холмов, чтобы поставить эту наивную процедуру на колени?

1 Ответ

3 голосов
/ 24 февраля 2010

Нетрудно доказать правильность алгоритма, если заметить, что функция расстояния для одного отрезка прямой является выпуклой функцией . Выпуклый в этом случае означает, что если мы будем думать о функции расстояния как о поверхности z = f (x, y), то, если бы мы заполнили объем над поверхностью, у нас было бы выпуклое тело. В случае расстояния от одного отрезка, тело будет выглядеть как треугольный клин с коническими концами.

Поскольку сумма выпуклых функций также является выпуклой , то сумма расстояний от нескольких отрезков также будет выпуклой функцией. Следовательно, любой найденный вами локальный минимум также должен быть глобальным минимумом в силу выпуклости функции.

...