0

私は現在、3つの目的を持つ多目的問題に取り組んでおり、すべての目的の重みを合計すると1になる加重合計アプローチを使用しています。たとえば、2つの目的がある場合、私の重みはステップとして0.1も使用していますだろう：

 0.9 0.1
 0.8 0.2
 0.7 0.3

しかし、現在、私は 3 つの目的で立ち往生しており、次のように 3 つの目的にわたって同様の重みの分布を作成できるアルゴリズムを見つけようとしています。

 1obj       2obj               3obj
 1.0        0.0                0.0
 0.9     (0 ; 0.1)           (0.1 ; 0)
 0.8   (0 ; 0.1 ; 0.2)    (0.2 ; 0.1 ; 0)

可能なすべての組み合わせを取得するアルゴリズムを提案できますか

4

1 に答える 1

0

この場合にすべての組み合わせを取得する最も簡単な方法は、問題をグラフとしてモデル化し、BFSなどのグラフ検出アルゴリズムを実行することです。

グラフはG=(V,E)どこにV = { (x1,x2,x3) | x1 + x2 + x3 = 1 }なりますE = { (v1,v2) | can get from v1 to v2 within a single change}（たとえば((1,0,0.0,0.0),(0.9,0.0,0.1))、エッジです-1回の変更で一方から他方に移動できるため）。

ここで、グラフが強く接続されているため (理由を自分で納得してください)、BFS はこのグラフのすべての頂点を検出し、可能なすべての組み合わせを検出します。

注意: 可能性の数は指数関数的であるため、多数のオブジェクトまたは小さなステップの場合、グラフ全体を検出するには長い時間がかかります。

小規模な最適化: (グラフのサイズが大きすぎると予想されない場合は不要): グラフをDAGとしてモデル化することにより、このソリューションのスペース消費を最適化できます(構造上の制限として「バック エッジ」を許可しない)。すべての頂点は単一の (一意の) ソースから引き続きアクセスできるため、これでも正しい結果が得られます。 これにより、DAG で BFS を実行する場合、セットを維持する必要がない
ため、スペースの消費が節約されます。visited

于 2012-06-07T05:39:44.057 に答える