压缩数学图

Question

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

你可以看到3个方案:a,b&c.如何更改元素(1,2,3 ...,9)的位置以使路径尽可能短？我的意思是这条线应该尽可能短.

我对它非常感兴趣,因为我正在绘制一个带有问题的图表,某种信息图表,如"按照线条来了解答案".我知道它有点关于图论...所以如果它太难了,你知道是否有任何程序用于压缩这样的东西？

例如,程序应该像这样工作:在输入中它应该得到3个pathes

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

并且在输出中应该是这个元素的坐标.

Answer 1

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

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