压缩数学图形

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'

输出应该是这些元素的坐标。

- mothorool

Answer 1

每当我遇到难以解决的优化问题时，我就会想到遗传算法。我的解决方案假设你已经熟悉GA（自己实现并不是很困难）。看着你提供的示例图表，假设节点将放置在一个NxN网格上（整数位置），然后为了编码基因组，考虑以下方案：

00101 00100 11010 11110 11000     
  A     B     C     D     E

每个部分编码了节点在网格中的位置（按顺序），使用二进制表示。每个部分的长度取决于网格的大小（长度= 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

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

- Amro