基于冲突模型的拓扑算法的研究与实现的中期报告.docx

基于冲突模型的拓扑算法的研究与实现的中期报告
本文介绍了基于冲突模型的拓扑算法的初步研究和实现。该算法使用冲突检测作为基础，并通过构建冲突图和搜索算法进行拓扑构建。主要包括以下几个部分：
1.冲突检测
通过扫描相邻节点，检测处于同一通道上的节点是否发生冲突，从而确定节点的状态：等待、传输或冲突。此外，为了提高冲突检测效率，使用了分组冲突检测方法，将节点分为若干组，每组内节点的传输时隙不可能相互冲突。
2.冲突图构建
在进行拓扑构建前，需要先构建冲突图，以确定节点之间的冲突关系。该算法使用了原始的递归算法，通过将节点分为当前集合和剩余集合，进行递归操作，最终得到完整的冲突图。
3.搜索算法
基于冲突图，使用搜索算法进行拓扑构建。其中，使用了深度优先搜索和广度优先搜索两种算法，并在进行搜索时，记录了已经搜索过的节点和已经确定拓扑的通道数，以便在搜索过程中进行剪枝。
4.实现
将算法实现在C++语言下，并使用Qt图形界面进行演示。通过图形化展示，可以直观地观察到拓扑结构的变化，并得到相关的统计结果。
目前，该算法已经构建出了冲突图，并使用深度优先搜索算法实现了拓扑构建。下一步的计划是进一步完善广度优先搜索算法，并进行性能优化，以提高算法的效率和准确性。