ベルトバランサーの問題（Factorio）
Belt Balancer Problem
解決：
UTU =ユニバーサルスループット無制限
3、4、および5ベルト用のUTUバランサーがあり、ベルトの数に関係なく使用できる可能性があります。 。このJupyterノートブックには、Python実装とともに例が示されています。 ベルトとスプリッターの任意のセットのフローを計算するための反復アルゴリズム 。
リンクをたどりたくない人のために、ここでノートブックのいくつかを引用します。スプリッターをジャンクションと呼びます。それが実際に機能する方法だからです。
各ベルトは、ゲームではタイルと呼ばれる単位長のセグメントで構成されています。モデルでは、各ベルトが座標方向に沿って左から右に流れることを想像しています。$ x $各ジャンクションは、特定のタイルの左端で2つのベルトを結合します。実際に使用される一部のバランサーにはループが含まれており、無限の長さのベルトがないとモデルで表現できないことに注意してください。
ベルトタイルの状態は密度で表されます$ 0 le rho le 1 $と速度$ 0 le v le 1 $。値$ v = 1 $は通常のベルト速度であり、$ rho = 1 $ベルトの最大容量です。明らかに、私たちは持つことができるだけです$ v<1$もしも$ rho = 1 $;これは、ベルトが完全にロードされ、下流に十分な流出がない状態です。
上流への流入は密度によって指定されます$ rho_ {up} $ドメインの左端（$ x = 0 $）および下流への流出はによって指定されます$ v_ {down} $ドメインの右端にあります。 UTUをテストする目的で、これらの値を0または1に設定することにのみ関心がありますが、より一般的な値は以下のアルゴリズムで機能します。
満たすべき主な条件は、各ジャンクションでの保全です。ベルトに沿ったアイテムの流れは、製品によって与えられます$ rho v $、および接合部に入る磁束は、出る磁束と等しい必要があります。スプリッターの動作と一致する方法で各ジャンクションでこの条件を満たすと予想したよりもはるかに複雑であることが判明しました。これは、以下のコードに反映されています。時間があるときに、保存を実現するために、アルゴリズムに適用される条件のより正確な数学的記述を追加したいと思います。
簡単に言うと、最初に設定しました$ rho = 0 $と$ v = 1 $境界を除いてどこでも。各反復で、増加するだけです$ rho $と減少$ v $;反復値は、常に正しい値の下限（それぞれ上限）です。各反復で、流入が流出よりも大きいジャンクションをチェックし（前の文の条件のため、逆の状況は発生しません）、保存と均等な流出を実現するためにそれらを調整します。可能であれば、これを達成するために流出密度を上げます。それが不可能な場合（流出密度の1つが1に達するため）、余分な流出はすべて他のベルトに割り当てられます。それが不可能な場合（両方の流出密度が1に達するため）、一方または両方の流入ベルトがいっぱいになり、速度が低下します。
これは、UTU3ベルトバランサーを通過する1つのフローの簡略図です。 
数字は密度で、色は速度です。この場合も、フローは左から右になり、各黒い線はジャンクション（「スプリッター」）を表します。ゲームでは次のようになります。
これは非常に単純で明白なようです。 Factorioフォーラムにまだ投稿されていないことに驚いています。
これが4ベルトUTUバランサーです。
そしてそれをゲーム内で構築する1つの方法：
私は独立してやって来ましたが、これはすでに発明され、Factorioフォーラムに投稿されていると思います。
ノートブックにも5ベルトバランサーがありますが、ゲーム内で作成するのに時間がかかりませんでした。
ノートブックには、UTUプロパティに必要なすべての入力と出力のセットを生成およびテストするためのコードが含まれています。
これらのバランサーは、1つに収まる限り多くのジャンクションを単純に配置し、それらをずらして構築されていることに気付くでしょう。これを十分に行えば、常にUTUバランサーが手に入ると思いますが、ベルトの数に応じてバランサーの長さがどのように長くなるのかわかりません。興味深いことに、私の4ベルトバランサーは3ベルトバランサーよりも短いです（モデル表現では、実際の形状を気にせずにベルトを自由に組み合わせることができます）。しかし、5ベルトバランサーははるかに長いです。
ノートブックのアルゴリズムは、次のような他のシナリオを調査するためにも使用できます。$ m $-に-$ n $とのバランサー$ m $等しくない$ n $、または他の回答で提案されたアイデアをテストするには、$ 2n $UTUバランサーは$ n $UTUバランサー。いくつかの特定のプロパティを持つ可能な限り最短のバランサーを見つけようとするブルートフォースまたはよりインテリジェントな検索にアタッチするのは簡単です。
私はこの問題の複雑さに驚いていると言わなければなりません。最初はそれを解決するのがはるかに簡単だと思っていました。特に、私はまだ解決策への明確なアプローチを思い付くことができず、ノートブックの反復アルゴリズムのみを思い付くことができました。非常に興味深い問題をありがとう。
アップデート ：コメントでは、上部の入力と下部の出力が無効になっていると、3ベルトバランサーが故障すると主張されています。これがその状況の写真であり、完全なスループットを示しています。
スプリッターは、@ Rhamphoryncusが主張していることを正確に実行していることに注意してください。たとえば、タイル2（3番目のタイル）の下部の2つのベルトを接続するスプリッターは、2つの上流のベルトのそれぞれから完全なベルトのちょうど1/2を引き出します。同じことが、タイル4でこれら2つのベルトを結合するスプリッターでも発生します。
これは数学的な答えではありませんが、ノンブロッキングの最小スパニングスイッチとClosネットワークを再発明しているようです。この場合、スプリッターは基本的に2x2クロスバースイッチであり、それらを使用してより大きなスイッチを構築しています。
簡単な例として、NxNスイッチ（この場合は2x2スプリッター）がある場合、それらの3N（3 * 2 = 6）を使用して、Nであるスイッチを構築できます。2xN2（したがって、6つのスプリッターを使用する人気のある4x4バランサーデザイン）。
16x16が必要な場合は、これらの4x4バランサーを12個取り、入力側に4個、出力側に4個、中央に4個、すべてのスイッチを次のステージのすべてのスイッチに1本のベルトで接続できます。次に、このプロセスを繰り返して256x256などを取得できます。
その後、数学については完全にはわかりませんが、私は 考える たとえば、デザインを半分にカットしてスループットを半分にすることができます（たとえば、6x 4x4バランサーで8x8を取得できます）。次に、入力/出力の一部を接続しないだけで、2の累乗ではないものを取得できます。
これは完全な答えではありませんが
仮定1：無制限の4：4バランサーが可能です。私の信念は、これはスループット無制限であるということです。
4：4バランサーの設計を採用し、各2：2バランサーを4：4バランサーに置き換えると、無制限であると私が信じている8：8バランサーが必要になります。
もう少し一般的：n：nバランサーがある場合（nは2の累乗）、4：4バランサーの設計を採用し、各2：2バランサーを：nバランサーに置き換えることで2n：2nを取得できます。 。
これは、常に幾何学的に可能であることを前提としています。
誘導により、2のすべての累乗はスループット無制限のバランサーを持つ必要があります。
補遺1：上記が成り立つと仮定すると、スループット無制限バランサーは2の累乗で可能であるため、余分な入力/出力をブロックすることで、より少ない数のスループット無制限バランサーを実現できます。
補遺2 :(これは単なる推測です）特定の順序ですべて同じ方向に向かっているベルトのセットがある場合、他のすべてのベルトに地下ベルトを使用させることで、任意の2つのベルトの場所を順番に切り替えることができるはずです。いくつかの正方形。したがって、2つのベルトの任意の順列が可能であるため、ベルトを任意に並べ替えることができます。これは、n：nのバランサーから常に2n：2nのバランサーを構築できることを意味します。