2

以下に、私が望む正確な形式で問題を表現します。

与えられた :同じ長さ(は 2 の倍数) の 2つNの浮動小数点リスト。すべての場合、 が存在することが知られています。（ゼロベースのインデックスを使用しています）Dkki=0,...,k-1j != iD[j]*D[i] == N[i]*N[j]

戻り値: (長さ) のようなk/2ペアのリスト。返されるペアは一意ではない可能性があります (ペアの有効なリストは問題ありません)。(i,j)D[j]*D[i] == N[i]*N[j]

このアルゴリズムのアプリケーションは、一般化回文固有値問題の固有値の逆ペアを見つけることです。等式条件は と同等ですがN[i]/D[i] == D[j]/N[j]、分母がゼロの場合にも機能します (これは確実な可能性です)。固有値問題の縮退により、ペアが一意ではなくなります。

より一般的には、アルゴリズムは次と同等です。

指定X:長さのリストk(kは 2 の倍数)。すべての に対して、 がtrue を返すようなものi=0,...,k-1が存在することが知られています。ここで、 はすべての に対して少なくとも 1 つに対して true を返すことが保証されているブール一致関数です。j != iIsMatch(X[i],X[j])IsMatchj != ii

戻り値 : リスト内のすべてのペアの (長さk/2)ペアのリスト。返されるペアは一意ではない可能性があります (ペアの有効なリストは問題ありません)。(i,j)IsMatch(i,j) == true

明らかに、私の最初の問題は を使って 2 番目の問題で定式化できますIsMatch(u,v) := { (u - 1/v) == 0 }。現在、浮動小数点精度の制限により、正確に等しいことはありません。そのため、一致エラーを最小限に抑えるソリューションが必要です。つまり、IsMatch(u,v)が値u - 1/vを返し、IsMatch がエラーの最小セットを返すリストをアルゴリズムが返すようにしたいとします。これは組み合わせ最適化問題です。最初に、考えられるすべてのインデックスiとのペア間の一致エラーを単純に計算できると考えてjいましたが、次に最小エラーのセットを選択する必要があり、どうすればよいかわかりません。

明確化

IsMatch関数は再帰的 ( をIsMatch(a,b)意味する) ですが、推移的ではIsMatch(b,a)ありません。しかし、それは 3 推移的です: をIsMatch(a,b) && IsMatch(b,c) && IsMatch(c,d)意味しIsMatch(a,d)ます。

補遺

この問題は明らかに、グラフ理論における最小重み完全一致問題と同じです。ただし、私の場合、「適切な」完全な一致が必要であることを知っているため、エッジの重みの分布は完全にランダムではありません。この情報は何らかの形で利用されるべきだと思います。ここでの問題は、検索の早い段階で私の以前の知識を使用して解決策に到達する、最小重量完全一致問題の適切な実装があるかどうかです。また、そのようなアルゴリズムの単純な実装への指針にもオープンです。

4

7 に答える 7

1

問題が解決したことを願っています。

まあ、IsMatch(i, j) and IsMatch(j, l)それならIsMatch(i, l)。より一般的には、IsMatch関係は推移的、可換的、再帰的です。その同値関係。このアルゴリズムは、リスト内で最も多く出現する要素に変換します (= の代わりに IsMatch を使用します)。

于 2009-11-27T00:24:08.293 に答える
0

（D [i]、N [i]）のペアを並べ替えることができるはずです。ゼロで除算する必要はありません。次のように乗算するだけです。

bool order(i,j) {
  float ni= N[i]; float di= D[i];
  if(di<0) { di*=-1; ni*=-1; }

  float nj= N[j]; float dj= D[j];
  if(dj<0) { dj*=-1; nj*=-1; }

  return ni*dj < nj*di;
}

次に、ソートされたリストをスキャンして、（N == D）と（N == -D）の2つの分離点を見つけます。以下を使用して、そこから逆数ペアのマッチングを開始できます。

abs(D[i]*D[j]-N[i]*N[j])<epsilon

妥当性チェックとして。最後に（N == 0）ポイントと（D == 0）ポイントを残します。それらはすべて互いに一致するため、それらをネガティブと見なすかポジティブと見なすかは関係ありません。

編集：あるいは、（N == 0）と（D == 0）のケースを別々に処理して、リストから削除することもできます。次に、（N [i] / D [i]）を使用して、残りのインデックスを並べ替えることができます。ゼロに近いケースと正確にゼロのケースを一致させることができるように、1.0と-1.0から開始することもできます。

于 2009-11-27T11:39:22.133 に答える
0

(私が問題を理解していれば...) 2 つのリスト内の製品の各ペアを照合する 1 つの方法を次に示します。

  1. 各ペア N を乗算し、積と積を構成する要素の添字を含む構造体に保存します。
  2. 各ペア D を乗算し、積と積を構成する要素の添字を含む構造の 2 番目のインスタンスに保存します。
  3. 製品の両方の構造を並べ替えます。
  4. 並べ替えられた両方の構造体配列を介してマージ型パスを作成します。一方の配列から他方の配列に十分に近い積が見つかるたびに、ソートされた各リストの 2 つの添字を記録して一致を確認できます。
  5. ismatch 関数に 1 つの並べ替え済みリストを使用して、積に対してバイナリ検索を実行することもできます。
于 2009-11-27T01:45:17.680 に答える
0

各ペア D を乗算し、積と積を構成する要素の添字を含む構造の 2 番目のインスタンスに保存します。

于 2009-11-27T01:53:29.703 に答える
0

CS の友人に尋ねたところ、彼は以下のアルゴリズムを思いつきました。彼はここにアカウントを持っていません (そして明らかにアカウントを作成したくないようです) が、彼の答えは共有する価値があると思います.

// We will find the best match in the minimax sense; we will minimize
// the maximum matching error among all pairs. Alpha maintains a
// lower bound on the maximum matching error. We will raise Alpha until
// we find a solution. We assume MatchError returns an L_1 error.

// This first part finds the set of all possible alphas (which are
// the pairwise errors between all elements larger than maxi-min
// error.
Alpha = 0
For all i:
    min = Infinity
    For all j > i:
        AlphaSet.Insert(MatchError(i,j))
        if MatchError(i,j) < min
            min = MatchError(i,j)
    If min > Alpha
        Alpha = min

Remove all elements of AlphaSet smaller than Alpha

// This next part increases Alpha until we find a solution
While !AlphaSet.Empty()
    Alpha = AlphaSet.RemoveSmallest()
    sol = GetBoundedErrorSolution(Alpha)
    If sol != nil
        Return sol

// This is the definition of the helper function. It returns
// a solution with maximum matching error <= Alpha or nil if
// no such solution exists.
GetBoundedErrorSolution(Alpha) :=
    MaxAssignments = 0
    For all i:
        ValidAssignments[i] = empty set;
        For all j > i:
            if MatchError <= Alpha
                ValidAssignments[i].Insert(j)
                ValidAssignments[j].Insert(i)

        // ValidAssignments[i].Size() > 0 due to our choice of Alpha
        // in the outer loop

        If ValidAssignments[i].Size() > MaxAssignments
            MaxAssignments = ValidAssignments[i].Size()
    If MaxAssignments = 1
        return ValidAssignments
    Else
        G = graph(ValidAssignments)
        // G is an undirected graph whose vertices are all values of i
        // and edges between vertices if they have match error less
        // than or equal to Alpha
        If G has a perfect matching
            // Note that this part is NP-complete.
            Return the matching
        Else
            Return nil

これは、NP 完全であるグラフの完全な一致を計算できることに依存していますが、少なくとも既知の問題に還元されます。ソリューションは NP 完全であることが期待されますが、実際には指定されたリストのサイズが非常に小さいため、これで問題ありません。より良い答えを数日間待つか、誰かが合理的な方法で完璧なマッチングを見つける方法を詳しく説明してくれるのを待ちます.

于 2009-11-27T02:25:04.897 に答える
0

D(i)*D(j) = N(i)*N(j) {私は * が通常の実数乗算であると仮定しました}

すべての N(i) が非ゼロであると仮定すると、

Z(i) = D(i)/N(i)。

問題: Z(i) = 1/Z(j) となる j を見つけます。

セットをポジティブとネガティブに分割し、別々に処理します。

明確にするためにログを取ります。z(i) = ログ Z(i)。

間接的にソートします。次に、並べ替えられたビューでは、たとえば、-5 -3 -1 +1 +3 +5 のようになります。+/- ペアを読み取ると、元のインデックスが得られます。

何か不足していますか、それとも問題は簡単ですか?

于 2009-11-27T09:17:51.370 に答える
0

さて、私はこの移植された Fortran コードを使用することになりました。ここでは、以下を使用して密な上三角距離行列を指定するだけです。

complex_t num = N[i]*N[j] - D[i]*D[j];
complex_t den1 = N[j]*D[i];
complex_t den2 = N[i]*D[j];
if(std::abs(den1) < std::abs(den2)){
    costs[j*(j-1)/2+i] = std::abs(-num/den2);
}else if(std::abs(den1) == 0){
    costs[j*(j-1)/2+i] = std::sqrt(std::numeric_limits<double>::max());
}else{
    costs[j*(j-1)/2+i] = std::abs(num/den1);
}

これはうまく機能し、私の目的には十分高速です。

于 2009-11-27T09:52:10.513 に答える