1

我有一个有向无环图，其中的节点是连接到其他节点中条目的条目列表。有点像这样：

entry     ]
entry--|  ] node 1
entry  |  ]
-----  |
entry<-|  ] node 2
entry  |  ]
-----  |
entry  |  ] node 3
entry--|  ]

节点内条目的顺序是固定的。这些条目存储在一个数组中，该数组具有它们链接到的条目的绝对索引。每个条目最多有 1 个链接，每个节点至少有 1 个链接。（换句话说，这是一个高度连通的图）。该图包含大约 100,000 个条目，分组在 40,000 个节点中。

我需要做的是通过重新排序节点来最小化条目之间的最大距离，以便我可以使用链接的相对索引并压缩底层数据结构。

因为压缩和性能是目标，所以添加外部数据（跳转表、列表中的特殊跳转元素）的解决方案是不可接受的。我真的需要一种算法来重新排序节点，以最小化条目之间的最大距离。有什么想法吗？

4

1 回答 1

1

您描述的问题是如何最小化最大距离。我认为这是 NP 难的，所以一个简单的解决方案不会很好。但是，您可以将其建模为 ILP 问题并为此使用一些求解器。

然后，您将最小化 M 作为目标。

约束将M>= abs(s_i-e_i)适用于所有链接l_i。s_i并e_i表示链接开始和结束条目的绝对索引。

这些条目可以根据它们所属的节点被重写，就像节点所属s_i=n_i+c_i的n_i索引和该节点内的固定偏移量（在其他条目中）一样。同样被重写。然后您就可以使用求解器进行优化了s_ic_ie_in_i

于 2012-12-07T09:26:51.290 回答