1

他のノードのエントリに接続するエントリのリストであるノードを持つ有向非巡回グラフがあります。このような種類：

entry     ]
entry--|  ] node 1
entry  |  ]
-----  |
entry<-|  ] node 2
entry  |  ]
-----  |
entry  |  ] node 3
entry--|  ]

ノード内のエントリの順序は固定されています。エントリは、リンク先のエントリへの絶対インデックスを持つ配列に格納されます。エントリごとに最大 1 つのリンクがあり、すべてのノードには少なくとも 1 つのリンクがあります。(つまり、これは高度に接続されたグラフです)。グラフには、40,000 のノードにグループ化された約 100,000 のエントリが含まれています。

私がしなければならないことは、リンクに相対インデックスを使用して基礎となるデータ構造を圧縮できるように、ノードを並べ替えてエントリ間の最大距離を最小限に抑えることです。

圧縮とパフォーマンスが目標であるため、外部データ (ジャンプ テーブル、リスト内の特別なジャンプ要素) を追加するソリューションは受け入れられません。エントリ間の最大距離を最小化するノードの並べ替えアルゴリズムが本当に必要です。何かご意見は？

4

1 に答える 1

1

あなたが説明している問題は、最大距離を最小限に抑える方法です。NP困難だと思うので、単純な解決策はあまり良くありません。ただし、それを ILP 問題としてモデル化し、そのために何らかのソルバーを使用することはできます。

次に、目的として M を最小化します。

制約はM>= abs(s_i-e_i)すべてのリンクに適用されますl_i。s_iリンクの開始エントリと終了エントリの絶対インデックスをe_i表します。

これらのエントリは、ノードが属するインデックスとそのノード内の固定オフセット (他のエントリの中で)と同様s_i=n_i+c_iに、それらが属するノードに関して書き換えることができます。同様に書き換えます。次に、ソルバーで最適化するように設定されていますn_is_ic_ie_in_i

于 2012-12-07T09:26:51.290 に答える