對“問題”模組化

摘自：《 The Algorithm Design Manual 》by Steve S. Skiena

劉建文略譯（ http://blog.csdn.net/keminlau）

Modeling the Problem

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.

為問題或任務建造模型是一種藝術，問題的模型是問題的一種描述精确和易了解的形式。适當的建造模型是應用算法設計技術解決任何實際問題的關鍵，因為你可以複用過曾經使用過的模組化經驗（KEMIN：都還沒有給“問題模組化”定位就談經驗是不是有點問題？）。适當模組化是有效使用本書第二部分的問題清單（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.

模組化隻是為問題設計算法的第一步。注意比較你的問題的細節在各個候選模型間差別。不必急于下定論說你的問題很特殊的，暫時忽略一些套不上模型的細節可解開的思維定勢，細心想想它們在本質層面是否一樣的。

參考

Design and Analysis of Algorithms

Data Structures and Algorithms

Alfred V. Aho, Bell Laboratories, Murray Hill, New Jersey

John E. Hopcroft, Cornell University, Ithaca, New York

Jeffrey D. Ullman, Stanford University, Stanford, California

There are many steps involved in writing a computer program to solve a given problem. The steps go from problem formulation and specification, to design of the solution, to implementation, testing and documentation, and finally to evaluation of the solution. This chapter outlines our approach to these steps. Subsequent chapters discuss the algorithms and data structures that are the building blocks of most computer programs.

編寫計算機程式解決一個問題是一個複雜的過程。這個過程包括問題分析和模組化、設計解決方案、代碼實作、測試和編寫文檔，最後對解決方案進行評估。

1.1 From Problems to Programs

Half the battle is knowing what problem to solve. When initially approached, most problems have no simple, precise specification. In fact, certain problems, such as creating a "gourmet" recipe or preserving world peace, may be impossible to formulate in terms that admit of a computer solution. Even if we suspect our problem can be solved on a computer, there is usually considerable latitude in several problem parameters. Often it is only by experimentation that reasonable values for these parameters can be found.

清晰知道待解決的問題是成功的一半。大多數問題一開始并沒有一個簡單的、精确的描述（規格specification）。而且實際上有一些問題，比如建立一個美食食譜之類的現實問題，超出了計算機可處理的範圍。即便是我們認為計算機應該可以處理的問題，也常常要限制問題的一些參數。這也常常需要經驗才能知道……FIXME

If certain aspects of a problem can be expressed in terms of a formal model, it is usually beneficial to do so, for once a problem is formalized, we can look for solutions in terms of a precise model and determine whether a program already exists to solve that problem. Even if there is no existing program, at least we can discover what is known about this model and use the properties of the model to help construct a good solution.

為問題建造形式模型對解決問題是很有益處的。第一可以套用已有問題解決方案；第二，即使沒有現成的例子，形式模型也使問題有迹可循，有助于找到更好的問題的解決方案。

Almost any branch of mathematics or science can be called into service to help model some problem domain. Problems essentially numerical in nature can be modeled by such common mathematical concepts as simultaneous linear equations (e.g., finding currents in electrical circuits, or finding stresses in frames made of connected beams) or differential equations (e.g., predicting population growth or the rate at which chemicals will react). Symbol and text processing problems can be modeled by character strings and formal grammars. Problems of this nature include compilation (the translation of programs written in a programming language into machine language) and information retrieval tasks such as recognizing particular words in lists of titles owned by a library.

幾乎任何一個數學或科學的分支都可以被認為是為某一個問題領域建造模型。數值問題可以被模組化成一些數學概念，像聯立線性方程（simultaneous linear equations）或微分方程（differential equations），聯立線性方程解決如求電路電流量，而微分方程預測人口增長等問題。