Roberry_house_dynamicprogramming_源码资源-CSDN文库

共2个文件

pdf：1个

cpp：1个

版权申诉

house

dynamicprogramming

148 浏览量 2021-10-04 02:19:33 上传评论收藏 333KB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

Roberry.zip （2个子文件）

Roberry

capitulo7.pdf 740KB

Roberry.cpp 1KB

533

Dynamic Programming

Dynamic programming is a useful mathematical technique for making a sequence of in-

terrelated decisions. It provides a systematic procedure for determining the optimal com-

bination of decisions.

In contrast to linear programming, there does not exist a standard mathematical for-

mulation of “the” dynamic programming problem. Rather, dynamic programming is a gen-

eral type of approach to problem solving, and the particular equations used must be de-

veloped to fit each situation. Therefore, a certain degree of ingenuity and insight into the

general structure of dynamic programming problems is required to recognize when and

how a problem can be solved by dynamic programming procedures. These abilities can

best be developed by an exposure to a wide variety of dynamic programming applications

and a study of the characteristics that are common to all these situations. A large number

of illustrative examples are presented for this purpose.

11.1 A PROTOTYPE EXAMPLE FOR DYNAMIC PROGRAMMING

EXAMPLE 1 The Stagecoach Problem

The STAGECOACH PROBLEM is a problem specially constructed

to illustrate the fea-

tures and to introduce the terminology of dynamic programming. It concerns a mythical

fortune seeker in Missouri who decided to go west to join the gold rush in California dur-

ing the mid-19th century. The journey would require traveling by stagecoach through un-

settled country where there was serious danger of attack by marauders. Although his start-

ing point and destination were fixed, he had considerable choice as to which states (or

territories that subsequently became states) to travel through en route. The possible routes

are shown in Fig. 11.1, where each state is represented by a circled letter and the direc-

tion of travel is always from left to right in the diagram. Thus, four stages (stagecoach

runs) were required to travel from his point of embarkation in state A (Missouri) to his

destination in state J (California).

This fortune seeker was a prudent man who was quite concerned about his safety. Af-

ter some thought, he came up with a rather clever way of determining the safest route. Life

This problem was developed by Professor Harvey M. Wagner while he was at Stanford University.

| | | |

▲

e-Text Main Menu

Textbook Table of Contents

insurance policies were offered to stagecoach passengers. Because the cost of the policy

for taking any given stagecoach run was based on a careful evaluation of the safety of that

run, the safest route should be the one with the cheapest total life insurance policy.

The cost for the standard policy on the stagecoach run from state i to state j,which

will be denoted by c

,is

534 11 DYNAMIC PROGRAMMING

746

324

415

243

BCD EFG HI J

These costs are also shown in Fig. 11.1.

We shall now focus on the question of which route minimizes the total cost of the

policy.

Solving the Problem

First note that the shortsighted approach of selecting the cheapest run offered by each suc-

cessive stage need not yield an overall optimal decision. Following this strategy would

give the route A  B  F  I  J, at a total cost of 13. However, sacrificing a little on

one stage may permit greater savings thereafter. For example, A  D  F is cheaper

overall than A  B  F.

One possible approach to solving this problem is to use trial and error.

However, the

number of possible routes is large (18), and having to calculate the total cost for each

route is not an appealing task.

C F

D G

B E

FIGURE 11.1

The road system and costs

for the stagecoach problem.

This problem also can be formulated as a shortest-path problem (see Sec. 9.3), where costs here play the role

of distances in the shortest-path problem. The algorithm presented in Sec. 9.3 actually uses the philosophy of

dynamic programming. However, because the present problem has a fixed number of stages, the dynamic pro-

gramming approach presented here is even better.

| | | |

▲

e-Text Main Menu

Textbook Table of Contents

Fortunately, dynamic programming provides a solution with much less effort than ex-

haustive enumeration. (The computational savings are enormous for larger versions of this

problem.) Dynamic programming starts with a small portion of the original problem and

finds the optimal solution for this smaller problem. It then gradually enlarges the prob-

lem, finding the current optimal solution from the preceding one, until the original prob-

lem is solved in its entirety.

For the stagecoach problem, we start with the smaller problem where the fortune

seeker has nearly completed his journey and has only one more stage (stagecoach run) to

go. The obvious optimal solution for this smaller problem is to go from his current state

(whatever it is) to his ultimate destination (state J). At each subsequent iteration, the prob-

lem is enlarged by increasing by 1 the number of stages left to go to complete the jour-

ney. For this enlarged problem, the optimal solution for where to go next from each pos-

sible state can be found relatively easily from the results obtained at the preceding iteration.

The details involved in implementing this approach follow.

Formulation. Let the decision variables x

(n  1, 2, 3, 4) be the immediate destina-

tion on stage n (the nth stagecoach run to be taken). Thus, the route selected is A 

 x

, where x

 J.

Let f

(s, x

) be the total cost of the best overall policy for the remaining stages, given

that the fortune seeker is in state s, ready to start stage n, and selects x

as the immedi-

ate destination. Given s and n, let x

* denote any value of x

(not necessarily unique) that

minimizes f

(s, x

), and let f

*(s) be the corresponding minimum value of f

(s, x

). Thus,

*(s)  min f

(s, x

)  f

(s, x

*),

where

(s, x

)  immediate cost (stage n)  minimum future cost (stages n  1 onward)

 c

 f

1

The value of c

is given by the preceding tables for c

by setting i  s (the current state)

and j  x

(the immediate destination). Because the ultimate destination (state J) is reached

at the end of stage 4, f

( J)  0.

The objective is to find f

(A) and the corresponding route. Dynamic programming

finds it by successively finding f

(s), f

(s), for each of the possible states s and

then using f

(s) to solve for f

(A).

Solution Procedure. When the fortune seeker has only one more stage to go (n  4),

his route thereafter is determined entirely by his current state s (either H or I) and his fi-

nal destination x

 J, so the route for this final stagecoach run is s  J. Therefore, since

(s)  f

(s, J)  c

s,J

, the immediate solution to the n  4 problem is

11.1 A PROTOTYPE EXAMPLE FOR DYNAMIC PROGRAMMING 535

n  4: sf

(s) x

H 3 J

I 4 J

Because this procedure involves moving backward stage by stage, some writers also count n backward to denote

the number of remaining stages to the destination. We use the more natural forward counting for greater simplicity.

| | | |

▲

e-Text Main Menu

Textbook Table of Contents

When the fortune seeker has two more stages to go (n  3), the solution procedure

requires a few calculations. For example, suppose that the fortune seeker is in state F.

Then, as depicted below, he must next go to either state H or I at an immediate cost of

F,H

 6 or c

F,I

 3, respectively. If he chooses state H, the minimum additional cost af-

ter he reaches there is given in the preceding table as f

(H)  3, as shown above the H

node in the diagram. Therefore, the total cost for this decision is 6  3  9. If he chooses

state I instead, the total cost is 3  4  7, which is smaller. Therefore, the optimal choice

is this latter one, x

 I, because it gives the minimum cost f

(F)  7.

536 11 DYNAMIC PROGRAMMING

Similar calculations need to be made when you start from the other two possible states

s  E and s  G with two stages to go. Try it, proceeding both graphically (Fig. 11.1)

and algebraically [combining c

and f

(s) values], to verify the following complete re-

sults for the n  3 problem.

(s, x

)  c

 f

)

n  3: sHIf

(s) x

E 48 4 H

F 97 7 I

G 67 6 H

The solution for the second-stage problem (n  2), where there are three stages to

go, is obtained in a similar fashion. In this case, f

(s, x

)  c

 f

). For example,

suppose that the fortune seeker is in state C, as depicted below.

| | | |

▲

e-Text Main Menu

Textbook Table of Contents

He must next go to state E, F, or G at an immediate cost of c

C,E

 3, c

C,F

 2, or

C,G

 4, respectively. After getting there, the minimum additional cost for stage 3 to the

end is given by the n  3 table as f

(E)  4, f

(F)  7, or f

(G)  6, respectively, as

shown above the E and F nodes and below the G node in the preceding diagram. The re-

sulting calculations for the three alternatives are summarized below.

 E: f

(C, E)  c

C,E

 f

(E)  3  4  7.

 F: f

(C, F)  c

C,F

 f

(F)  2  7  9.

 G: f

(C, G)  c

C,G

 f

(G)  4  6  10.

The minimum of these three numbers is 7, so the minimum total cost from state C to the

end is f

 E.

Making similar calculations when you start from state B or D (try it) yields the fol-

lowing results for the n  2 problem:

11.1 A PROTOTYPE EXAMPLE FOR DYNAMIC PROGRAMMING 537

(s, x

)  c

 f

)

n  2: sEFGf

(s) x

B 11 11 12 11 E or F

C 7 9 10 7 E

D 8 8 11 8 E or F

In the first and third rows of this table, note that E and F tie as the minimizing value of

, so the immediate destination from either state B or D should be x

 E or F.

Moving to the first-stage problem (n  1), with all four stages to go, we see that the

calculations are similar to those just shown for the second-stage problem (n  2), except

now there is just one possible starting state s  A, as depicted below.

These calculations are summarized next for the three alternatives for the immediate des-

tination:

 B: f

(A, B)  c

A,B

 f

(B)  2  11  13.

 C: f

(A, C)  c

A,C

 f

 D: f

(A, D)  c

A,D

 f

(D)  3  8  11.

| | | |

▲

e-Text Main Menu

Textbook Table of Contents

评论收藏

内容反馈

版权申诉

呼啸庄主

粉丝: 74
资源: 4702

Roberry_house_dynamicprogramming_源码

[人才房产]房产中介网站系统源码_house.zip源码ASP.NET网站源码打包下载

房产中介小程序 weixinmao_house 8.0.31安装更新一体包.zip微信小程序模板源码

kc_house_data.rar

house price_python预测_house_python预测_python_python课件_源码.zip

house price_python预测_house_python预测_python_python课件_源码.rar.rar

kc_house_data.csv

kc_house_data.csv.zip

房产中介小程序 weixinmao_house 8.0.31安装更新一体包.rar

[人才房产]房产中介网站系统源码_house（ASP.NET源码）.rar

房产中介小程序 weixinmao_house 8.0.77 安装更新一体包.zip微信小程序模板源码

UE4_UE5室内dviz_K_House

[人才房产]易想房产网YxHouse 2.1 (金色大气版)_changehope_house_free_v2.1_源1.zip

房产中介小程序+weixinmao_house+2.8

boston_house_prices.csv

C_To_Managed_Call_introducedii1_house_Minihousesketchup_源码

[人才房产]phpcms2007 房产模块 Beta 1_phpcms2007_house.zip源码PHP项目源代码下载

房产中介网站系统源码_house.zip

冰河的渗透实战笔记-冰河.pdf

大灰狼远控2021最新版，解压密码222

J-LINK V10 V11固件.rar

ISO21434.pdf

Web安全漏洞扫描工具-AWVS14

stm32f103 adc采样+dma传输+fft处理 频率计_fft处理_stm32_ADCFFT_频率计_ADC采样_

CTF 竞赛入门指南（ctf-all-in-one）.pdf

Web中间件常见漏洞总结.pdf

jts-1.14.zip

CobaltStrike4.4.zip

RK3568硬件设计资料.zip_C#

最新资源

stm32f103 adc采样+dma传输+fft处理频率计_fft处理_stm32_ADCFFT_频率计_ADC采样_