有限の値を持つセルの数

Question

プログラミングに関する質問が1つ発生しました。

私はN個の細胞を持っていると考えてください。これらの細胞は、いくつかの整数値または表現を持つことができます。 反復回数がT回になることがあります。繰り返しごとに、いくつかのセルを更新できます。 繰り返しごとに、どれくらいの数のセルが有限の値を持つかを知る必要があります（これは決めることができます）。

たとえば、N = 5の場合、5つのセルはA、B、C、D、Eになります。 A = 4、B = D + E、C = 2 * B、D = 6、E = A + B とすると、この場合、2つのセル（AとD） B、C、Eの値は決めることができません.BはEに依存しますが、これはB（循環直接依存）に依存します。一方、Cは未定のBに依存する。

D + Eの代わりにBを10に更新すると、すべてのセルが有限の値を持つとします。 A（4）、B（10）、C（20）、D（6）、E（14）。セルの各繰り返し値を変更することができる。

制約：（1' <「N = 200 <、1 < 'T' < = 1000）私が試した何

：依存それlist.Ifするすべてcell.For各反復更新のための依存関係のリストを作成します未定義の要素が1つ含まれている場合、この繰り返しではこのセルは有限の値を持つことができません。 他にも優れたアプローチがありますか？

Answer 1

本質的に、私はすべての道を進み、適切な依存グラフを作成します。これは有向グラフであり、ノードに依存する場合、ノードは他のノードへのエッジを持つ。

ノードを更新するときに、送信エッジを破棄し、必要に応じて再構築します。実際の計算：各ノードから、「既知」とマークされたノードに遭遇したときに終了する深さ優先のトラバーサルを開始し、マークを後方に伝播し始める。すなわち、ノードが「既知」であるとマークする。子ノードにはそのようにマークされます。

これは基本的にあなたのソリューションと同じだと思います。実際の実装に応じて、これは実行時のパフォーマンスが向上する可能性があります。これは視覚的にクリーンなソリューションだと思います。 3 -

どうかのA = 2 * BとB = A：ヘンリーさんのコメント@について

？周期的な参照にもかかわらず、 にはA = 6、B = 3というユニークな解があります。

更新後に最適化ステップを導入することができます。サイクルを調べることができます。見つかった場合、方程式のシステムを解くことで問題を解決しようとすることができます。それはクールだろう。