算法问题清单

摘自：《The Algorithm Design Manual 》
刘建文略译（http://blog.csdn.net/keminlau）
A Catalog of Algorithmic Problems

Preface

Most of the professional programmers that I've encountered are not well prepared to tackle algorithm design problems. This is a pity, because the techniques of algorithm design form one of the core practical technologies of computer science. Designing correct, efficient, and implementable algorithms for real-
world problems is a tricky business, because the successful algorithm designer needs access to two distinct bodies of knowledge:

如何为计算机问题设计算法？设计过程是否有法可循？虽然算法设计经多年经验积累已经成为（计算机科学）一种核心技术（即有法可循），为问题设计出正确、有效和可实现的算法还是经验活、麻烦活。一位成功的算法设计者必须学会使用两个关键的知识或工具：

• l Techniques - Good algorithm designers understand several fundamental algorithm design techniques, including data structures, dynamic programming, depth-first search, backtracking, and heuristics. Perhaps the single most important design technique is modeling, the art of abstracting a messy real-world application into a clean problem suitable for algorithmic attack.

设计技术：一位合格的算法设计者必须掌握几项基本的算法设计技术，包括数据结构、动态规划、深度优先搜索、回溯方法和启发方法。或许，为“问题”建模的技术是重中之重；建模是一种抽象机制，它清理干净“毛茸茸”的问题，使它适合算法处理。

• l Resources - Good algorithm designers stand on the shoulders of giants. Rather than laboring from scratch to produce a new algorithm for every task, they know how to find out what is known about a particular problem. Rather than reimplementing popular algorithms from scratch, they know where to seek existing implementations to serve as a starting point. They are familiar with a large set of basic algorithmic problems, which provides sufficient source material to model most any application.

现有资源：合格的算法设计者是站在巨人的肩膀上的。业界已经为各种计算问题设计了算法，不要试图去从头开始为一个计算问题设计新的算法。成功的算法设计者应该对一些基本的算法了如指掌。

KEMIN:算法和问题是一体两面，没有问题哪来算法，要算法要干什么？所以研究算法转为研究问题，算法是抽象的，而问题是比较具体的，所以弄清楚计算需要处理什么样的问题，把它们归类是很重要的。

A Catalog of Algorithmic Problems算法问题清单

This is a catalog of algorithmic problems that arise commonly in practice. It describes what is known about them and gives suggestions about how best to proceed if the problem arises in your application.

本算法问题清单是对实践中反复出现的问题的总结。清单每项给出对问题的认识经验和处理它的一般建议。

What is the best way to use this catalog? First, think a little about your problem. If you recall the name of your problem, look up the catalog entry in the index or table of contents and start reading. Read through the entire entry, since it contains pointers to other relevant problems that might be yours. If you don't
find what you are looking for, leaf through the catalog, looking at the pictures and problem names to see if something strikes a chord. Don't be afraid to use the index, for every problem in the book is listed there under several possible keywords and applications. If you still don't find something relevant, your
problem is either not suitable for attack by combinatorial algorithms or else you don't fully understand it. In either case, go back to step one.

怎么使用本问题清单？首先，回想起你的问题的名字（或相关信息），并根 据它开始查阅本书索引或清单的目录；如果找到对应的条目，通读整条条目，因为条目内会有指向相关问题的链接，而那些问题很可能就是你的问题。如果目录索引 找不到，那么浏览整个清单，从每条条目的大概内容看能不能找到共鸣。千万不要嫌麻烦而不使用索引，因为本书的每一个问题的可能关键字都会列入索引。如果你 仍然没能找到相关的问题，你的问题要么不适合用组合算法处理，要么你还没有完全弄明的你的问题。无论是哪一个，都返回第一步重新开始。

The catalog entries contain a variety of different types of information that have never been collected in one place before. Different fields in each entry present information of practical and historical interest.
FIXME

To make this catalog more easily accessible, we introduce each problem with a pair of graphics representing the problem instance or input on the left and the result of solving the problem on this instance on the right. We have invested considerable thought in selecting stylized images and examples that illustrate desired behaviors, more than just definitions. For example, the minimum spanning tree example illustrates how points can be clustered using minimum spanning trees. We hope that people without a handle on algorithmic terminology can flip through 浏 览 the pictures and identify which problems might be relevant to them. We augment these pictures with more formal written input and problem descriptions in order to eliminate any ambiguity inherent in a purely pictorial( 绘画的, 用图画表示的, 插图的)representation.

为了提高清单的可读性，我们为每个问题 设计了一对展示问题实例的输入和输出的插图。我们精心的设计问题的插图和描述问题行为的例子，而不是仅仅的给出文字定义。比如，最小生成树的例子，它的插 图展示了图节点是如何通过最小生成树聚簇在一起的。我们希望不十分熟悉算法术语（词汇）的人们可以通过浏览这些形象的插图迅速辨认出自己的问题。此外，为 了进一步去除单纯插图式展示的潜在模糊性，我们还增加了更形式化的问题描述。

Once you have identified your problem of interest, the discussion section tells you what you should do about it. We describe applications where the problem is likely to arise and special issues associated with data from them. We discuss the kind of results you can hope for or expect and, most importantly, what you should do to get them. For each problem, we outline a quick-and-dirty algorithm and pointers to algorithms to try next if the first attempt is not sufficient. We also identify other, related problems in the catalog.

For most if not all of the problems presented, we identify readily available software implementations, which are discussed in the implementation field of each entry. Many of these routines are quite good, and they can perhaps be plugged directly into your application. Others will be incomplete or inadequate
for production use, but they hopefully can provide a good model for your own implementation. In general, the implementations are listed in order of descending usefulness, but we will explicitly recommend the best one available for each problem if a clear winner exists. More detailed information for many of these implementations appears in Chapter . Essentially all of the implementations are available via the WWW site associated with this book, reachable at http://www.cs.sunysb.edu/algorith.

Finally, in deliberately smaller print, we discuss the history of each problem and present results of primarily theoretical interest. We have attempted to report the best results known for each problem and point out empirical comparisons of algorithms if they exist. This should be of interest to students and researchers, and also to practitioners for whom our recommended solutions prove inadequate and who need to know if anything better is possible

• l Data Structures 数据结构
• Dictionaries
• Priority Queues
• Suffix Trees and Arrays
• Graph Data Structures
• Set Data Structures
• Kd-Trees
• l Numerical Problems数值问题
• Solving Linear Equations
• Bandwidth Reduction
• Matrix Multiplication
• Determinants and Permanents
• Constrained and Unconstrained Optimization
• Linear Programming
• Random Number Generation
• Factoring and Primality Testing
• Arbitrary-Precision Arithmetic
• Knapsack Problem
• Discrete Fourier Transform
• l Combinatorial Problems 组合问题
• Sorting
• Searching
• Median and Selection
• Generating Permutations
• Generating Subsets
• Generating Partitions
• Generating Graphs
• Calendrical Calculations
• Job Scheduling
• Satisfiability
• l Graph Problems: Polynomial-Time 图问题（多项式时间）
  
• Connected Components
• Topological Sorting
• Minimum Spanning Tree
• Shortest Path
• Transitive Closure and Reduction
• Matching
• Eulerian Cycle / Chinese Postman
• Edge and Vertex Connectivity
• Network Flow
• Drawing Graphs Nicely
• Drawing Trees
• Planarity Detection and Embedding
• l Graph Problems: Hard Problems 图问题（困难问题）
• Clique
• Independent Set
• Vertex Cover
• Traveling Salesman Problem
• Hamiltonian Cycle
• Graph Partition
• Vertex Coloring
• Edge Coloring
• Graph Isomorphism
• Steiner Tree
• Feedback Edge/Vertex Set
• l Computational Geometry 计算几何问题
  
• Robust Geometric Primitives
• Convex Hull
• Triangulation
• Voronoi Diagrams
• Nearest Neighbor Search
• Range Search
• Point Location
• Intersection Detection
• Bin Packing
• Medial-Axis Transformation
• Polygon Partitioning
• Simplifying Polygons
• Shape Similarity
• Motion Planning
• Maintaining Line Arrangements
• Minkowski Sum
• l Set and String Problems
  
• Set Cover
• Set Packing
• String Matching
• Approximate String Matching
• Text Compression
• Cryptography
• Finite State Machine Minimization
• Longest Common Substring
• Shortest Common Superstring

参考

• 对“问题”建模
• “问题”是什么？