0

この質問は、実装よりも効率的なアルゴリズムに関するものなので、コードは投稿しません。（質問を理解するのに本当に役立ちません）

質問を紹介すると、自動車のクラッシュレポートを計算するプログラムを開発しています。一連の「方程式」 (以降はEq、複数形は Eqs) を提供し、データを入力して通常は n 個の結果を取得します。

例: 対象空間 (x) を選択し、入力時間 (t)、加速度 (a)、初期速度 (v) を選択すると、x = (a*t)+((a*t^2)/2) になります。問題は、このEqs が vars と ecuation 自体よりも多くのものを含むオブジェクト内にあるということです。それをBo (busssines オブジェクトの話です。

そのため、BO は非常に大きく (そしてそうである必要があります)、とりわけ、1 つの Bo は N 個の Eq を持つことができ、複数の結果が得られます。また、すべての Eq が入力として値の範囲を取ることができるため、うまくいきます.. . (2 つの変数で範囲を使用できると仮定しましょう。実際にはこれは制限されていません)、結果ごとに結果の表が作成されます (一部の Bos には 4 つの異なる結果があります)。範囲の Te ステップは、最初の範囲が 20、2 番目の範囲が 10 に制限されています。(1 つの Bo の 800 の結果にマッピングされる 4 つの結果を持つ Bo で)。

ところで、この Bos をそれぞれの結果とともに保存 (ファイルに保存) する必要があり、Var 入力は実行時に毎回計算することはできません (ecuation を保存し、var 入力を保存して、毎回結果を計算することができます)。 Bos はこれらの ecuations を変更することができ、ユーザーは以前の結果を保持する必要があるため、質問しないでください..

また、Bo の結果の 1 つを別の Bo の Eq 入力にインポートすることもできます。したがって、前の例 (Bo1 と呼びましょう) では、加速はそれを計算する別の Bo (Bo2) から発生する可能性があり、それを計算するために他のパラメーターを使用します。Bo2 の入力を変更すると、結果が変わるため、少なくとも 1 Bo1 の var が変化し、Bo1 の結果が変化します。これはカスケードできます (B3 からの B2 インポートなど)。そして、1 つの Bo は、N 個の他の Bo から N 個の変数をすべてインポートできます。

ポインターまたは参照型を使用できません (おそらく参照型を使用できますが、とにかく多くの作業が必要であり、さまざまなユーザーから以前に保存されたデータを操作する必要があり、参照が欠落しているオブジェクトなど)。

配列のコレクションを使用することにしました。各配列に格納されている {Id_of_Bo_Exporting, Id_Bo_importing,Id_Variable_of_Bo_Importing,..(特定の結果のエクスポートをマップする ids)} 配列は int です (最初の 2 は長い)。

あまり好きではありませんが、コードは問題なく動作しています。(読んでくれてありがとう) 質問はこれからです、私は約束します。

問題は、循環インポートをチェックする必要があることです。B3 が B2 からインポートし、B2 が B1 からインポートする場合、B3 (または B2) からの Bo1 のインポートを許可すべきではありません。これは無限ループにつながります (ループを停止することはできますが、そのインポートを許可する数学的な観点からのロジックではありません)。

インポートリストは最終的に非常に長くなる可能性があります

私は ArrayList< ArrayList< long>> のことを考えているので、インポートを追加するたびに、この「もの」に Ids を追加します。(arraylist の arraylist)

long の各配列は、最初の位置に「Bo id ヘッダー」を持ち、Bo がインポートされるたびに、新しい Id がそのリストに追加され、Bo をインポートする他のすべての Bo (インポートを作成するもの) が追加されます。

したがって、ユーザーが B1 から B9 を作成しようとすると、メソッドが検出し、B1 が独自のリストに追加され、許可されません。

実装はとても簡単です。（Javaを使用しましょう。いいえ、私は.netを使用しています。自分でプロジェクトを開始しませんでした）

例 {{}}

B1 は B2 からインポートします: { {B1,B2} }

B1 は B6 からインポートします: {{B1,B2, B6 }}

B4 からの B2 インポート: {{B1,B2,B6, B4 }, {B2,B4} }

B9 からの B4 インポート: {{B1,B2,B3,B4, B9 },{B2,B4, B9 }, {B4,B9 }}

B10 からの B3 インポート: {{B1,B2,B3,B4,B9, B10 },{B2,B4,B9},{B4,B9}, {B3,B10} }

long の各配列は、最初の位置に「Bo id ヘッダー」を持ち、Bo がインポートされるたびに、新しい Id がそのリストに追加され、Bo をインポートする他のすべての Bo (インポートを作成するもの) が追加されます。

したがって、ユーザーが B1 から B9 を作成しようとすると、メソッドが検出し、B1 が独自のリストに追加され、許可されません。

実装はとても簡単です。（Javaを使用しましょう。いいえ、私は.netを使用しています。自分でプロジェクトを開始しませんでした）

private boolean checkCircularity(long ida,long idb){
//ida importing, idb exporting
// asume List is public and called iL
// Clone il to restore it in case}
for (int i = 0 ; i < iL.size() ;i++)  
    // Each arraylist of long in the big array iL
{    
    // I would use some kind of SetUniqueList, dont know in c#
    // but i could check it if needed and add it if it doesnt exist
    if (iL.get(i).contains(ida))
    {
        if (((iL.get(i)).get(0)) == idb)
        {// Circiut, breaks for's restore the original list and returns false
        }
        else{
            if (!iL.get(i).contains(idb)) {iL.get(i).add(idb);}
        }
    }
}       return true;    }

さて、質問 (ListSet などを使用して開始) は、これを行うためのより効率的な方法を考えることができますか? 両方のリスト (ユーザーによっては、インポートと iL が非常に速く大きくなる可能性があります)。キャプションはスピードです。

4

1 に答える 1

0

質問を正しく理解していれば、「循環性」のチェックは、実際にはグラフでのサイクル検出の例です。つまり、各「インポート」が有向グラフ エッジとしてモデル化されている場合、サイクルを検出しようとしています。

それが正しければ、これはよく理解された問題です。インポートを直接のノード参照としてモデル化し、サイクルを検出するための標準アルゴリズムの 1 つを使用することをお勧めします。サイクル検出を参照してください。

于 2015-01-28T07:49:06.377 に答える