图的顶点着色问题是离散数学和图论的一个热门课题,也是一个经典的NP完全问题,目前仍然没有精确的算法可以在多项式时间内求解该问题。但是,图顶点着色算法在频率分配,最短路径,医学图像加密等诸多领域都具有广泛的应用。因此,图顶点着色问题的算法研究具有重要的理论意义和应用价值。近年来,基于群智能的粒子群优化算法得到了许多学者的关注,粒子群优化算法凭借极强的全局寻优能力在许多研究领域得到广泛应用。本文将粒子群算法应用于求解图顶点着色问题,提出了一种离散粒子群图顶点着色算法。该算法改进了传统的粒子群算法只能求解连续型问题的限制,在离散型问题的解空间内重新定义了粒子的位置,粒子的速度以及其更新方式,以及粒子群算法中的加法、减法以及乘法等运算。采用美国离散数学与理论计算研究中心(DIMACS)的64个图例对算法进行了验证,并通过与HPGA等其它启发式算法比较,证明了本文算法的有效性,可以高效搜索DIMACS图例的最小着色数。此外,由于图的顶点着色问题拥有指数级的解空间,假如图G有N个顶点,用K种颜色进行顶点着色,着色方案的解空间为K的N次方。因此,当求解问题规模N较大时,必须提高粒子群算法的速度才能高效的搜索指数级的解空间。本文利用基于GPU的并行计算平台CUDA对算法进行加速,提出基于CUDA的并行离散粒子群图顶点着色算法。算法实现了并行的粒子种群初始化,粒子速度、位置更新,适应度值计算,并行归约求解全局最优粒子,很大程度上提高了算法的效率。尤其相比于串行比较归约出全局最优粒子的时间复杂度O(n),本文采用对数步长交替方式归约全局最优粒子仅需O(log n)的时间复杂度。实验结果表明,相比于其他算法,本文提出的算法在找到已知图例最小着色方案时所需时间更少,对比基于CPU算法求解图顶点着色问题时,基于CUDA的并行算法较大程度上减少了计算时间。因此基于CUDA的并行离散粒子群图顶点着色算法在求解更大规模的图例上有很大的潜力。