【免费】8.陈瑜希《多角度思考创造性思维》1资源-CSDN文库

需积分: 0 136 浏览量 2022-08-03 23:12:13 上传评论收藏 262KB PDF 举报

资源推荐

资源详情

资源评论

CTSC’2007 国家集训队论文南京市外国语学校陈瑜希

多角度思考创造性思维

----运用树型动态规划的解题思路和方法的探析

关键字

树结构动态规划信息学奥赛

摘要

在近几年信息学竞赛中，需要运用树型动态规划解决的问题频繁出现，这些问题变化

繁多、各类思想精华渗透其中，对选手分析问题的能力和解题创造性思维有着较高的要求

因此它在竞赛中占据了重要地位。

本文将分析近几年国际比赛、全国比赛中的树型动态规划问题，重点探讨几种树型动

态规划问题的解法，并从这些问题的分析过程中，提炼出解决这类问题的思想方法——多

角度思考，创造性思维。旨在论述解决问题的思维过程，而不仅仅是解题方法。

正文

信息学竞赛中通常会出现这样的问题：给一棵树，要求以最少的代价（或取得最大收

益）完成给定的操作。有很多问题都是在树和最优性的基础上进行了扩充和加强，从而变

成了棘手的问题。

这类问题通常规模较大，枚举算法的效率无法胜任，贪心算法不能得到最优解，因此

要用动态规划解决。

和一般动态规划问题一样，这类问题的解决要考虑 3 步。

1、确立状态

几乎所以的问题都要保存以某结点为根的子树的情况，但是要根据具体问题考虑是否

要加维，加几维，如何加维。

2、状态转移

第 1 页共 15 页

CTSC’2007 国家集训队论文南京市外国语学校陈瑜希

状态转移的变化比较多，要根据具体问题具体分析，这也是本文例题分析的重点。

3、算法实现

由于树的结构，使用记忆化搜索比较容易实现。

由于模型建立在树上，即为树型动态规划。

顾名思义，树型动态规划就是在“树”的数据结构上的动态规划。

大部分动态规划题都是线性的，线性的动态规划有二种方向，既向前和向后，相应的

线性的动态规划有二种方法，既顺推与逆推。而树型动态规划是建立在树上的，也相应的

有两个方向：

1．根—>叶：既根传递有用的信息给子节点，完后根得出最优解的过程。

2．叶－>根：既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题

比较的多，应用比较广泛

当然，还有一类问题，同时需要两种遍历方向，本文的第一题就属于这类。

问题描述

Chris 家的电话铃响起了，里面传出了 Chris 的老师焦急的声音：“喂，是 Chris 的家长

吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试， Chris 的父母就心急如

焚，他们决定在尽量短的时间内找到 Chris。他们告诉 Chris 的老师：“根据以往的经验，

Chris 现在必然躲在朋友 Shermie 或 Yashiro 家里偷玩《拳皇》游戏。现在，我们就从家出发去

找 Chris，一但找到，我们立刻给您打电话。”说完砰的一声把电话挂了。

Chris 居住的城市由 N 个居住点和若干条连接居住点的双向街道组成，经过街道 x 需花

费 T

x

分钟。可以保证，任两个居住点间有且仅有一条通路。Chris 家在点 C，Shermie 和

Yashiro 分别住在点 A 和点 B。Chris

的老师和

Chris

的父母都有城市地图，但

Chris

的父母

知道点

A

、

B

、

C

的具体位置而

Chris

的老师不知

。

为了尽快找到 Chris，Chris 的父母会遵守以下两条规则：

 如果 A 距离 C 比 B 距离 C 近，那么 Chris 的父母先去 Shermie 家寻找 Chris，如果

找不到，Chris 的父母再去 Yashiro 家；反之亦然

 Chris 的父母总沿着两点间唯一的通路行走。

显然，Chris 的老师知道 Chris 的父母在寻找 Chris 的过程中会遵守以上两条规则，但由

于他并不知道 A，B，C 的具体位置，所以现在他希望你告诉他，最坏情况下 Chris 的父母

要耗费多长时间才能找到 Chris？

第 2 页共 15 页

A

Shermie

Chris

Yashiro

1

1

C

B

1

A

剩余14页未读，继续阅读

内容反馈

苗苗小姐

粉丝: 40
资源: 328

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip