0

この問題は、ACMICPCカンプール地域排除ラウンドで提起された問題のサブ問題です。

(Pa, Pb)2Dポイントと(Pc, Pd)それぞれで囲まれた2つの線分が与えられた場合、関数を最小化するpとq（範囲内）を見つけます。[0,1]

f(p, q) = D(Px, Pa) + D(Py, Pd) + k D(Px, Py) where 
                                2 <= k <= 5, 
                                Px = p Pa + (1-p) Pb, 
                                Py = q Pc + (1-q) Pd and 
 D(x, y) is the euclidean distance between points x and y

（事実上、PxとPyは線分上の点であり、関数は、ユークリッド距離のk倍のコストの接続リンクを介してPaからPdに移動するコストをエンコードします）

この機能に関するいくつかの所見：

  1. 平行線分は常に、との少なくとも1つを0または1のいずれかにしますp。q
  2. 交差する線分は常に線分の交点を引き起こしp、q位置を特定します（これを証明するために三角不等式を適用できます）

質問：線が傾斜していて潜在的に分離している一般的なケースでは、この関数を最小化するにはどうすればよいですか？

4

1 に答える 1

1

fとに関する偏導関数を取り、pそれらを0に設定し、とqを解くことができるはずです。それはあなたに（ローカル）最小値を与えるでしょう。最小値にとがある場合は完了です。そうでない場合は、4つのエンドポイント（など）を確認してください。pq0 <= p <= 10 <= q <= 1p=0,q=1

これですべての縮退状態が処理されるとは思いませんが、良いスタートになるはずです。

于 2010-10-30T22:03:43.050 に答える