math - 压缩数学图

Question

我想画一个像这样的图形:
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'

在输出中应该是这个元素的坐标。

Answer 1

每当遇到难以解决的优化问题时，我就会想到genetic algorithms .我下面的解决方案假设您熟悉 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

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

示例
为了说明这一点，请考虑具有城市街区距离的先前布局，给出以下两条路径: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

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