数学的なグラフの圧縮

Question

私はこのようなものになり、グラフを描きたいです。 altテキストhttp://img25.imageshack.us/img25/9786/problemo.png

、B＆C：

あなたは3 pathesを見ることができます。どのように私は要素の位置変更することができます（1,2,3 ...、9）できるだけ短いパスの長い作るには？私は、この行はできるだけ短くしてください意味ます。

イム私は、「答えを知っているラインに従ってください」などのインフォグラフィックのいくつかの種類を質問してグラフを描いていますbecouseことに非常に興味を持って。私が知っているグラフ理論についてそのビット...ので、その硬すぎ、このようなコンパクトなものにLinux用の任意のプログラムがある場合は、あなたが知っている場合は？

たとえば、プログラムは次のように動作するはずです： 入力では、3 pathes

を取得する必要があります

a='1,5,7,8,4,2,6'
b='4,2,3,6,9,8,5'
c='7,9'

そして、この要素の座標であるべきで出力

Answer 1

私は解決が困難である最適化問題を持っているときはいつでも、

、私は遺伝的アルゴリズムを考えるの。以下の私のソリューションは、あなたがGA（それを自分で実装するのは非常に難しいことではありません）

に精通していることを前提としてい あなたが与えた例のグラフを見ると、それからのゲノムを体系化するために、私たちはノードがN×N個のグリッド上（整数位置）に配置されると仮定してみましょう。は、次のスキームを検討します：

00101 00100 11010 11110 11000     
  A     B     C     D     E

ここで、各部分は、ノード（この順序で）の（バイナリで）グリッド内の位置を符号化します。各部分の長さは、グリッドのサイズ（長さ= CEIL（LOG2（N * N）））に依存する。
グリッドは、左から右に、行ごとに番号が付けられます。

そこで、一例として、4つのノード（A、B、C、D）と3×3グリッドとの完全なグラフの文字列

0011 0001 0101 1000    =   3  1  5  8 
 A    B    C    D          A  B  C  D

以下のレイアウトを表す

. B .       00  01  02
A . C       03  04  05
. . D       06  07  08

次に、我々は、通常の（一次元又は二点クロスオーバー）としてクロスオーバーの演算子を設計し、変異同様に（ランダムに1ビットを反転）。私達はちょうど任意の時点で、我々は唯一のグリッド内ののを有効な位置を持っていることを確認する必要があります。
最後にフィットネス関数は長いパス（最小化問題として）を不利になる、経路上のノード間の距離の一部の機能（複数のパスの合計）であろう。 例では、ノード間の都市ブロック距離を取ることである。
方法の残りの部分は、標準的な遺伝的アルゴリズム（初期化、評価、選択、再生、終了）である。

の例の 例示するために、次の二つの経路を考えると、都市ブロック距離との以前のレイアウトを検討：A D C BとC B D A

A -> D -> C -> B
  3  + 1  + 2    = 6        therefore
C -> B -> D -> A              fitness(0011 0001 0101 1000) = 6 + 8 = 14
  2  + 3  + 3    = 8

もちろん目標は、トレーニング機能を最小限に抑えるレイアウトを見つけることです。