算法问题清单
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
参考
分享到:
相关推荐
算法岗位准备清单1
python优化算法工具包-整理一份可以让Python变得更快的工具清单,排序算法数据结构 最快的排序算法
程序员实用算法+源码,本书一共七个部分全部下载才可正常解压
蚁群优化算法求解旅行商问题。内有代码有报告 1、理解蚁群优化算法的思想。 2、利用 Matlab 实现蚁群优化算法求解 TSP 问题。 3、分析算法中各种参数变化对计算结果的影响。 二、实验要求 1、打印程序清单。 2...
TSP问题的遗传算法求解方案--源程序清单(旅行商问题,包含算法介绍,源程序,测试结果).doc
Dummy Loves算法和数据结构 描述 这是一个存放我在工作或学习中遇到的所有有趣算法...算法问题清单 给定总和的可能组合数 给定总和的可能组合列表 给定金额所需的最少硬币数量 预购遍历 订单遍历 水平顺序遍历 通过预订
互联网外包项目需求清单模板
TSP问题的遗传算法求解方案--源程序清单(旅行商问题,包含算法介绍,源程序,测试结果).doc
主要代码清单: #include "stdio.h" #include "conio.h" int board[8][8] ={ {0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,...
模拟退火算法求解旅行商问题,有代码 1、理解模拟退火算法的思想。 2、利用 Matlab 实现模拟退火算法求解 TSP 问题。 3、分析算法中各种参数变化对计算结果的影响。 二、实验要求 1、打印程序清单。 2、绘制...
理解遗传算法的基本思想和基本流程,应用 Sheffield 遗传算法工具箱和 Matlab 神经网 络工具箱,完成基于遗传算法的 BP 神经网络的初始权阈值的优化,分析算法中各种参数变 化对计算结果的影响,并比较未使用遗传...
如今大多数关于算法的图书都是大学教科书,或者是令人厌倦的相同算法集合改头换面后的作品。本书是给出所有算法的完整代码实现的第一本书,这些算法在开发人员的日常工作中非常有用。. 本书重点关注的是实用,立即...
清单和定额的算法分享.pdf
### 2 神经网络回归预测、时序预测、分类清单 **2.1 bp预测和分类** **2.2 lssvm预测和分类** **2.3 svm预测和分类** **2.4 cnn预测和分类** ##### **2.5 ELM预测**和分类 ##### **2.6 KELM预测**和分类 **...
2、利用 Matlab 实现粒子群算法求解函数优化问题。 3、分析算法中各种参数变化对计算结果的影响。 1、打印程序清单。 2、绘制每代个体适应度值变化图,记录算法的最优解。 3、分析惯性权重的变换对求解性能的...
AI算法岗求职攻略(涵盖准备攻略、刷题指南、内推和AI公司清单等资料)
本实验目的是通过使用银行家算法实现系统资源的分配和安全性检查模拟,提高学生对操作系统资源分配功能...4)按照实验题目要求独立正确地完成实验内容(编写、调试算法程序,提交程序清单及及相关实验数据与运行结果)
在Visual C++ 编译环境下,模拟退火算法程序,并利用它们求解了48个城市的TSP问题。 2.程序说明 由于篇幅有限,且程序中还包括界面实现和计算线程处理等一些与算法无关的代码。为方便阅读,程序清单只介绍实现算法...
目 录 一、概述 3 1、设计目的 3 2、开发环境 3 3、任务分配 3 二、需求分析 4 1、死锁概念: 4 2、关于死锁的一些结论: 4 ...5、源程序清单 13 五、结束语 21 1、心得与体会: 21 2、实例: 21 六、参考文献 23
程序员实用算法(算法领导三架马车之一,与《算法导论》完美搭档)