没有合适的资源?快使用搜索试试~ 我知道了~
首页动态规划原理:抽象框架与解题策略
动态规划原理:抽象框架与解题策略
需积分: 5 0 下载量 192 浏览量
更新于2024-07-17
收藏 124KB PDF 举报
本文档探讨了动态规划的一种抽象框架——估值网络(Valuation Network, VN),它是一种用于表示和解决离散优化问题的有效工具。在VN中,问题的结构被转换为一系列称为估值的函数,这些函数代表了目标函数的不同组成部分。核心概念包括组合操作和边际化操作。 组合操作的作用是将目标函数中的各个因子整合成全局目标函数,也称为联合估值。这个过程类似于在数学优化中合并各个局部最优解来形成整体最优解。而边际化操作则是最大化或最小化,它可以用来评估某个决策变量改变时对整体目标的影响,这对于寻找局部最优解至关重要。 在解决VN的过程中,关键在于定义一组简单但基本的公理(Axioms),这些公理确保了组合和边际化操作能够通过局部计算得到有效的解决方案。通过满足这些公理,我们可以利用局部信息来推导全局最优解,这就是动态规划的核心思想。 文档进一步介绍了一种名为融合算法(Fusion Algorithm)的方法,它基于这些公理设计,旨在通过局部计算来解决VN。对于优化问题而言,这种算法在非串行环境下等价于经典的动态规划方法。因此,融合算法可以被视为动态规划方法的一种抽象描述,而那些公理则成为了应用动态规划的前提条件。 总结来说,本论文提供了一个框架,使得动态规划原理能够在复杂的离散优化问题中得以应用,通过明确的规则和公理确保了解决过程的有效性和效率。这不仅扩展了动态规划的适用范围,也为理解和实践动态规划提供了一种新的视角。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/10945239/bg3.jpg)
33
2 VALUATION NETWORKS AND OPTIMIZATION
A valuation network consists of valuations, combination, and marginalization. We will discuss
each of these in detail. We will illustrate all definitions using an optimization problem from Bertele
and Brioschi [1972].
An Optimization Problem. There are five variables labeled A, B, C, D, and E. Each
variable has two possible values. Let a and ~a denote the possible values of A, etc. The global
objective function f for variables A, B, C, D, and E factors additively as follows: f = f
1
+ f
2
+
f
3
, where f
1
is a function for E, A, and C, f
2
is a function for B and A, and f
3
is a function for E,
B, and D. Table I shows the details of these three functions. The problem is to find the minimum
value of f and to find a configuration of all variables where the minimum value is achieved.
Variables, State Spaces, and Configurations. We use the symbol W
X
for the set of
possible values of a variable X, and we call W
X
the state space for X. We are concerned with a
finite set Q of variables, and we assume that all the variables in Q have finite state spaces.
Given a finite non-empty set h of variables, let W
h
denote the Cartesian product of W
X
for X in
h, i.e., W
h
= ´{W
X
| X Î h}. We call W
h
the state space for h. We call elements of W
h
configurations of h. Lower-case bold-faced letters, x, y, etc., will denote configurations. If x is a
configuration of g, y is a configuration of h, and gÇh = Æ, then (x, y) will denote the
configuration of gÈh obtained by concatenating x and y.
It is convenient to allow the set of variables h to be empty. We adopt the convention that the
state space for the empty set Æ consists of a single element, and we use the symbol ¨ to name that
element; W
Æ
= {¨}. If x is a configuration of g, then (x, ¨) is simply x.
Values and Valuations. We are concerned with a set D whose elements are called values.
D may be finite or infinite. Given a set h of variables, we call any function s: W
h
® D, a valuation
for h, and we call h the domain of s. Note that to specify a valuation s for Æ, we need to specify
only a single value, s(¨). We will use lower-case Greek letters to denote valuations.
In our optimization problem, the set D is the set of real numbers, and we have three valuations
f
1
, f
2
and f
3
. f
1
is a valuation for {E, A, C}, f
2
is a valuation for {B, A}, and f
3
is a valuation
Table I.
The Factors of the Objective Function, f
1
, f
2
, and f
3
W
{E, A, C}
f
1
W
{B, A}
f
2
W
{E, B, D}
f
3
eac 1 ba 4 ebd 0
e a ~c 5 b ~a 0 e b ~d 6
e~ac 2 ~ba 8 e~bd 5
e ~a ~c 2 ~b ~a 5 e ~b ~d 4
~eac 3 ~ebd 5
~e a ~c 8 ~e b ~d 3
~e ~a c 6 ~e ~b d 1
~e ~a ~c 4 ~e ~b ~d 3
剩余14页未读,继续阅读
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/9b43a40c1e524d39b560b39c690e7d29_tianyuanzk.jpg!1)
tianyuanzk
- 粉丝: 0
- 资源: 7
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 构建Cadence PSpice仿真模型库教程
- VMware 10.0安装指南:步骤详解与网络、文件共享解决方案
- 中国互联网20周年必读:影响行业的100本经典书籍
- SQL Server 2000 Analysis Services的经典MDX查询示例
- VC6.0 MFC操作Excel教程:亲测Win7下的应用与保存技巧
- 使用Python NetworkX处理网络图
- 科技驱动:计算机控制技术的革新与应用
- MF-1型机器人硬件与robobasic编程详解
- ADC性能指标解析:超越位数、SNR和谐波
- 通用示波器改造为逻辑分析仪:0-1字符显示与电路设计
- C++实现TCP控制台客户端
- SOA架构下ESB在卷烟厂的信息整合与决策支持
- 三维人脸识别:技术进展与应用解析
- 单张人脸图像的眼镜边框自动去除方法
- C语言绘制图形:余弦曲线与正弦函数示例
- Matlab 文件操作入门:fopen、fclose、fprintf、fscanf 等函数使用详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)