2

問題があります：

私はクラス A とクラス B を持っています。これらのインスタンス オブジェクトは、さまざまな量で互いに似ているか異なっているかをプログラムで調べることができます。たとえば、それらは完全に一致する場合もあれば、まったく異なる場合もあります (クラスが異なっていても、同じ情報を表し、同じスコアを付けることができます)。

ここで、A の 1 つと B の 1 つの 2 つのコレクションがある場合、A と B をペアにして、どちらかのコレクションが他のコレクションよりも大きいか、 As または B の一部が単純に一致するにはあまりにも異なる場合は?

私の最初の試みは、2 次元配列を作成することでした。各セルは一致の「スコア」 (0 = パーフェクト、数値が大きいほど悪い) であり、すべてのパスを再帰的に繰り返し、累積スコアが最も低いものを探します。これは機能し、結果は完璧ですが、非常に遅いです。

より効率的なアルゴリズムに関するアイデアはありますか?

ご参考までに、私の A クラスはオーディオ ミキサーの入力チャネルを表し、B は同じ (シーンと呼ばれる) 持続状態を表します。私が解決しようとしている問題は、既存のミキサーにシーンをインポートする方法です。この場合、シーン (B) は、既存のチャンネル (A) とわずかに、または大きく異なる場合があります。どちらかを少し変更して一致させることができれば、チャネル (A) を追加したくありません。たとえば、A にエフェクト インサートを追加して、B と完全に一致させ、別の A を追加する必要がないようにすることができます。

マイク

4

3 に答える 3

2

これは2部マッチングの問題のように聞こえ、エッジの重み付けに類似性メトリックを使用することで、標準の最大フロー/最小カットソリューションで解決できる可能性があります。

これは多分役に立ちます

于 2009-03-04T04:28:29.827 に答える
0

アルゴリズムはありません。一般的な提案のみです。必要なだけ多くの時間を費やして、途中で見つけた最良のオプションを選択するまで、ランダムにサンプリングする可能性を試すことができます。通常、このアプローチでは最適なソリューションは見つかりませんが、プログラムは非常に簡単です。また、問題によっては、最適に十分近づくこともあります。実験して、ランダム サンプルの数が増えると品質がどのように向上するかを確認できます。運が良ければ、少数のサンプルで十分な場合があります。

于 2009-03-04T11:18:04.117 に答える
0

私はヒューリスティックにそれをします。

最初に完全一致のセットを収集します。

次に、しきい値を設定し、そのしきい値よりも優れた一致を収集します。

一方または両方のセットが使い果たされるまで、しきい値を拡張して繰り返します。

これでトライアルマッチができましたが、これは最善ではないかもしれません。

シミュレートされたアニーリングの多くのサイクルを実行します。一致するリンクをランダムに並べ替え、それぞれのコストに依存する確率に基づいてそれらを維持するかどうかを決定します。

これにより、一致するスペースを探索することができ、より適切な一致が近くにある場合は、それらを見つける必要があります。

于 2009-03-10T12:04:36.047 に答える