Computational complexity of combinatorial and graph theoretic problems

组合和图论问题的计算复杂性

• 批准号: 183871-2009
• 负责人: Brewster, Richard
• 金额: $ 1.38万
• 依托单位: Thompson Rivers University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=522979
• 关键词: Computational; complexity; combinatorial; graph; theoretic

The speed and power of modern computers is truly impressive. So much so, that one might believe any reasonable problem can be solved, even by brute force, in reasonable time. Surprisingly this is not the case. Consider the problem of assigning resources to a collection of users, for example scheduling teams in a round robin tournament. The goal is to assign the resources in the most efficient way possible, subject to constraints restricting the assignments. This a Constraint Satisfaction Problem or CSP. For a fast computer to exhaustively search through all the possible combinations looking for the optimum assignment could take thousands of years. This is an example of "combinatorial explosion"; the sheer number of combinations defeats brute force solutions. More efficient algorithms, if they exist, must be employed.

现代计算机的速度和能力确实令人印象深刻。因此，人们可能会相信，任何合理的问题都可以在合理的时间内解决，即使是通过蛮力。令人惊讶的是，情况并非如此。考虑将资源分配给一组用户的问题，例如，在循环赛中安排球队。目标是以尽可能最有效的方式分配资源，但要受到限制分配的限制。这是一个约束满足问题或CSP。对于一台快速的计算机来说，彻底搜索所有可能的组合以寻找最佳分配可能需要数千年的时间。这是一个“组合爆炸”的例子；组合的绝对数量击败了暴力解决方案。必须采用更有效的算法，如果它们存在的话。