有没有人知道规范 CS 问题的良好参考？
我在想诸如“分类问题”、“装箱问题”、“劳苦推销员问题”之类的东西。
编辑：首选网站
BCS
问问题
745 次
6 回答
4
您可能可以在诸如Introduction to Algorithms之类的算法教科书中找到最好的。尽管我从未读过那本书，但它以详尽而闻名，并且可能包含您可能遇到的大部分问题。
于 2008-08-30T01:00:11.707 回答
4
Garey 和 Johnson的“Computers and Intractability: A guide to the theory of NP-Completeness”是这类事情的一个很好的参考，尽管“解决的”问题（在 P 中）显然在书中没有给予太多关注。
我不知道有什么好的在线资源，但卡普关于减少和复杂性的开创性论文Reducibility between Combinatorial Problems (1972)可能是 Hard Problems 的“规范”参考。
于 2008-08-30T01:07:50.020 回答
3
您是否查看过维基百科的分类：计算问题和分类：NP 完整问题页面？它可能不完整，但它们看起来像是很好的起点。维基百科似乎在 CS 主题方面做得很好。
于 2008-08-30T03:14:09.653 回答
3
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.
于 2008-09-17T23:26:59.600 回答
2
你肯定想看看 NIST's Dictionary of Algorithms and Data Structures。它有旅行商问题、拜占庭将军问题、哲学家进餐问题、背包问题（我认为=你的“装箱问题”）、切货问题、八皇后问题、骑士之旅问题、忙碌的海狸问题，停机问题等。
它没有行刑队同步问题（我对这个遗漏感到惊讶）或吉普问题（比计算机科学更多的后勤问题）。
有趣的是，codinghorror.com上有一个博客，它以拼图的形式讨论了其中的一些。（我不记得我是否读过博客中引用的 Smullyan 的书，但他是谜题和哲学思考的优秀编译器。Martin Gardner 和 Douglas Hofstadter 和HE Dudeney是其他人。）
也可以查看Stony Brook Algorithm Repository。
（或在 google 上查找“组合问题”，或在Wolfram Mathworld中搜索“问题”或查看Hilbert 的问题，但在所有这些链接中，其中许多是纯数学而非计算机科学。）
于 2009-01-24T21:49:01.940 回答
0
@rcreswick 这些听起来像是很好的参考，但对我的想法有点害羞。（但是，据我所知，这是最好的）
我不会将任何内容标记为已接受，希望人们可以找到更好的参考。
同时，我将在这里列出一些问题，随意添加更多
排序问题找到以给定方式单调的集合的顺序
装箱问题将一个集合划分为最小数量的集合，其中每个子集“小于”某个限制
苦行推销员问题在具有最小总权重的加权图中找到一个哈密顿循环
于 2008-09-01T04:27:27.057 回答