`
buliedian
  • 浏览: 1243785 次
  • 性别: Icon_minigender_2
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论
阅读更多

对“问题”建模

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),联立线性方程解决如求电路电流量,而微分方程预测人口增长等问题。

分享到:
评论

相关推荐

    背包问题 数学建模 背包问题 数学建模

    背包问题 数学建模 背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: ...

    数学建模仓库选址问题

    "数学建模仓库选址问题" 数学建模仓库选址问题是指在某个地区内,存在多个商品粮生产基地,每个基地的粮食数量不同,为了使得这些基地到仓库的总运费最小,需要确定仓库的位置。这个问题可以通过数学建模来解决。 ...

    捕鱼问题数学建模最优捕捞策略

    在探讨自然资源管理与环境保护问题时,捕鱼问题作为典型例证,常常成为数学建模竞赛的议题。捕捞活动不仅要满足人类的食品需求,还要确保生态系统的长期稳定与生物种群的可持续发展。本文以“捕鱼问题数学建模最优...

    数学建模——人员安排问题.pdf

    数学模型的建立通常需要对问题进行深入的分析和理解,涉及数学理论和计算机软件的综合运用。在本案例中,数学建模被应用于解决“人员安排问题”。 人员安排问题通常指的是在特定约束条件下,如何合理地安排人员的...

    数学建模论文 评卷分配问题

    本文以大学生数学建模评卷分配问题为研究对象,提出了基于数学建模的优化分配方法,旨在为这一问题提供解决方案。 在数学建模中,问题往往需要被简化以方便求解。本文采用平均分配原则,即根据各题组的试卷总数,将...

    数学建模 自习室问题

    【数学建模】是利用数学方法来解决实际问题的一种手段,尤其在教育领域,它常被用于优化资源分配,提高效率。在这个自习室问题中,数学建模的应用旨在解决大学晚自习教室的开放管理,以减少电力浪费并满足学生的需求...

    数学建模最短路问题

    内容很详细,主要介绍了数学建模里面最短路问题!对参加数学建模的同学一定会有帮助~!

    数学建模农作物种植问题.doc

    《数学建模在农作物种植问题中的应用》 数学建模是一种将实际问题转化为数学问题,通过数学工具进行求解的方法,广泛应用于各个领域,其中包括农业。农作物种植问题就是这样一个典型的实例,它涉及到土地利用效率、...

    油价问题的数学建模[定义].pdf

    油价问题的数学建模是对油价的合理定价机制的研究和探索。油价的上涨将对社会各个层面带来影响,包括农民的收入、快递公司与网购者的影响、油站燃油供给紧张等。因此,探索一种可靠的油价定价机制是非常必要的。 一...

    数学建模之自来水管道铺设问题代码.rar

    《数学建模与MATLAB在自来水管道铺设问题中的应用》 数学建模是解决实际问题的重要工具,尤其在工程领域,如自来水管道铺设问题。在这个问题中,我们需要考虑如何优化管道布局,以确保水源能够有效地输送到每个用户...

    数学建模(资源分配问题)

    数学建模是一种应用数学工具解决实际问题的方法,它在资源分配问题中发挥着关键作用。在本案例中,我们面临的是一个塑料制品...本案例展示了如何利用数学建模解决企业资源分配问题,对初学者来说是一个很好的实践案例。

    报童问题 数学建模 代码

    数学建模 报童 数学建模典型问题,很简单实现容易理解

    神经网络对复杂系统建模.docx

    2. 模型复杂度问题:神经网络对复杂系统建模需要考虑模型的复杂度,过高的复杂度可能会导致模型的不稳定性。 3. 可解释性问题:神经网络对复杂系统建模的结果可能不易解释,需要进行进一步的分析和解释。 六、结论 ...

    数学建模论文数学建模best

    1. **问题理解**:任何数学建模活动的起点是对所给问题的理解。这不仅包括对问题背景的深入挖掘,还需要明确问题的最终目标。理解问题过程中,应收集相关领域的知识,这有助于更准确地界定问题的关键所在。 2. **...

    关于零件参数问题的建模.pdf数学建模

    为了解决这个问题,需要对零件参数进行建模和优化。零件参数问题是一个复杂的问题,它涉及到多个参数的交互作用,例如零件的尺寸、材料、加工工艺等。 二、问题的假设模型 为了建立数学模型,需要对零件参数问题...

    2021年五一数学建模b题消防救援问题论文+matlab代码(及代码所需文件)

    这篇压缩包文件包含的是2021年五一数学建模竞赛中的B题——消防救援问题的相关研究论文和MATLAB代码。数学建模是一项利用数学工具解决实际问题的比赛,旨在培养学生的创新思维、团队协作和问题解决能力。在这个案例...

    数学建模[高考公平性问题+饭店餐桌布局]

    在数学建模领域,我们经常会遇到各种实际问题的抽象与解决。本次提供的压缩包文件包含了两个具体的案例,分别是“高考公平性问题”和“饭店餐桌布局”。这两个话题都是日常生活和社会运行中常见的问题,通过数学建模...

    华中数学建模网-提供数学建模论文、数学建模及其数学建模竞赛题目

    在数学建模领域,华中数学建模网是一个重要的资源平台,它专注于提供数学建模相关的论文、资料以及数学建模竞赛的题目,为学生、教师以及对数学建模感兴趣的人员提供了丰富的学习材料。数学建模是应用数学解决实际...

Global site tag (gtag.js) - Google Analytics