【源码】基于C++的布局布线算法实现

项目简介

本项目聚焦于布局布线算法中迷宫布局布线算法和FM算法划分的实现。运用C++编程语言，结合工厂模式与优先队列等技术，达成了算法的高效实现与优化。

项目的主要特性和功能

1. 迷宫布局布线算法
   • 运用A*算法开展路径搜索，达成迷宫里的最优路径规划。
   • 借助优先队列提升搜索效率，多数情况下能得到较优连线结果。
   • 通过调整边权重（增加边权重、降低已布线边权重）优化多点连线结果。
2. FM算法实现划分
   • 采用桶型数据结构查找最大增益并更新，优化大数据量下算法的时间复杂度。
   • 引入多起始点方法改进FM算法，通过随机数生成随机初始平衡划分，多次运行以寻找最优结果。

安装使用步骤

环境要求

• 需Visual Studio 2019及以上版本以正常打开项目所有文件。
• 确保src文件夹的编码格式为Unicode(UTF-8)。
• 生成可在Windows下运行的Routing.exe可执行文件，若要在Linux下运行，需修改Makefile文件。

使用方式

1. 编译项目：依据自身环境编写并替换Makefile，当前项目中的Makefile仅适用于Windows。
2. 运行项目：在file文件夹中编写好测试文件file.txt后，在项目文件夹下运行以下命令： bash .\Routing.exe FM file\file.txt .\Routing.exe Astar file\file.txt
3. 计算A*布线长度：file文件夹中有计算Astar布线长度的程序，原理是利用两个存储矩阵的文件中的矩阵做差然后计算布线线长。在file文件夹中执行如下命令： bash .\Calc.exe file1 file2

输出结果

• FM算法：输出划分结果和最小切割大小。
• A*算法：输出连好线的迷宫图。

下载地址

点击下载 【提取码: 4003】【解压密码: www.makuang.net】