5

次のようなグラフを描きたい: 代替テキスト http://img25.imageshack.us/img25/9786/problemo.png

a、b、c の 3 つのパスが表示されます。要素 (1,2,3...,9) の位置を変更してパスをできるだけ短くするにはどうすればよいですか? つまり、この行はできるだけ短くする必要があります。

私は質問のあるグラフを描いているので、非常に興味があります。「線をたどって答えを知る」のようなインフォグラフィックです。私はそれがグラフ理論について少し知っています...それが難しすぎる場合、Linuxがこのようなものを圧縮するためのプログラムがあるかどうか知っていますか?

たとえば、プログラムは次のように動作する必要があります。入力では、3 つのパスを取得する必要があります。

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

出力では、この要素の座標が必要です。

4

1 に答える 1

3

解決するのが難しい最適化問題があるときはいつでも、遺伝的アルゴリズムについて考えます。以下の私のソリューションは、あなたが GA に精通していることを前提としています (自分で実装するのはそれほど難しくありません

) 、次のスキームを検討してください。

00101 00100 11010 11110 11000     
  A     B     C     D     E

ここで、各部分はノードのグリッド内の位置を (バイナリで) (その順序で) エンコードします。各部分の長さは、グリッドのサイズ ( length=ceil(log2(N*N)) ) によって異なります。
グリッドには、行ごとに左から右に番号が付けられます。

例として、4 つのノード (A、B、C、D) と 3x3 グリッドを持つ完全なグラフの場合、文字列は次のようになります。

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 点または 2 点の交差)設計し、突然変異も同様に設計します (ランダムに 1 ビットを反転)。いつでも、グリッド内に有効な位置しかないことを確認する必要があります。
最後に、適合度関数は、パス上のノード間の距離 (複数のパスの合計) の関数になり、長いパスにペナルティを課します (最小化問題として)。例として、ノード間の市区町村の距離を取得します。
メソッドの残りの部分は、標準的な遺伝的アルゴリズム (初期化、評価、選択、複製、終了) です。

例 例A D C Bを示すために、次の 2 つ の パスが与えられた場合に、街区の距離を含む前のレイアウトを考えてみましょう。 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

明らかに、目標はフィットネス関数を最小化するレイアウトを見つけることです。

于 2009-09-26T23:07:52.367 に答える