これはmathoverflowのための十分な数学だとは思わなかったので、ここで試してみると思いました。しかし、それはプログラミング上の問題のため、そのトピックのsorta。熱方程式を使用したロードバランシング
私はグラフの頂点数がA、B、Cです。それぞれに負荷 "値"があり、これらは任意のトポロジで接続されています(そこには少なくともスパニングツリー)。この問題の目的は、各頂点間で、可能な限り最小限のフローを使用して負荷を転送することです。
各エッジに沿った転送値を知りたいと思います。
私が考えていた問題の解決策は、それを熱伝達の問題として扱い、反復的に負荷を移すか、熱方程式を何らかの方法で解くことで、各エッジに沿って散逸する負荷の量を数えることでした。したがって、ネットワークが定常状態に達するまでの熱伝達の量は結果をもたらすはずである。
これはうまくいくと思うが、それは愚かな解決策のようだ。私は誰かが私を指すことができる参照またはサンプルの問題があるかどうか疑問に思っています - 私は検索するキーワードが不明です。
シンプレックスの問題またはネットワークフローの問題のいずれかとして問題を結合する方法がわかりませんでした。各エッジには容量が無限にあり、各ノードも無制限です。解決するために2つの同時最小化問題があるので、シンプレックスは適用されないようですね??
[Laplacian smoothing](http://en.wikipedia.org/wiki/Laplacian_smoothing)のように聞こえます。 – lhf
問題を明確に定義していません。可能な限り最小のフローを使用して、各頂点間で負荷を転送することは、いくつかのことを意味する可能性があります(おそらく最小限のフローになります)。熱伝達を使用すると、高い値を持つ頂点から低い値を持つ頂点に「荷重」を移動したいことが示唆されます。おそらく、あなたの目標は、すべての頂点のレベルローディングを達成するために必要な最小限の転送量です。しかし、これまで説明したデータでは、連続モデル(熱伝達)はサポートされていないと私は考えています。 – hardmath