2

ウサコ問題「電気柵」の解法を書いています。この問題では、大量の線分の中から点の最適な位置を見つける必要があるため、点と線分の間の距離の合計は可能な限り小さくなります。

ヒルクライムを実行できる可能性があるという考えがあり、すべてのテストケースで機能しました。与えられた分析では同様の方法が使用されましたが、なぜこれが機能するのかは説明されていませんでした。

したがって、与えられたタスクにおける局所最適の存在を証明することも反証することもできません。誘導を使用して実行できるという考えがありましたが、機能させることができませんでした。手伝って頂けますか？

更新された定義

(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

なんらかの理由で、問題には局所最適値が 1 つしか含まれていないため、次の手順を使用して解決できます。

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)

問題は次のとおりです。なぜこれは、グローバルな最適状態に向かう途中で行き詰まらないのでしょうか? この素朴な手順を屈服させる地元の丘の頂上がないのはなぜですか?

4

1 に答える 1

3

単一の線分の距離関数が凸関数であることに気付いた場合、アルゴリズムの正しさを証明するのは簡単です。この場合の凸とは、距離関数を曲面 z=f(x,y) と考えた場合、曲面の上のボリュームを埋めると、凸型の立体になることを意味します。1 つの線分からの距離の場合、ソリッドは円錐形の端を持つ三角形のくさびのように見えます。

凸関数の和も凸なので、複数の線分からの距離の和も凸関数になります。したがって、見つけた局所的最小値は、関数が凸であるため、大域的最小値でもある必要があります。

于 2010-02-24T20:01:34.047 に答える