权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Exact algorithms for NP-hard problems

NP 困难问题的精确算法

基本信息

批准号：
EP/D053633/1
负责人：
Daniel Paulusma
金额：
$ 11.89万
依托单位：
Durham University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2006
资助国家：
英国
起止时间：
2006 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FD053633%2F1
关键词：
Exact algorithms NP hard problems

项目摘要

We propose to study exact algorithms for NP-hard problems. An algorithm can be seen as a set of constructions for solving a problem. An exact algorithm is an algorithm that solves a problem to optimality. NP-hard problems are a special kind of optimization problems for which most probably no polynomial time (i.e. fast ) algorithm exists. As an example of an NP-hard problem we can consider the travelling salesman problem (TSP). In this problem a travelling salesman has to make a tour through a number of cities starting and returning to city 1 in such a way that the total travel distance is minimal. Of course, it is possible to solve this problem to optimality by computing the distance of every tour and then choosing a tour with minimum distance. This simple algorithm costs a huge amount of computation time. Already in the case of a relatively small number of cities, the problem can not be solved (within reasonable time) on any modern computer that uses this algorithm.Our research will result in faster algorithms for this kind of problems. Even a faster exact algorithm that does not run in polynomial time can already mean that in practice much larger instances (cf. with many cities in TSP) can be solved. Secondly, we hope that our research will lead to a better understanding of NP-hard problems with respect to the (worst-case) time it takes to solve them. Since it is very unlikely to obtain polynomial time algorithms for this kind of problems, we can not expect to develop exact algorithms that are faster than a certain threshold. By developing faster algorithms for a number of NP-hard problems we hope to find out whether thresholds for different problems are somehow related to each other.

我们建议研究NP-Hard问题的精确算法。算法可以被视为一组用于解决问题的构造。精确算法是一种将问题解决到最优的算法。NP-Hard问题是一类特殊的优化问题，很可能不存在多项式时间(即快速)算法。作为NP难问题的一个例子，我们可以考虑旅行商问题(TSP)。在这个问题中，旅行推销员必须以总旅行距离最小的方式在多个城市旅行，从城市1出发，然后返回城市1。当然，可以通过计算每条线路的距离，然后选择距离最小的线路来解决这个问题，使其达到最优。这种简单的算法耗费了大量的计算时间。在城市数量相对较少的情况下，这个问题在任何使用这种算法的现代计算机上都不能(在合理的时间内)得到解决。我们的研究将为这类问题带来更快的算法。即使不是在多项式时间内运行的更快的精确算法也可能已经意味着在实践中更大的实例(参见。TSP中的多个城市)可以得到解决。其次，我们希望我们的研究将导致更好地理解NP-Hard问题关于解决它们所需的(最坏情况)时间。由于对于这类问题不太可能获得多项式时间算法，所以我们不能期望开发出比某个阈值更快的精确算法。通过为一些NP-Hard问题开发更快的算法，我们希望找出不同问题的阈值是否以某种方式相互关联。