3

タイプdoubleのクラスを考えてみましょう

class path_cost {
   double length;
   double time;
};

のリストを辞書式順序で注文したい場合path_costs、問題があります。読む ：）

私がそのように同等性テストに完全に等しいを使用する場合

bool operator<(const path_cost& rhs) const {
   if (length == rhs.length) return time < rhs.time;
   return length < rhs.length;
}

わずかな偏差（たとえば、長さの計算における数値の不正確さによる）により、長さテストが失敗する可能性があるため、結果の順序は間違っている可能性があります。

{ 231.00000000000001, 40 } < { 231.00000000000002, 10 }

誤って保持します。

代わりにそのような公差を使用する場合

bool operator<(const path_cost& rhs) const {
   if (std::fabs(length-rhs.length)<1-e6)) return time < rhs.time;
   return length < rhs.length;
}

次に、<演算子が推移的ではなくなったため、並べ替えアルゴリズムがひどく失敗する可能性があります（つまり、a<bおよびb<cの場合、a <cは成り立たない可能性があります）

何か案は？ソリューション？実数直線を分割して、各パーティション内の数が等しいと見なされるようにすることを考えましたが、それでも、同等性テストが失敗するが、失敗しない場合が多すぎます。

（James Curranによる更新、うまくいけば問題を説明します）：数字を考えると：

  • A = {231.0000001200、10}
  • B = {231.0000000500、40}

  • C = {231.0000000100、60}

    • A.LengthとB.Lengthは7-e7異なるため、時間を使用し、A<Bです。
    • B.LengthとC.Lengthは4-e7だけ異なるため、時間を使用し、B<Cです。
    • A.LengthとC.Lengthは1.1-e6異なるため、長さを使用し、A>Cです。

（Esben Mose Hansenによる更新）これは純粋に理論的なものではありません。非推移的なソート演算子を指定すると、標準のソートアルゴリズムがクラッシュするか、悪化する傾向があります。そして、これはまさに私が争っていたものです（そして男の子はデバッグするのがとても楽しかったです;））

4

5 に答える 5

4

比較機能だけが本当に必要ですか？

最初に長さで並べ替えてから、ペアを同じ長さであると思われるグループにグループ化し、各グループ内で時間で並べ替えてみませんか?

長さで並べ替えたら、必要なヒューリスティックを適用して、長さが「等しい」かどうかを判断し、グループ化を行うことができます。

于 2010-07-14T17:14:50.380 に答える
1

あなたがやりたいことができるとは思えません。本質的には、特定のケースでは a>b という事実を無視して a=b のふりをしたいと言っているようです。差が特定の値よりも小さい場合に a と b が等しい場合、a と b のすべての値に対して a と b が等しいという証明を構築できると確信しています。次のようなもの：

C と 2 つの数値 A と B の許容誤差に対して、一般性を失うことなく A > B の場合D(n) = B+n*(C/10)、0<=n<=(10*(A-B))/(C)自明に D(n) が D(n-1) と D(n+1) の許容誤差内にあり、したがって、それらに相当します。また、D(0) は B であり、D((10*(AB))/(C))=A なので、A と B は等価であると言えます。

その問題を解決できる唯一の方法は、パーティショニング方法を使用することだと思います。10^6 を掛けてから int shoudl パーティションに変換するようなものはかなりうまくいきますが、1.00001*10^-6 と 0.999999*10^-6 がある場合、それらは異なるパーティションに出力され、望ましくない可能性があります。 .

問題は、あなたのデータを調べて、それを最適に分割する方法を見つけることになります。私はあなたのデータについて何も知らないので、私は助けることができません. :)

PSアルゴリズムは、アルゴリズムが与えられたとき、または特定の解決できないケースに遭遇したときに実際にクラッシュしますか?

于 2010-07-14T15:06:43.503 に答える
1

私は2つの解決策を考えることができます。

比較が非推移的な場合に失敗しないソート アルゴリズムを慎重に選択できます。たとえば、少なくとも自分で実装した場合は、クイックソートが失敗することはありません。(クイックソートの最悪の場合の動作が心配な場合は、最初にリストをランダム化してから並べ替えることができます。)

または、トレランス パッチを拡張して等価関係になり、推移性を復元することもできます。等価関係との関係を完成させるための標準的な共用体検索アルゴリズムがあります。union-find を適用した後、各等価クラスの長さをコンセンサス値 (平均など) に置き換えてから、必要な並べ替えを行うことができます。偽の並べ替えを防ぐために浮動小数点数を医者にするのは少し奇妙に感じますが、うまくいくはずです。

実際、モロンは良い点を指摘しています。結合して検索する代わりに、最初に長さで並べ替えてから、許容範囲内にある近傍をリンクしてから、2 番目のキーの各グループ内でサブ並べ替えを行うことができます。これは私の 2 番目の提案と同じ結果になりますが、より単純な実装です。

于 2010-07-14T15:34:23.930 に答える
0

通常の s では 100% の精度を得ることはできませんdouble。あなたは、公差を使用するとプログラムの正確さに影響が及ぶことを恐れていると言っています。これを実際にテストしましたか？プログラムに実際に必要な精度のレベルは?

1e-9ほとんどの一般的なアプリケーションでは、十分な許容範囲が見つかります。もちろん、それはすべてアプリケーションに依存します。必要な精度のレベルを見積もって、許容値を許容値に設定するだけです。

それでも失敗した場合、それdoubleは単にあなたの目的には不十分であることを意味します. このシナリオはほとんどありませんが、非常に高精度の計算が必要な場合に発生する可能性があります。その場合、任意の精度のパッケージ (Java の BigDecimal やCのGMPなど) を使用する必要があります。繰り返しますが、他に方法がない場合にのみ、このオプションを選択してください。

于 2010-07-14T14:13:49.163 に答える
0

私はあなたのアプリケーションに精通していませんが、グラフ内のポイント間の距離の違いは、浮動小数点数の丸め誤差よりも桁違いに大きいと確信しています。したがって、2 つのエントリが丸め誤差だけが異なる場合、それらは本質的に同じであり、リストに表示される順序に違いはありません。常識的な観点から、心配する必要はありません。

于 2010-07-14T14:02:00.270 に答える