DSP-parallel computing
- 0 Collaborators
我们在此次项目名为：并行化解决旅行商问题的各种算法，包括：遗传算法、粒子群算法、蚁群算法。旅行商问题是给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路 。此类问题属于NP难问题，无法在线性时间内解决，所以我们决定采用智能优化搜索算法，即各种仿生群体算法（遗传算法、粒子群算法、蚁群算法）来解决该问题，此类算法具有隐含并行性，对求解目标进行合理表示之后便可获得较优解，并且比较适合采用并行算法进行优化。 ...learn more
Project status: Under Development
Overview / Usage
旅行商问题是给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路 。此类问题属于NP难问题，无法在线性时间内解决，所以我们决定采用智能优化搜索算法，即各种仿生群体算法（遗传算法、粒子群算法、蚁群算法）来解决该问题，此类算法具有隐含并行性，对求解目标进行合理表示之后便可获得较优解，并且比较适合采用并行算法进行优化。
Methodology / Approach
我们使用dpc++以及openMP高级语言来对串行算法进行并行化处理，比较并行化前后运行时间来得出并行化后对算法的改进程度。