11

このアルゴリズムの問​​題について質問があります。問題を貼り付けてから、現在の考えと解決策を確認します。

N (up to 100,000)、として定義された線分があります[(x1, y1), (x2, y2)]。ここで、x1 < x2およびy1 < y2（たとえば、線分は正の勾配を持っています）。端点であっても、線分が接触したり交差したりすることはありません。最初のセグメントには(x1, y1) = (0, 0)。各セグメントを、人が登らなければならない2Dの丘として想像してください。

人(0, 0)は最初の丘から始めて着陸します。人が丘に着陸するときはいつでも、彼は最後まで登ります、それは(x2, y2)まっすぐにジャンプします。彼が別の丘（セグメントのどこかに）に着陸した場合、プロセスは続行されます。彼はその丘を登ってジャンプします。丘がもうない場合、彼は倒れ-INFINITY、プロセスは終了します。各丘は、ポイントを含むがポイントを含まない(x1, y1) -> (x2, y2)と見なす必要があります。これにより、人が上の位置で上から落下した場合は丘に着陸しますが、から落下した場合は丘に着陸しません。上記の。(x1, y1)(x2, y2)x = x1x = x2

目的は、彼が触れた丘の数を数えることです。

私の現在の考え

x軸に沿って平面を横切る線をスイープすることを考えています。各セグメントは、BEGINイベントとENDイベントで構成されます。線分の始まりに遭遇するたびに、それをセットに追加します。線分の終わりに遭遇するたびに、それをセットから削除します。そして、現在の丘の終点に到達したら、着陸できる最も高い丘のセットを確認する必要があります。ただし、セット内にN個のエントリが存在する可能性があるため、これをすばやく確認する方法を判断する方法がわかりません。また、別の丘にジャンプした後は、各セグメントの傾斜が異なる可能性があるため、これらの順序が変更されます。この違いを説明する方法がわかりません。

何かご意見は？

4

4 に答える 4

1

バロンさん、あなたのアルゴリズムは完全に正しいです。スイープ ラインが移動しても、並べ替えられたリスト内の要素の順序は変わりません。

ソートされた線分を追跡する方法が必要なだけです。これを行う 1 つの方法は、ライン セグメントのマップを保持することです。比較演算子は、現在のスイープ位置の現在の x 値によって計算されるセグメントの y 値によってライン セグメントを比較します。このマップからの挿入、削除、クエリは O(log(n)) です。

于 2014-05-23T09:02:40.997 に答える
1

前処理では、すべてのセグメントをトラバースし、stl multimap< pair, linesegment> または同様のものにポイントを追加できます。この前処理のコストは O(NlogN) になります。その後、スイープ ライン メソッドを続行できます。マルチマップからポイントを反復する必要があります。すべてのポイントがソートされ、ポイントが対応する行への参照が含まれているため、O(N) のコストがかかります。

于 2014-03-19T05:14:16.293 に答える
0

ここでは、ラインスイープアルゴリズムが良いアイデアだと思います。これまでのアルゴリズムを要約し、私の改善点を追加しましょう。

  • 線を左から右にスイープしています。
  • 現在アクティブなすべてのセグメントを一覧表示するアクティブリストがあります。これらはスイープラインと交差するセグメントです
  • すべての線分のすべての端点は「イベント」と見なされます
  • 線がセグメントの「開始」を横切ってスイープすると、そのセグメントはアクティブなセグメントのリストに追加されます
  • 線がセグメントの「端」を横切ってスイープすると、そのセグメントはアクティブなセグメントのリストから削除されます
  • ラインセグメントの削除時にアクティブセットにラインセグメントがない場合、プロセスは終了します
  • 線分を削除したときにアクティブセットに線分がある場合は、次のことを確認する必要があります。
    • A）以前に削除された終了頂点の「下」に部分があるアクティブセットに線分があるかどうか。
    • B）これらの線分のどれに人が着陸するか。

アイデアは、このクエリが効率的になるように、「アクティブセット」内の線分を並べ替えることです。私が考えているのは、線の傾きとy切片がわかっていれば、開始頂点のx位置の交点を計算できるということです。

GreaterThan(segment1,segment2){ // is segment 1 higher than segment 2?
//y = mx + b; compute y value of point on segment 2 for a given x value from s1
//that is, m and b are slope and y-intercept of s2
yVal = m * (segment1.first.x) + b
if (yVal < segment1.first.y)
   return true //the point on s2 corresponding to s1.first is lower than s1.first
return false
}

線は交差しないため、他の線がこの線を「通過」しないと想定できます。

開始頂点が「人」の現在の線の終了頂点よりも高い線分を追加しない場合は、アクティブセットに無関係な線分を追加しないようにする必要があります（つまり、現在の線の「上」にある線分）。

ここで、最後の線分の頂点が「着陸可能」でないという特殊なケースについて心配する必要があります。頂点はイベントであるため、セグメントテストを実行する前にすべてのイベントを処理します。このようにして、アクティブセット内のラインの端の頂点に誤って着地することはありませんが、追加されたばかりのラインセグメントに着地します。

アクティブセット内のラインセグメントの並べ替えられたリストができたので、一定時間でクエリを実行して一番上のラインセグメントを取得できます。新しいラインセグメントを追加するには、対数時間しかかかりません。

これはどのように聞こえますか？

于 2013-03-09T03:25:40.443 に答える
0

これが Haskell の大まかな方向性です。「セグメント」は線分です。(この例では、コードをテストするために、3 番目のセグメントは 2 番目のセグメントのわずかに上にあります。) "matches" は、最後のセグメント pt (x0,y0) の上部を x 境界内に配置する丘/セグメントを見つけます。 x0 のアフィン変換に対応する y 以上 (「アフィン」は、セグメントのアフィン関数、いわば ax+b を計算します)。最後に、countHills は次の丘の可能な一致をテストし、y が y0 (アフィン a*x0+b によって計算) に最も近いものを選択し、登った丘を順番に累積して結果を出力します。明らかに、このアイデアは、はるかに長いセグメント リストの最適化が必要になる場合があります。

以下の結果出力は、1 番目と 3 番目のセグメントを示しています。

2 番目の丘/セグメントは 3 番目よりも低いため、結果には含まれません - 代わりに 3 番目に着陸します
。 ),(5.0,3.0))]

import Data.List

segments = [((0,0),(2,5)),((1,1),(5,2)),((1,1.5),(5,3))]

top segment = snd segment

matches pt = 
  let x0 = fst pt 
      y0 = snd pt
  in filter (\x -> x0 >= fst (fst x) 
                   && x0 < fst (snd x) 
                   && (affine x) x0 <= y0) segments  

affine segment = 
  let x1 = fst $ fst segment
      y1 = snd $ fst segment
      x2 = fst $ snd segment
      y2 = snd $ snd segment
  in (+ ((x1*y2-x2*y1) / (x1-x2))) . (* ((y2-y1) / (x2-x1)))

countHills segments = countHills' (head segments) [] where
  countHills' x result = 
    let hills = matches $ top x
        x0 = fst (top x)
        y0 = snd (top x)
    in if null hills 
          then result ++ [x]
          else let nextHill = 
                     minimumBy (\a b -> compare 
                                        (y0 - (affine a) x0) 
                                        (y0 - (affine b) x0)) hills
               in countHills' nextHill (result ++ [x])
于 2013-03-09T04:10:51.800 に答える