3

私が書いている作図ソフトウェアで発生した問題を (効率的に) 解決するためのアルゴリズムが必要です。

N と M の 2 つのノードのセットがあります。N の各ノード n0 には、M の一意の (n0 の) ノードへの 0 から M の接続があります。これらのノードのセットは、N 個のノードを持つ 2 本の平行な水平線上に配置されます。 M ノードの上の行にあります。接続は、N から M への直線として描画されます。

私がする必要があるのは、交差を最小限に抑えるために、水平線内で N ノードと M ノードを再配置することです。O（N！* M！）であるすべての可能な配置を単純に列挙するよりも効率的なこれを行う方法はありますか？（実際には、各接続も交差をチェックする必要があるため、それよりもかなり悪いです）。

関連する文献への参照も歓迎しますが、その関連性が望まれる理由についての説明が必要です。

指摘したように、一般的なケースでは、これは 2 部グラフ (セット N および M) の平面化アルゴリズムと見なすことができます。ただし、この特定の問題はそれよりもかなり制限されており (高速化できることを願っています)、次のように追加情報を生成する必要があります (低速化する可能性があります)。

  1. ダイアグラムの制限は、接続が N から M への直線として描かれなければならないことです。グラフ理論では、これは事実上、接続がN または M のノードの後ろに行くことはできず、それらの間のみに行くことを意味します。したがって、4 つのコネクタを持つ 2x2 のケースは、一般的な 2 部グラフのケースでは平坦化できますが、私の図の場合は平坦化できません。

  2. 追加情報は、平面化できない場合でも、最小交差ソリューション (またはそれに近いソリューション) が必要であるということです。一般に、最小交差アルゴリズムは、平面化のみのアルゴリズムとは大きく異なります。

4

4 に答える 4

1

ノードがライン上の特定の位置を維持する必要がない限り、問題はフォースグラフアライメントで解決できます（何らかの変更を加えてそれを引き離すことが必要な場合でも）

変更する必要がある主な点は、X と Y の両方でノードを整列させるのではなく、X 軸でのみノードを整列させて、強制整列を 2D ではなく 1D にすることです。

アルゴリズムの前提は、ノードに作用する力があることです。そのため、ノードには反発力が作用し、互いに遠ざかります。ただし、互いに接続されているノードには、より大きな引力が作用します。反発。各ループで力を追加して、互いに引き付けられているノードが互いに近づくようにしますが、そうでないノードは反発します。あるしきい値よりも低い総力を合計すると、整列が行われます。 0.001。

http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)

于 2012-10-21T03:20:09.420 に答える
1

あなたが説明したモデルは二部グラフと呼ばれ、あなたが要求するのは平坦化アルゴリズムです。あなたの質問に答える最良の方法は、少しグーグルすることです.

于 2011-04-10T12:46:12.870 に答える
1

suddnely_me は正しいですが、完璧なソリューションは必要ないかもしれません。非常に単純な貪欲なアルゴリズムを試すこともできます。接続数に応じてすべてのノードをソートします。次に、水平線に1つずつ追加します..考えていませんでしたが、簡単なアプローチにつながる可能性があります..

于 2011-04-10T13:04:40.207 に答える
0

NとMの大きさは？時間 O(min(N, M)! * 2**max(N, M) * poly(N, M)) で実行される動的計画法に基づくソリューションがありますが、それが大幅な改善かどうかはわかりませんあなたの見解ではブルートフォースを超えています。

于 2011-04-10T16:56:32.670 に答える