5

我想绘制一个类似这样的图表： alt text http://img25.imageshack.us/img25/9786/problemo.png

您可以看到 3 条路径：a、b 和 c。如何更改元素 (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（自己实现并不难）

查看您提供的示例图，让我们假设节点将放置在 NxN 网格（整数位置）上，然后对基因组进行编码，考虑以下方案：

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

接下来我们像往常一样设计交叉算子（一个或两个点交叉），以及变异（随机翻转一位）。我们只需要确保在任何时候，我们在网格内都只有有效的位置。
最后，适应度函数将是路径上节点之间距离的某个函数（多条路径的总和），它将惩罚长路径（作为最小化问题）。一个例子是节点之间的街区距离。
该方法的其余部分是标准遗传算法（初始化、评估、选择、复制、终止）。

示例 为了说明，考虑前面的布局与城市街区距离，给定以下两条路径： 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

显然，目标是找到最小化适应度函数的布局。

于 2009-09-26T23:07:52.367 回答