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

This topic created in 1216 days ago, the information mentioned may be changed or developed.

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

求算法. 或者关键字.

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

谢谢大佬.

2 replies • 2023-07-06 21:48:38 +08:00

xupefei

Jul 6, 2023 via iPhone

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

onlytmp

Jul 6, 2023

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

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