C++-远程-1个月

项目编号：【165804】
C++编写自动绘制矿井通风网络图（AOE有向无环网络图）要解决的问题本质是一个多层图交叉分支优化的组合优化NP-难问题，算法的目的是为了将复杂的AOE网络分块局部绘制再合并成整体运用算法以实现最大化减少分支交叉的目的。

要实现的是多层次网络绘制（总入口在下，总出口在上所以节点也是自下而上排的有向无环图）就是数据结构中的AOE网。初步想法是:

1.进风井（起始节点）与回风井（终止节点）之间通过大气虚拟分支连接，通过大气分支识别出起、终节点，起点在总图最下，终点在总图最上。

2.建立数学模型，使得最后输出的网络图分支交叉数近似最小。

根据有向图的拓扑节点排序关系：

3. 多层次划分子网：

步骤：根据节点间的连接关系使用社区检测算法（如不同的社区检测算法像GeLouvain算法等，并比较其效果，选择最适合数据的算法，考虑使用Leiden算法，它是Louvain算法的改进版，能够更快地收敛并且通常能找到更优的社团结构）根据拓扑数据和聚类指标对网络进行分层次划分。



2. 确定子网的相对位置：

步骤：将同层次子网视作一个节点，根据分层法和拓扑数据分析子网（划分区域）之间的分支连通情况，运用启发式搜索算法进行节点排序（只能左右，上下位置关系被AOE图性质限制被分层法相对定死）以确定各子网在总网中的层次关系及相对位置。

或者可以利用层次聚类算法（如自底向上的层次聚类）来帮助确定子网的层次关系和相对位置。

可以协商确认

3. 明确各个子网的初步形状：

步骤：根据子网的相对位置，初步确定每个子网的初步形状，以方便后续两步骤进行操作。

（在设计初步形状时，可以考虑使用图形优化技术来减少节点的重叠和边的交叉，提高图形的可读性）。



4. 对子网内的节点排序：

步骤：根据子网所处的相对位置使用启发式搜索算法（如蚁群算法）结合Sugiyama分层法（可能会用到虚拟坐标）对子网内的节点进行排序，以减少子网内分支交叉，防止子网间连通分支穿透子网。（减少分支交叉，是一个多层图分支交叉优化的组合优化问题）

（以上四步根据建立的！！数学模型！！来确定近似最小交叉分支数目，每步骤的生成效果图要截图体现出来。）

5. 确认具体坐标进行绘制：

步骤：连接各子网合并成总体网络图。使用Fruchterman-Reingold算法、Sugiyama算法等来确定每个节点的具体坐标。保证节点不重爹以及非交叉分支不汇集。



最后合成最终的效果图那样的一个椭圆形形状总图。



当然算法都是我初步设想的可能有不合理你可以商量着换主要按照1.2.3…的思路来就行

做出来的最终效果图不要两个椭圆要合并成一个椭圆的总图，保证所有有向边的方向倾斜趋势是向上的，确保是有向无环图！

因为是组合优化得NP难问题，交叉必不可免，但追求效果要实现最小化交叉分支数！