N 个点分成两排对这 N 个点进行排序让他们的交点最少

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 809 天前的主题，其中的信息可能已经有所发展或是发生改变。

上图交点数是 3, 但是我们可以打乱 A1 A2 ... Am B1 B2 ... Bn 的顺序让他们的交点数变化.

求算法. 或者关键字.

穷举的话 m! * n! 数量有点大啊...

谢谢大佬.

2 条回复 • 2023-07-06 21:48:38 +08:00

xupefei

2023-07-06 18:27:51 +08:00 via iPhone

我拍脑袋想了一下，似乎把 incoming 和 outgoing 最少的节点排左边就是最优解？

onlytmp

2023-07-06 21:48:38 +08:00

求图的连通分量吧，连通分量之间分开摆放就不会有交点，连通分量内部尽量展开摆放以减少交点

N 个点 分成两排 对这 N 个点进行排序 让他们的交点最少