找回密码
 欢迎注册
楼主: aimisiyou

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

[复制链接]
 楼主| 发表于 2018-5-23 20:33:07 | 显示全部楼层
hujunhua 发表于 2018-5-21 12:06
“A、B均按最优策略执行,最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。”

何谓“ ...


用动态规划推导如下:
A[i,j]:表示从 ij 项,轮取方可取到的最大和值(i<j);
sum[i,j]:表示从 i j 项的和值;
即有A[i,j]=max{ai+(sum[i+1,j]-A[i+1,j]),aj+(sum[i,j-1]-A[i,j-1])}
             =max{sum[i,j]-A[i+1,j],sum[i,j]-A[i,j-1]}
             =sum[i,j]-min{A[i+1,j],A[i,j-1]}
1.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-5-23 22:31:02 | 显示全部楼层
(defun fmax (lst)
         (defun f(lst)
               (setq i 1)
              (mapcar '(lambda (x) (if (minusp (setq i (* i -1)) ) x  0 )) lst)
          )
          (if  (= 0 (rem (length lst) 2))
               (setq va (max
                             (apply '+ (f lst))  
                             (apply '+ (f (cdr lst)))
                         )
                )
               (setq va (max
                               (+ (car lst) (min (apply '+ (f (cdr lst)))  (apply '+ (f (cddr lst)))))
                               (+ (last lst) (min (apply '+ (f (cdr (reverse lst))))  (apply '+ (f (cddr (reverse lst))))))
                         )
                )
           )
)
_$ (fmax '(5 9 2 11 8 13 6))
21
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-27 11:02:50 | 显示全部楼层
取牌游戏.PNG
程序简单,只能得到和,不能得到路径。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-5-28 11:04:57 | 显示全部楼层
如何证明,当数列项数为偶数时,双方都按最终和值最大策略,先手想取得最大和值必是全取偶数项或全取奇数项?

点评

显然不对,比如8,4,1,2先手会取走8,2两数  发表于 2018-5-28 11:39
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-30 10:26:49 | 显示全部楼层
aimisiyou 发表于 2018-5-28 11:04
如何证明,当数列项数为偶数时,双方都按最终和值最大策略,先手想取得最大和值必是全取偶数项或全取奇数项 ...


不是全取偶数项或者全取奇数项,而是每次都取剩下的偶数个数中,奇数和与偶数和较大的一方。检查这个策略是否与动态规划的结果相一致。

我估计即使这样,也存在不一致的例子。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-30 11:15:14 | 显示全部楼层
5,1,2,11,2,1
偶数项和更大,但是第一步最优策略是选择奇数项的5,使得先手可以取走17
如果先选择偶数项的1,先手只能取走13
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-6-6 12:50:34 | 显示全部楼层
本帖最后由 aimisiyou 于 2018-6-6 14:33 编辑

A[i,j]=max{ai+(sum[i+1,j]-A[i+1,j]),aj+(sum[i,j-1]-A[i,j-1])}
        =max{sum[i,j]-A[i+1,j],sum[i,j]-A[i,j-1]}
        =sum[i,j]-min{A[i+1,j],A[i,j-1]}
由此,每算一个A[i,j]就要算一次sum[i,j],加法运算次数太多(尤其是当i远远小于j时),而且局部加法很多是重复的,严重影响效率,考虑优化。

从图中可以看出(定义从上往下依次为第一层、第二层……;显然,从第二层开始,每个节点上层有两个子节点),从第三层开始,节点A[i,j]的值=该节点的较小子节点的较小子节点的值+对应值(若该节点的子节点在左边,对应值为第一层第j个数;若该节点的子节点在右边,对应值为第一层第i个数;),这样通过先查找再做一次加法运算来替换sum大量求和运算,显然大大提高了程序运行效率。
(defun f (lst)
  (setq i -1)
  (setq lst1 (mapcar '(lambda (x y)   
                         (progn
                            (setq i (+ i 1))
                            (list (if (<= x y) 0 1)
                                  (min x y)
                                  (max x y)   
                                  (if (< i 1) nil (nth (- i 1) lst))
                                  (nth (+ i 2) lst)
                            )
                         )        
                      )
                      (reverse (cdr (reverse lst)))
                      (cdr lst)
               )
   )
   (while (cdr lst1)
         (setq lst1 (mapcar '(lambda (x y)   
                               (list (setq j (if (<= (caddr x) (caddr y)) 0 1))   
                                     (min (caddr x) (caddr y))  
                                     (if (= j 0) (+ (cadr x) (last x))  (+ (cadr y) (cadddr y)))
                                     (cadddr x)
                                     (last y)
                                )
                              )        
                           (reverse (cdr (reverse lst1)))
                           (cdr lst1)
                      )
            )
   )
(caddr (car lst1))
)

_$ (f '(2 7 5 4 9 1 8 15 3 9 5 2 11 7 4 6))
53
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-7 13:50:47 | 显示全部楼层
最近学python,来个:
  1. def aplay(l):
  2. k,m,n=l,len(l)-1,0
  3. while n<m:k,n=[max(l2-k1,l1-k2) for l1,l2,k1,k2 in zip(l[:-n-1],l[n+1:],k[:-1],k[1:])],n+1
  4. print((k[0]+sum(l))/2)
  5. aplay([5,9,2,11,8,13,6])
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-6-13 21:24:59 | 显示全部楼层
本帖最后由 aimisiyou 于 2018-6-13 21:39 编辑
aimisiyou 发表于 2018-5-21 12:18
哦表述错误了。最优策略应该是整局下来总分达到最大。

;;获取所有最优策略取法
(defun f (lst)
  (setq i -1)
  (setq lst1 (mapcar '(lambda (x y)   
                         (progn
                            (setq i (+ i 1))
                            (list (if (< x y) -1 (if (= x y) 0 1))
                                  (min x y)
                                  (max x y)   
                                  (if (< i 1) nil (nth (- i 1) lst))
                                  (nth (+ i 2) lst)
                                  (list
                                         (list
                                               (max x y)
                                               (min x y)
                                          )
                                   )
                            )
                         )        
                      )
                      (reverse (cdr (reverse lst)))
                      (cdr lst)
               )
   )
  (while (cdr lst1)
       (setq lst1 (mapcar '(lambda (x y)   
                              (list (setq j (if (< (caddr x) (caddr y)) -1 (if (= (caddr x) (caddr y)) 0 1)))   
                                    (min (caddr x) (caddr y))  
                                    (if (<= j 0) (+ (cadr x) (cadddr (cdr x)))  (+ (cadr y) (cadddr y)))
                                    (cadddr x)
                                    (cadddr (cdr y))
                                    (if (= j -1)
                                         (mapcar '(lambda (z) (cons (cadddr (cdr x)) z)) (last x) )
                                         (if (= j 1)
                                             (mapcar '(lambda (z) (cons (cadddr y) z)) (last y) )
                                             (append
                                                       (mapcar '(lambda (z) (cons (cadddr (cdr x)) z)) (last x) )
                                                       (mapcar '(lambda (z) (cons (cadddr y) z)) (last y) )
                                              )
                                         )
                                    )
                                )
                              )        
                           (reverse (cdr (reverse lst1)))
                           (cdr lst1)
                      )
            )
   )
  (last  (car lst1))
)


(f '(5 9 2 11 8))
((8 11 2 9 5) (8 11 5 9 2) (5 9 8 11 2) (5 9 2 11 8))

(f '(5 9 2 11 8 13 6))
((6 13 8 11 2 9 5) (6 13 8 11 5 9 2) (6 13 5 9 8 11 2) (6 13 5 9 2 11 8) (5 9 6 13 8 11 2) (5 9 6 13 2 11 8) (5 9 2 11 6 13 8) (5 9 2 11 8 13 6))

(f '(5 3 2 11 8 13 6))
((6 13 8 11 5 3 2) (6 13 5 3 8 11 2) (6 13 5 3 2 11 8) (5 3 6 13 8 11 2) (5 3 6 13 2 11 8) (5 3 2 11 6 13 8) (5 3 2 11 8 13 6))

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 14:21 , Processed in 0.052576 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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