数学研发论坛

 找回密码
 欢迎注册
查看: 538|回复: 22

[提问] 动态规划中的一个证明问题

[复制链接]
发表于 2018-5-18 16:00:11 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
A、B两人下一个双人游戏:N个正整数的序列放在一个游戏平台上(例如4 7 2 9 5 2),两人轮流从序列的两端取数,取数后该数字被去掉并累加到本玩家的得分中,当数取尽时,游戏结束。以最终得分多者为胜。A、B均按最优策略执行,最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。A、B按顺序按最优策略的过程形成一条最优路径。显然,给定的数列若是按规律排列(如递增或递减),那么最优路径总条数仅有一条。

猜想:若数列不是按规律排列,那么最优路径总条数一定是偶数。不知能否证明?

例如数列(4 7 2 9 5 2)的四条最优路径为:
(2,5,9,2,7,4)
(2,5,9,4,7,2)
(2,4,7,5,9,2)
(2,4,7,2,9,5)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-5-19 09:42:00 | 显示全部楼层
当有n个数时,A可能的取值为2个或1个,留下n-1个数,然后B可能的取值为2个或1个,留下n-2个数,再接着A可能的取值为2个或1个…故总路径条数为1或2^k的形式。
不知这样算不算证明?

点评

5,3,2,11,8,13,6最优路径应该7条  发表于 2018-5-28 16:55
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-19 10:19:49 | 显示全部楼层
aimisiyou 发表于 2018-5-19 09:42
当有n个数时,A可能的取值为2个或1个,留下n-1个数,然后B可能的取值为2个或1个,留下n-2个数,再接着A可能 ...

题目是否可以先化简?
1,N个正整数就看作1——N,最优策略好像没有变?
2,只要有先手的最优路径就可以了?
3,先讨论先手占不到便宜的算法?

补充内容 (2018-5-20 09:17):
第1条有问题:N个正整数就看作是从1开始的连续数,最优策略好像没有变?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-5-20 09:43:36 | 显示全部楼层
王守恩 发表于 2018-5-19 10:19
题目是否可以先化简?
1,N个正整数就看作1——N,最优策略好像没有变?
2,只要有先手的最优路径就可 ...

要是递增或递减就太简单了,先手总是取大的值。

点评

我的意思是说:例如数列(4 7 2 9 5 2)就看作(2 4 1 5 3 1)  发表于 2018-5-20 09:59
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-20 14:25:10 | 显示全部楼层
如果N是偶数,先手方有非负策略。

一、先手方首先比较奇数项之和和偶数项之和,如果不相等,比如奇数项之和较大,那么先手方就首取第1项。剩下的序列首尾都是偶数项,后手方只能取到偶数项,然后又剥出一个奇数项,接着被先手方取走,剩下的首尾又都是偶数项。依此下去,先手方就能取到全部奇数项。后手方取到全部偶数项,先手方胜。
二、如果奇数项之和与偶数项之和相等,先手方可简单地依上述方法取到全部奇数项,立于不败。但先手方可以改进一下策略,还有胜机。如果先手方在前面的若干回合中取得了总和较多的数,那么剩下的偶数个数,奇数项之和与偶数项之和就不再相等,先手方可以改变奇偶取向,选择剩下的总和较多的一半从而取胜。
三、在奇数项之和与偶数项之和相等的情况下,先手方可以控制任选奇偶,后手方可以控制先手方的取数顺序,那么问题来了:是否存在一个非常数的序列,后手方可以控制不让先手方在前面的回合中取到较多的和?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-20 14:46:07 | 显示全部楼层
{1, 3, 2, 1, 3, 2}这种简单的双重序列(每个数出现2次),先手方无法取胜。所以上楼的问题答案是肯定的。或许我们应该换一种问法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-5-20 20:09:00 | 显示全部楼层
hujunhua 发表于 2018-5-20 14:25
如果N是偶数,先手方有非负策略。

一、先手方首先比较奇数项之和和偶数项之和,如果不相等,比如奇数项 ...

先手取胜时的总和和先手取的总和达到最大是一个问题么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-21 12:06:13 | 显示全部楼层
aimisiyou 发表于 2018-5-20 20:09
先手取胜时的总和和先手取的总和达到最大是一个问题么?


“A、B均按最优策略执行,最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。”

何谓“当前情况下最大可能的总分”,要看几步?如果只看一步的话,{4, 7, 2,  9, 5, 2}首取不该是4么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-5-21 12:18:37 | 显示全部楼层
hujunhua 发表于 2018-5-21 12:06
“A、B均按最优策略执行,最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。”

何谓“ ...

哦表述错误了。最优策略应该是整局下来总分达到最大。

点评

全局最优路径是动态规划方法能找到的吗?  发表于 2018-5-23 11:38
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-5-21 12:38:28 | 显示全部楼层
试了几个例子,按最优策略与按奇偶分析策略结果一致。难道两者等价?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-8-21 14:01 , Processed in 0.055674 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表