仮想回線パケット交換では、最初にネットワーク内の送信元と宛先の間に専用パスを確立します。パスの長さは短いほうがよいでしょう。ここでもまた、最短リンクに沿った最小リンクの容量は、情報の流れに制限を課します。
したがって、コスト関数、つまり経路長と最小リンク容量の重み付けされた組み合わせを設計することが望ましいです。パスの長さ l を減らし、最小リンク容量 c minを増やしたいので、コスト関数は( w 1 * f(c min ) - w 2 *g(l ))を最大化することができます。ここで w 1と w 2は重みで、f と g は線形関数または非線形関数のいずれかです。
任意のネットワークでこの問題を解決する効率的なアルゴリズムは何でしょうか??
私はこの問題に1週間以上悩まされており、これまでのところ何の進歩もありませんでした. しかし、最も広い問題はリンクの容量のみを考慮しますが、問題に長さの要素をどのように含めるか。または、問題にアプローチする他の方法があります。