有没有人知道有关规范CS问题的良好参考？

我在考虑"分类问题"，"装箱问题"，"行销员问题"等问题。

编辑：网站首选

解决方案

回答

我们可能会在算法教科书(例如《算法简介》)中找到最好的方法。尽管我从未读过这本书，但它以透彻而著称，可能包含我们可能会遇到的大多数问题。

回答

Garey和Johnson的"计算机与难处理性：NP完全性理论指南"是此类问题的重要参考，尽管"解决"问题(P中)显然在书中并未给予太多关注。

我不知道有什么好的在线资源，但是Karp的开创性论文《组合问题之间的可约性》(1972)关于减少和复杂性可能是"难题"的"规范"参考。

回答

我们是否看过Wikipedia的"类别：计算问题"和"类别：NP完整问题"页面？它可能还不完整，但是它们看起来像是很好的起点。 Wikipedia在CS主题方面似乎做得很好。

回答

@rcreswick听起来像是很好的参考，但与我在想的却有些fall。 (但是，据我所知，这是最好的)

我不会将任何内容标记为已接受，希望人们能找到更好的参考。

同时，我将在此处列出一些问题，可以随意添加更多问题

排序问题查找以给定方式单调的集合的顺序

箱装箱问题将一个集合划分为最小数量的集合，其中每个子集"小于"某个限制

棘手的推销员问题在总图最小的加权图中找到哈密顿循环

回答

我认为我们不会在一本书中找到所有这些问题的答案。我从未见过任何像样的，全面的算法网站，因此，建议我们坚持使用本书。就是说，我们总是可以得到有关规范算法文本的入门资料(我通常总是推荐三种：CLRS，Manber，Aho，Hopcroft和Ullman(这在某些关键主题上有​​点过时了，但它是如此正式)并且都写得很好(这是必须阅读的)。所有这些都包含重要的组合问题，从某种意义上说，它们是计算机科学中的规范问题。在学习了图论的一些基础知识之后，我们将可以使用Network Flows和线性编程：这些技术包括一组最终将解决我们将遇到的大多数问题的技术(将变量限制为整数值的线性编程是NP困难的)网络流处理图上定义的问题(具有加权/电容边)在似乎与图论无关的领域中有非常有趣的应用，有关的教科书是Ahuja，Magnanti和Orlin's。线性编程是某种网络流的超集，并且处理以方程式线性系统形式对受约束的变量的线性函数进行优化。 Bazaraa是一本强调与网络流量关系的书。然后，我们可以继续进行整数编程，这是一个非常有价值的工具，它提供了许多用于对诸如装箱，任务调度，背包问题等问题建模的自然技术。一个很好的参考书是L. Wolsey的书。

回答

我们肯定想看一下NIST的算法和数据结构字典。它有旅行推销员问题，拜占庭将军问题，进餐哲学家问题，背包问题(我认为是"箱包装问题")，切削问题，八皇后问题，骑士旅行问题，繁忙的海狸问题，停顿问题等。

它没有射击队同步问题(我对此遗漏感到惊讶)或者吉普车问题(比计算机科学更多的后勤)。

有趣的是，在codinghorror.com上有一个博客，其中以拼图形式讨论了其中一些博客。 (我不记得我是否读过博客中引用的Smullyan的书，但他是难题和哲学思考的很好的编译器。MartinGardner和Douglas Hofstadter和H.E. Dudeney就是其他人。)

也可以查看Stony Brook算法存储库。

(或者在Google上查找"组合问题"，或者在Wolfram Mathworld中搜索"问题"，或者查看希尔伯特的问题，但是在所有这些链接中，许多链接都是比计算机科学更纯粹的数学。)