对“问题”建模

《算法设计手册》

• 摘自：《The Algorithm Design Manual 》
• 作者：Steve S. Skiena

Modeling is the art of formulating your application in terms of precisely described, well-understood problems. Proper modeling is the key to applying algorithmic design techniques to any real-world problem. Indeed, proper modeling can eliminate the need to design or even implement algorithms by relating your application to what has been done before. Proper modeling is the key to effectively using the problem catalog in Part II of this book.

为问题或任务建造模型是一种艺术，问题的模型是问题的一种描述精确和易理解的形式。适当的建造模型是应用算法设计技术解决任何实际问题的关键，因为你可以复用过曾经使用过的建模经验。适当建模是有效使用本书第二部分的问题清单（problem catalog）的关键。

Real-world applications involve real-world objects. You might be working on a system to route traffic in a network, to find the best way to schedule classrooms in a university, or to search for patterns in a corporate database. Most algorithms, however, are designed to work on rigorously defined abstract structures such as permutations, graphs, and sets. After all, if you can't define what you want to do, you can't hope to compute it. You must first describe your problem abstractly, in terms of fundamental structures and properties.

真实世界处理是真实的对象。你可能处理诸如这样的问题：设计一个网络通信的路由系统、为大学找出最佳的课程表、或者查找公司数据的某条记录。但是，大部分算法被设计成处理有严格定义的抽象结构，如列表、图和集合。问题来了，你无法定义你想要做什么，那么你也就没法知道如何去处理（计算）它。因此，你必须先抽象地描述你的问题，以一些基本的结构和属性。

Whatever your application is, odds are very good that others before you have stumbled upon the same algorithmic problem, perhaps in substantially different contexts. Therefore, to find out what is known about your particular widget optimization problem,'' you can't hope to look in a book under widget. You have to formulate widget optimization in terms of computing properties of abstract structures such as:

l Permutations, which are arrangements, or orderings, of items. For example,{4,2,3,1} and {1,2,3,4} are two distinct permutations of the same set of four integers. Permutations are likely the object in question whenever your problem seeks an arrangement,'' tour,'' ordering,'', or sequence.''

排列，就是元素的安排或排序。问题如找出…………用到的都是排列

l Subsets, which represent selections from a set of items. For example, {1,3,4} and {2} are two distinct subsets of the first four integers. Order does not matter in subsets the way it does with permutations, so the subsets {1,3,4} and {3,4,1} would be considered identical. Subsets are likely the object in question whenever your problem seeks a cluster,'' collection,'' committee,'' group,'' packaging,'' or selection.''

子集（组合），就是从一预定的集合中选择一些元素。子集（组合）内的元素的顺序是无关的。

Trees, which represent hierarchical relationships between items. Figure (a) illustrates a portion of the family tree of the Skiena clan. Trees are likely the object in question whenever your problem seeks a hierarchy,'' dominance relationship,'' ancestor/decendant relationship,'' or taxonomy.''

树

l Graphs, which represent relationships between arbitrary pairs of objects. Figure (b) models a network of roads as a graph, where the vertices are cities and the edges are roads connecting pairs of cities. Graphs are likely the object in question whenever you seek a network,'' circuit,'' web,'' or relationship.''

图

l Points, which represent locations in some geometric space. For example, the locations of McDonald's restaurants can be described by points on a map/plane. Points are likely the object in question whenever your problems work on sites,'' positions,'' data records,'' or locations.''

点

l Polygons, which represent regions in some geometric space. For example, the borders of a country can be described by a polygon on a map/plane. Polygons and polyhedra are likely the object in question whenever you are working on shapes,'' regions,'' configurations,'' or boundaries.''

多边形

l Strings, which represent sequences of characters or patterns. For example, the names of students in a class can be represented by strings. Strings are likely the object in question whenever you are dealing with text,'' characters,'' patterns,'' or labels.''

字串

These fundamental structures all have associated problems and properties, which are presented in the catalog of Part II. Familiarity with all of these problems is important, because they provide the language we use to model applications. To become fluent流利的; 流畅的 in this vocabulary, browse through the catalog and study the input and output pictures for each problem. Understanding all or most of these problems, even at a cartoon/definition level, will enable you to know where to look later when the problem arises in your application.

这些基本结构全都有相对应的问题类型和属性，这些内容在本书第二部分的有一个清单（problem catalog）。熟悉所有这些问题类型是重要的，因为它们为你提供了问题建模的语言。要熟练掌握建模词汇，可浏览那问题清单并逐一研究每个问题的输入和输出图。理解了所有或大部分这些问题类型（即使是很初步的了解）可让你在遇到实际问题时不致于迷失方向而手足无措。

Examples of successful application modeling will be presented in the war stories spaced throughout this book. However, some words of caution are in order. The act of modeling reduces your application to one of a small number of existing problems and structures. Such a process is inherently constraining, and certain details might not fit easily into the given model. Also, certain problems can be modeled in several different ways, some much better than others.

本书介绍一个成功的问题建模例子--战争故事。建模的时候有些东西是要注意的……FIXME……这个过程是固有的约束，一些细节并不能很好对上指定的模型。还有，一个特定的问题可有多种建模方式，其中有优劣之分。

Modeling is only the first step in designing an algorithm for a problem. Be alert for how the details of your applications differ from a candidate model. But don't be too quick to say that your problem is unique and special. Temporarily ignoring details that don't fit can free the mind to ask whether they were fundamental in the first place.

建模只是为问题设计算法的第一步。注意比较你的问题的细节在各个候选模型间区别。不必急于下定论说你的问题很特殊的，暂时忽略一些套不上模型的细节可解开的思维定势，细心想想它们在本质层面是否一样的。