毕业论文初稿(11)

最小生成树

结点的图的一棵生成树。其中：第i个位置的数不能使i+1，且这个数不能与前i-1个数的任意一个相同。

解码方法：排列p中的第i个位置的数为j，则表示的一条边为：从结点j到结点i+1的一条边。如：排列p=（4，5，1，6，2，3）表示的6条边为：4—>2,5—>3,1—>4,6—>5,2—>6,3—>7,也即有7个结点的图的一棵生成树为1—>4—>2—>6—>5—>3—>7。

这种编码策略的优点是：编码长度为问题结点数的线性函数，且可以充分的利用了边之间的信息，编码简单，方便进行插入，删除等操作。

参考文献：