|
|||||
|
|
| 混合图上的投递员问题的近似算法 | |
| 作者姓名： | 彭允 |
| 作者单位： | 山东大学数学系 |
| 摘 要： | 1.引言投递员问题是一类很广泛的应用问题,实际生活中的收购废品、清扫马路等都可以化成求解混合图上的投递员问题。考虑一个混合图G=(V,E,A),其中边集E和弧集A分别代表双向和单行马路或街道,顶点集V代表这些马路的交点。中国投递员问题是要求一条从某点出发经过各条马路至少一次(如果是单向马路,应按指定方向走),并且费用最少的路线。最初的投递员问题是考虑无向图上的情况,即是所要经过的街道都是双向的。无向图上的投递员问题是多项式 |
| 本文献已被 CNKI 等数据库收录！ | |