一种在欧式空间中设计NP-Hard问题多项式近似方案的新技术

摘要

该文讨论的是一类限制在欧式平面上的NP-Hard问题,这类问题可以称为

目录

原创性声明及关于学位论文使用授权的声明

摘要

第一章前言

第二章NP-hard问题与多项式时间近似方案简介

一、欧式平面

二、多项式时间近似方案

三、TSP问题

四、Steiner树问题

五、K-Median问题

第三章随机平面分割

一、分割方法

二、由最优解修改成面向标记解增加的代价

第四章随机平面分割后近似最优解计算

一、求K-Median面向标记解

二、求TSP面向标记解

第五章编程实现与测试结果

一、系统实现

二、实验数据及测试结果

三、数据分析

第六章结论

参考文献

致谢

攻读硕士期间发表论文