规范问题列表
有人知道规范 CS 问题的良好参考吗？
我正在考虑诸如“排序问题”、“装箱问题”、“辛苦的推销员问题”之类的问题。
编辑：首选网站
Does anyone known of a a good reference for canonical CS problems?
I'm thinking of things like "the sorting problem", "the bin packing problem", "the travailing salesman problem" and what not.
edit: websites preferred
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
@rcreswick 这些听起来像是很好的参考资料，但与我的想法有点不相符。 （但是，据我所知，这是最好的）
我不会将任何内容标记为已接受，希望人们可以找到更好的参考。
同时，我将在这里列出一些问题，可以随意添加更多
排序问题找到以给定方式单调的集合的顺序
装箱问题 strong> 将一个集合划分为最少数量的集合，其中每个子集都“小于”某个限制
劳累推销员问题 在加权图中找到具有最小总权重的哈密顿循环
@rcreswick those sound like good references but fall a bit shy of what I'm thinking of. (However, for all I know, it's the best there is)
I'm going to not mark anything as accepted in hopes people might find a better reference.
Meanwhile, I'm going to list a few problems here, fell free to add more
The sorting problem Find an order for a set that is monotonic in a given way
The bin packing problem partition a set into a minimum number of sets where each subset is "smaller" than some limit
The travailing salesman problem Find a Hamiltonian cycle in a weighted graph with the minimum total weight
您看过维基百科的 Category:Computational issues 和 类别：NP 完整问题 页？ 它可能并不完整，但它们看起来是很好的起点。 维基百科似乎在计算机科学主题方面做得很好。
Have you looked at Wikipedia's Category:Computational problems and Category:NP Complete Problems pages? It's probably not complete, but they look like good starting points. Wikipedia seems to do pretty well in CS topics.
我认为您不会仅在一本书中找到所有这些问题的答案。 我从未见过任何关于算法的像样的、全面的网站，所以我建议你坚持阅读书籍。 也就是说，您总是可以获得一些有关规范算法文本的介绍性材料（我通常推荐三个：CLRS，Manber，Aho、Hopcroft 和 Ullman（这个在某些关键主题中有点过时，但它是如此正式且写得很好，所以它们都包含重要的组合问题，从某种意义上说，这些问题是计算机科学中的典型问题。在学习了一些图论基础知识后，您将能够转向网络。流和线性规划。这些技术包括最终解决您将遇到的大多数问题的技术（变量仅限于整数值的线性规划是 NP 困难的）。边）在看似与图论没有任何关系的领域中具有非常有趣的应用。 有关这方面的教科书是 Ahuja、Magnanti 和 Orlin 的。 线性规划是网络流的某种超集，涉及优化受线性方程组形式限制的变量的线性函数。 Bazaraa 的是一本强调与网络流关系的书。 然后您可以继续学习整数编程，这是一个非常有价值的工具，它提供了许多用于建模问题的自然技术，例如装箱、任务调度、背包问题等。 一个很好的参考是 L. 沃尔西的书。
I don't think you'll find the answers to all those problems in only one book. I've never seen any decent, comprehensive website on algorithms, so I'd recommend you to stick to the books. That said, you can always get some introductory material on canonical algorithm texts (there are always three I usually recommend: CLRS, Manber, Aho, Hopcroft and Ullman (this one is a bit out of date in some key topics, but it's so formal and well-written that it's a must-read). All of them contain important combinatorial problems that are, in some sense, canonical problems in computer science. After learning some fundamentals in graph theory you'll be able to move to Network Flows and Linear Programming. These comprise a set of techniques that will ultimately solve most problems you'll encounter (linear programming with the variables restricted to integer values is NP-hard). Network flows deals with problems defined on graphs (with weighted/capacitated edges) with very interesting applications in fields that seemingly have no relationship to graph theory whatsoever. THE textbook on this is Ahuja, Magnanti and Orlin's. Linear programming is some kind of superset of network flows, and deals with optimizing a linear function on variables subject to restrictions in the form of a linear system of equations. A book that emphasizes the relationship to network flows is Bazaraa's. Then you can move on to integer programming, a very valuable tool that presents many natural techniques for modelling problems like bin packing, task scheduling, the knapsack problem, and so on. A good reference would be L. Wolsey's book.
您肯定想要查看 NIST 的算法和数据结构词典。 它有旅行推销员问题，拜占庭将军问题，哲学家就餐问题，背包问题（=你的“装箱问题”，我认为），切割库存问题，八皇后问题，< a href="http://www.nist.gov/dads/HTML/knightstour.html" rel="nofollow noreferrer">骑士之旅问题，忙碌海狸问题，停止问题等。
它没有行刑队同步问题（我对这个遗漏感到惊讶）或吉普车问题（比计算机科学更多的物流）。
有趣的是，codinghorror.com 上有一个博客，其中讨论了其中的一些内容拼图形式。 （我不记得我是否读过博客中引用的 Smullyan 的书，但他是谜题和哲学思考的优秀编译者。Martin Gardner 和 Douglas Hofstadter 以及 HE Dudeney 是其他人。）
也可以查看 Stony Brook 算法存储库。
（或者在谷歌上查找“组合问题”，或者在 中搜索“问题” Wolfram Mathworld 或查看希尔伯特问题，但在所有这些链接中许多其中更多的是纯数学而不是计算机科学。）
You definitely want to look at NIST's Dictionary of Algorithms and Data Structures. It's got the traveling salesman problem, the Byzantine generals problem, the dining philosophers' problem, the knapsack problem (= your "bin packing problem", I think), the cutting stock problem, the eight queens problem, the knight's tour problem, the busy beaver problem, the halting problem, etc. etc.
It doesn't have the firing squad synchronization problem (I'm surprised about that omission) or the Jeep problem (more logistics than computer science).
Interestingly enough there's a blog on codinghorror.com which talks about some of these in puzzle form. (I can't remember whether I've read Smullyan's book cited in the blog, but he is a good compiler of puzzles & philosophical musings. Martin Gardner and Douglas Hofstadter and H.E. Dudeney are others.)
Also maybe check out the Stony Brook Algorithm Repository.
(Or look up "combinatorial problems" on google, or search for "problem" in Wolfram Mathworld or look at Hilbert's problems, but in all these links many of them are more pure-mathematics than computer science.)
您可能可以在算法简介等算法教科书中找到最好的内容。 尽管我从未读过那本书，但它因内容详尽而闻名，并且可能包含您可能遇到的大部分问题。
You can probably find the best in an algorithms textbook like Introduction to Algorithms. Though I've never read that particular book, it's quite renowned for being thorough and would probably contain most of the problems you're likely to encounter.
“计算机与难处理性：NP 完备性理论指南”加里和约翰逊对于这类事情是一个很好的参考，尽管书中“已解决”的问题（P）显然没有得到太多关注。
我不知道有什么好的在线资源，但卡普的开创性论文 组合之间的可归约性关于简化和复杂性的问题（1972）可能是困难问题的“规范”参考。
"Computers and Intractability: A guide to the theory of NP-Completeness" by Garey and Johnson is a great reference for this sort of thing, although the "solved" problems (in P) are obviously not given much attention in the book.
I'm not aware of any good on-line resources, but Karp's seminal paper Reducibility among Combinatorial Problems (1972) on reductions and complexity is probably the "canonical" reference for Hard Problems.