首页 > 其他分享 >决策单调性优化 DP

决策单调性优化 DP

时间:2024-10-31 17:43:19浏览次数:3  
标签:le 不等式 决策 DP 四边形 最优 优化 单调

前言

本文将介绍决策单调性优化 DP 的相关内容。持续更新修正,如有差错请指出。

1.四边形不等式优化

1.1 四边形不等式与决策单调性

  • 四边形不等式:如果对于任意的 \(a \le b \le c \le d\) 均成立

\[w(a,d) + w(b,c) \ge w(a,c) + w(b,d) \]

则称代价函数 \(w\) 满足四边形不等式。观察上述形式,即包含劣于相交,注意这是当我们要求代价函数 \(w\) 最小时四边形不等式的符号,如果我们要求 \(w\) 最大,相当于对其取相反数,那么相应的,此时的四边形不等式需要变号
四边形不等式优化利用的是状态转移方程中的决策单调性,通常用于解决一系列的最优化问题。
在解决动态规划相关问题的时候,通常会遇到以下这种形式

\[f_i = \min\limits_{j < i} \{ f_j + w(j,i)\} \]

其中 \(\min\) 也可能是 \(\max\)。一般情形下,这类问题解决的时间复杂度为 \(\mathcal{O(n^2)}\),如果 \(f\) 具有决策单调性,那么就可以将时间复杂度优化至 \(\mathcal{O(n\log n)}\) 甚至 \(\mathcal{O(n)}\)。

  • 决策单调性:设 \(p_i\) 表示 \(f_i\) 取到最小值时 \(j\) 的值(如果有多个 \(j\) 满足则取最小),即 \(f_i\) 的最优决策点。当代价函数 \(w\) 满足四边形不等式时,\(p_i\) 在 \([1,n]\) 上单调不降,\(f\) 具有决策单调性。则我们有

\[\forall i \in [1,n],j \in [0,p_i),f_{p_i} + w(p_i,i) \le f_j + w(j,i) \]

要证明这一点,可以使用反证法。假设对于 \(f_i,f_j(i < j)\),其最优决策点 \(p_j < p_i\),此时 \(p_j < p_i < i < j\),据四边形不等式有 $$w(p_j,j) + w(p_i,i) \ge w(p_j,i) + w(p_i,j)$$但是根据决策点的最优化条件又有 \(w(p_i,i) \le w(p_j,i),w(p_j,j) \le w(p_i,i)\),即 $$w(p_j,j) + w(p_i,i) \le w(p_j,i) + w(p_i,j)$$与四边形不等式矛盾。
由此得证。

对于 \(f_i\),其具有最小/最大最优决策点,将上述对 \(p_i\) 的定义更换为取最大后,关于原 \(p_i\) 的所有结论都是同样成立的,最大最优决策点同样具有单调不降的性质。注意可能存在 \(i < i'\),但是 \(i'\) 的最大最优决策点小于 \(i'\) 的最小最优决策点,故一般题目当中我们都默认只取最小(大)最优决策点来转移。

1.2 解题套路

通常我们先写出 \(f_i\) 的转移式子,大多数情况下,通常使用

\[w(j,i + 1) + w(j + 1,i) \ge w(j,i) + w(j + 1,i + 1) \]

来检验代价函数是否满足四边形不等式。

然后对于一个决策,取它作为最优决策点的 \(f_i\) 所组成的是一个区间。对于决策 \(p_i < p_{i'}\),则这两种决策能成为最优决策的区间 \([l_{p_i},r_{p_i}],[l_{p_{i'}},r_{p_{i'}}]\),有 \(r_{p_i} < l_{p_{i'}}\)。

我们写一个二分函数 \(check(j,i)\) 计算出第一个以 \(j\) 作为最优决策不如以 \(i\) 作为最优决策优秀的点,那么可以使用单调队列来维护最优决策点,并进行 DP 转移了。

标签:le,不等式,决策,DP,四边形,最优,优化,单调
From: https://www.cnblogs.com/songszh/p/18518524/juecedandiaoxingDP

相关文章

  • 线程池ThreadPoolExecutor配合callable获得线程执行结果
    此处记录使用callable创建线程,使用线程池执行,看下是否有进行线程复用并且FutureTask返回结果线程创建publicclassMyCallableBakeUserimplementsCallable<String>{privateinta;publicMyCallableBakeUser(inta){this.a=a;}@Overrid......
  • 使用ThreadPoolExecutor线程池消化线程执行代码
    此处记录一个使用ThreadPoolExecutor线程池的demo线程代码publicclassExcutorRunnableimplementsRunnable{@Overridepublicvoidrun(){System.out.println(Thread.currentThread().getName()+":线程执行666");try{Thread.......
  • 【最优化】第二次要点整理
    目录精确线搜索技术进退法确定搜索区间分割法确定极小值二分法黄金分割法插值法三点二次插值法(拉格朗日插值法)【问题】在迭代中,已知\(x^{(k)}\)和下降方向\(d^{(k)}\),如何确定下降步长\(\alpha^{(k)}\),使得\(f(x^{(k)}+\alpha^{(k)}d^{(k)})<f(x^{(k)})\)?精确线搜索技......
  • Unity性能优化-降低功耗,发热量,耗电量之OnDemandRendering篇
    公司游戏项目,手机运行严重发烫,耗电量飞快。在暂时无法做其他美术性和技术性优化的情况下,我写了这个公司内部文档,并做了个实验,今天干脆公布出来,希望对大家有用。 --官方文档:Unity-ScriptingAPI:OnDemandRendering--Youtube讲解:https://www.youtube.com/watch?v=RYgWn6jbt......
  • HarmonyOS:长列表加载性能优化
    ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤博客园地址:为敢技术(https://www.cnblogs.com/strengthen/ )➤GitHub地址:https://github.com/strengthen➤原文地址:https://www.cnblogs.com/strengthen/p/18517770➤如果链接不是为敢技术的博客园地址,则可能是......
  • 大模型训练优化方法_大模型调优
    写在前面在训练模型尤其是大模型的时候,如何加快训练速度以及优化显存利用率是一个很关键的问题。本文主要参考HF上的一篇文章:https://huggingface.co/docs/transformers/perf_train_gpu_one,以及笔者在实际训练中的一些经验,给出一些比较实用的方法。先看一个总览的表:方法......
  • TCP和UDP
    TCP(传输控制协议)连接导向:在数据传输之前,TCP需要建立连接(如三次握手),确保双方可以通信。可靠性:TCP提供数据传输的可靠性,确保数据包按顺序到达,且没有丢失。丢失的数据包会被重传。流量控制和拥塞控制:TCP具有流量控制机制,防止发送方过快发送数据,导致接收方处理不过来。同时,它也会根......
  • 低成本ASO优化提升应用商店评分
    推广一款APP时,往往会面临如何提升其评分和评价的情况。本文作者结合其实际经验,从如何减少差评和增加好评两个方向,为我们分享了如何提升评分,从而辅助产品增长。在APP推广的过程中,有很多小问题不被重视,但是对产品的转化率却有极大帮助。在一些团队里,因为没有专职做ASO的同学,运......
  • 校园社团信息管理:Spring Boot技术的应用与优化
    摘要随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施在技术上已逐步成熟。本文介绍了校园社团信息管理系统的开发全过程。通过分析校园社团信息管理系统管理的不足,创建了一个计算机管理校园社团信息管理系统的方案。文章介绍了校园社团信息管理系统的系统分......
  • 在K8S中,假设一家公司希望通过采用新技术来优化其工作负载的分配,公司该如何有效地实现
    在Kubernetes(K8s)中,一家公司若希望通过采用新技术来优化其工作负载的分配,可以遵循一系列策略和方法来实现高效的资源分配。以下是一些详细的建议:1.评估与规划资源需求评估:对公司现有的工作负载进行全面的资源需求评估,包括CPU、内存、存储和网络等资源。根据工作负载的特点,将......