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

2023-07-06 18:17:43 +08:00
 chaleaochexist

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

求算法. 或者关键字.

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

谢谢大佬.

756 次点击
所在节点    算法
2 条回复
xupefei
2023-07-06 18:27:51 +08:00
我拍脑袋想了一下，似乎把 incoming 和 outgoing 最少的节点排左边就是最优解？
onlytmp
2023-07-06 21:48:38 +08:00
求图的连通分量吧，连通分量之间分开摆放就不会有交点，连通分量内部尽量展开摆放以减少交点

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/954651

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX