开源众包
232人浏览/7人投稿
562天前
已托管赏金
问题的本质是一个多层图交叉分支优化的组合优化NP-难问题，算法的目的是为了将复杂的AOE网络分块局部绘制再合并成整体运用算法以实现最大化减少分支交叉的目的。要实现的是多层次网络绘制（总入口在下，总出口在上所以节点也是自下而上排的有向无环图）就是数据结构中的AOE网。初步想法是:1. 多层次划分子网：步骤：使用社区检测算法（如不同的社区检测算法像GeLouvain算法等，并比较其效果，选择最适合数据的算法，考虑使用Leiden算法，它是Louvain算法的改进版，能够更快地收敛并且通常能找到更优的社团结构）根据拓扑数据和聚类指标对网络进行分层次划分。2. 确定子网的相对位置：步骤：将同层次子网视作一个节点，根据分层法和拓扑数据分析子网（划分区域）之间的分支连通情况，运用启发式搜索算法进行节点排序（只能左右，上下位置关系被AOE图性质限制被分层法相对定死）以确定各子网在总网中的层次关系及相对位置。或者可以利用层次聚类算法（如自底向上的层次聚类）来帮助确定子网的层次关系和相对位置。可以协商确认3. 明确各个子网的初步形状：步骤：根据子网的相对位置，初步确定每个子网的初步形状，以方便后续两步骤进行操作。（在设计初步形状时，可以考虑使用图形优化技术来减少节点的重叠和边的交叉，提高图形的可读性）。4. 对子网内的节点排序：步骤：根据子网所处的相对位置使用启发式搜索算法（如蚁群算法）结合Sugiyama分层法（可能会用到虚拟坐标）对子网内的节点进行排序，以减少子网内分支交叉，防止子网间连通分支穿透子网。（减少分支交叉，是一个多层图分支交叉优化的组合优化问题）5. 确认具体坐标进行绘制：步骤：连接各子网合并成总体网络图。使用Fruchterman-Reingold算法、Sugiyama算法等来确定每个节点的具体坐标。保证节点不重爹以及非交叉分支不汇集。最后合成最终的效果图那样的一个椭圆形形状总图。！！！当然算法都是我初步设想的可能有不合理你可以商量着换主要按照1.2.3…的思路来就行做出来的最终效果图不要两个椭圆要合并成一个椭圆的总图，保证所有有向边的方向倾斜趋势是向上的，确保是有向无环图！！因为是组合优化得NP难问题，交叉必不可免，但追求效果要实现最小化交叉分支数！
