当前位置: 首页 > news >正文

算法导论【在线算法】—The Ski-Rental Problem、The Lost Cow Problem、The Secretary Problem

算法导论【在线算法】

  • The Ski-Rental Problem
    • 问题描述
    • 在线算法
    • 证明
  • The Lost Cow Problem
    • 问题描述
    • 在线算法
    • 类似问题—寻宝藏
  • The Secretary Problem
    • 问题描述
    • 在线算法
    • The Best Possible k

The Ski-Rental Problem

问题描述

  • 假设你正在上滑雪课。每节课结束后,你决定(取决于你喜欢的程度、你的骨骼状况和天气)是继续滑雪还是完全停止滑雪。
  • 你可以选择以1美元一次的价格租用滑雪板,也可以以B美元的价格购买滑雪板。
  • 你是买还是租?
  • 如果你事先知道你一生中会滑雪多少次,那么选择租还是买就很简单了。
  • 如果你要滑雪超过BBB次,那就在开始前购买,否则就一直租。该算法的代价为min(T,B)min(T,B)min(T,B)
  • 这种对未来了如指掌的策略被称为离线策略。

在线算法

  • 实际上,你不知道你会滑雪多少次。你该怎么办?
  • 在线策略是:取一个数字k,这样在租用k−1次后,您将购买滑雪板(就在第k次滑雪之前)。
  • 如果我们取k=Bk=Bk=B,那么可以保证我们支付不会超过离线策略成本两倍的费用
  • 例如:假设B=7美元,那么,在6次租金之后,你就买了。总付款:6+7=13$

证明

最坏情况下,k=Bk=Bk=B,我们选择在滑雪次数T=k−1T=k-1T=k1次后再也不滑雪,那么在线算法的总费用为B−1+B=2B−1B-1+B=2B-1B1+B=2B1,而离线算法取得的最优解为min(T,B)=Bmin(T,B)=Bmin(T,B)=B,此时竞争比为2B−1B=2−1B\cfrac{2B-1}{B}=2-\cfrac{1}{B}B2B1=2B1,则我们说这个策略是(2−1B)(2-\cfrac{1}{B})(2B1)竞争的
在这里插入图片描述

The Lost Cow Problem

问题描述

  • Old McDonald失去了他最喜欢的奶牛。最后一次看到它朝着通向两条无限道路的路口行进。没有一位目击者能说出奶牛是选择了左边还是右边的路线。
  • 在这里插入图片描述

在线算法

  • 在线算法是9-competitive的,换句话说:在找到奶牛之前可能经过的距离最多是最佳离线算法(知道奶牛在哪里)距离的9倍
  • 最坏的情况是,他发现奶牛的距离比他上次在这一侧搜索的距离稍远
  • 因此,OPT=2j+εOPT=2j+εOPT=2j+ε,其中j=j=j=迭代次数,εεε是某个小距离。然后
  • 在这里插入图片描述
  • 伪代码如下:

在这里插入图片描述

类似问题—寻宝藏

在这里插入图片描述
在这里插入图片描述

mmm条路编号为1,2,3...m1,2,3...m1,2,3...m,从第一条路开始寻找,初始寻找距离为d=1d=1d=1,如果在这个距离内找到了宝藏则结束寻找,没找到则寻找距离翻倍,切换至寻找下一条路径,路径编号对mmm取模,保证每次寻找的路径都是合法的,直到找到宝藏。

Treasure(m)
d = 1;current side = 1
while true doWalk distance d on current sideif find treasure thenexitelsed = 2dcurrent side = (current side+1)%mreturn to starting point

该算法的竞争比为O(m)O(m)O(m)

证明:

​ 最坏的情况是,发现宝藏的距离比上次在这条路上搜索的距离稍远一点点,因此,最优解为OPT:2j+εOPT:2^j +εOPT2j+ε,其中jjj=迭代次数,εεε是某个小距离。则:

CostOPT=2j+ε>2jCostON=m(1+2+4+...+2j+1)+2j+ε=m⋅2j+2+2j+ε=(4m+1)⋅2j+ε<(4m+1)⋅CostOPT\begin{aligned} Cost OPT &= 2^j +ε>2^j\\ \ \ \ \ \ \ Cost ON&= m(1+2+4+...+2^{j+1})+2^j +ε\\ &= m · 2^{j+2} +2^j +ε = (4m+1)· 2^j +ε < (4m+1) · Cost OPT \end{aligned} CostOPT      CostON=2j+ε>2j=m(1+2+4+...+2j+1)+2j+ε=m2j+2+2j+ε=(4m+1)2j+ε<(4m+1)CostOPT

所以竞争比为O(4m+1)=O(m)O(4m+1)=O(m)O(4m+1)=O(m)

The Secretary Problem

问题描述

  • 我们有n位候选人(可能是求职者或可能的婚姻伴侣)。
  • 我们的目标是选择最好的候选人。
  • 假设候选人可以从最好到最坏完全排序,没有任何联系。
  • 候选人以随机顺序依次到达。
  • 我们只能在候选人到达时确定他们的相对排名。
  • 我们不能观察绝对等级。
  • 每次面试后,我们必须立即接受或拒绝申请人。
  • 候选人一旦被拒绝,就不能被召回。
  • 一旦候选人被录取,我们就停止面试。

在线算法

  • 已知候选人数n
  • 在线策略在遇到第i位候选人后,我们能够给出分数score(i)
  • 选择一个正整数k<n,面试并拒绝前k位候选人。
  • 继续面试剩下的n-k位,并接受第一位得分高于前k位候选人的候选人。
  • 如果最高分在第一批面试的k人里,那么我们必须接受第n位即最后一位申请人
  • 伪代码:在这里插入图片描述

The Best Possible k

结论:如果我们在k=nek=\cfrac{n}{e}k=en的情况下实施我们的策略,我们将以至少1e\cfrac{1}{e}e1的概率成功雇佣我们最合格的申请人

相关文章:

算法导论【在线算法】—The Ski-Rental Problem、The Lost Cow Problem、The Secretary Problem

算法导论【在线算法】The Ski-Rental Problem问题描述在线算法证明The Lost Cow Problem问题描述在线算法类似问题—寻宝藏The Secretary Problem问题描述在线算法The Best Possible kThe Ski-Rental Problem 问题描述 假设你正在上滑雪课。每节课结束后&#xff0c;你决定&a…...

linux 下怎样给pdf 文件加书签

linux 下怎样给pdf 文件加书签 对于没有书签的pdf文件,怎样给pdf加标签呢? 以方便阅读. 以前总是要借助windows下pdf 工具, 叫什么来者? 忘了 记得是编辑一个用tab表示目录级别的文本文件, 有一种直观的感觉,大目录下嵌套着小目录 ..., 然后导入到文件中 linux 下有没有这种…...

[软件工程导论(第六版)]第2章 可行性研究(课后习题详解)

文章目录1. 在软件开发的早期阶段为什么要进行可行性研究&#xff1f;应该从哪些方面研究目标系统的可行性&#xff1f;2. 为方便储户&#xff0c;某银行拟开发计算机储蓄系统。储户填写的存款单或取款单由业务员输入系统&#xff0c;如果是存款&#xff0c;系统记录存款人姓名…...

[软件工程导论(第六版)]第3章 需求分析(课后习题详解)

文章目录1. 为什么要进行需求分析&#xff1f;通常对软件系统有哪些需求&#xff1f;2. 怎样与用户有效地沟通以获取用户的真实需求&#xff1f;3. 银行计算机储蓄系统的工作过程大致如下&#xff1a;储户填写的存款单或取款单由业务员输入系统&#xff0c;如果是存款则系统记录…...

基于分布鲁棒联合机会约束的能源和储备调度(Matlab代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客 &#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜…...

ETL和数据建模

一、什么是ETL ETL是数据抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;、加载&#xff08;Load &#xff09;的简写&#xff0c;它是将OLTP系统中的数据经过抽取&#xff0c;并将不同数据源的数据进行转换、整合&#xff0c;得出一致性的数据&…...

ccc-pytorch-回归问题(1)

文章目录1.简单回归实战&#xff1a;2.手写数据识别1.简单回归实战&#xff1a; 用 线性回归拟合二维平面中的100个点 公式&#xff1a;ywxbywxbywxb 损失函数&#xff1a;∑(yreally−y)2\sum(y_{really}-y)^2∑(yreally​−y)2 迭代方法&#xff1a;梯度下降法&#xff0c;…...

【JAVA八股文】框架相关

框架相关1. Spring refresh 流程2. Spring bean 生命周期3. Spring bean 循环依赖解决 set 循环依赖的原理4. Spring 事务失效5. Spring MVC 执行流程6. Spring 注解7. SpringBoot 自动配置原理8. Spring 中的设计模式1. Spring refresh 流程 Spring refresh 概述 refresh 是…...

二叉树的相关列题!!

对于二叉树&#xff0c;很难&#xff0c;很难&#xff01;笔者也是感觉很难&#xff01;虽然能听懂课程&#xff0c;但是&#xff0c;对于大部分的练习题并不能做出来&#xff01;所以感觉很尴尬&#xff01;&#xff01;因此&#xff0c;笔者经过先前的那篇博客&#xff0c;已…...

Java设计模式 - 原型模式

简介 原型模式&#xff08;Prototype Pattern&#xff09;是用于创建重复的对象&#xff0c;同时又能保证性能。这种类型的设计模式属于创建型模式&#xff0c;它提供了一种创建对象的最佳方式。 这种模式是实现了一个原型接口&#xff0c;该接口用于创建当前对象的克隆。当直…...

深度学习中的 “Hello World“

Here’s an interesting fact—Each month, there are 186.000 Google searches for the keyword “deep learning.” 大家好✨,这里是bio🦖。每月有超18万的人使用谷歌搜索深度学习这一关键词,是什么让人们对深度学习如此感兴趣?接下来请跟随我来揭开深度学习的神秘面纱。…...

购买WMS系统前,有搞清楚与ERP仓库模块的区别吗

经常有朋友在后台询问我们关于WMS系统的问题&#xff0c;他们自己也有ERP系统&#xff0c;但是总觉得好像还差了点什么&#xff0c;不知道是什么。今天&#xff0c;我想通过本文&#xff0c;来向您简要地阐述ERP与WMS系统在仓储管理上的不同之处。 ERP仓库是以财务为导向的&…...

一文吃透 Spring 中的IOC和DI

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

分布式任务处理:XXL-JOB分布式任务调度框架

文章目录1.业务场景与任务调度2.任务调度的基本实现2.1 多线程方式实现2.2 Timer方式实现2.3 ScheduledExecutor方式实现2.4 第三方Quartz方式实现3.分布式任务调度4.XXL-JOB介绍5.搭建XXL-JOB —— 调度中心5.1 下载与查看XXL-JOB5.2 创建数据库表5.3 修改默认的配置信息5.4 启…...

【源码解析】Ribbon和Feign实现不同服务不同的配置

Ribbon服务实现不同服务&#xff0c;不同配置是通过RibbonClient和RibbonClients两个注解来实现的。RibbonClient注册的某个Client配置类。RibbonClients注册的全局默认配置类。 Feign实现不同服务&#xff0c;不同配置&#xff0c;是根据FeignClient来获取自定义的配置。 示…...

【webpack5】一些常见优化配置及原理介绍(二)

这里写目录标题介绍sourcemap定位报错热模块替换&#xff08;或热替换&#xff0c;HMR&#xff09;oneOf精准解析指定或排除编译开启缓存多进程打包移除未引用代码配置babel&#xff0c;减小代码体积代码分割&#xff08;Code Split&#xff09;介绍预获取/预加载(prefetch/pre…...

力扣sql简单篇练习(十九)

力扣sql简单篇练习(十九) 1 查询结果的质量和占比 1.1 题目内容 1.1.1 基本题目信息 1.1.2 示例输入输出 1.2 示例sql语句 # 用count是不会统计为null的数据的 SELECT query_name,ROUND(AVG(rating/position),2) quality,ROUND(count(IF(rating<3,rating,null))/count(r…...

线段树c++

前言 在谈论到种种算法知识与数据结构的时候,线段树无疑总是与“简单”和“平常”联系起来的。而这些特征意味着,线段树作为一种常用的数据结构,有常用性,基础性和易用性等诸多特点。因此,今天我来讲一讲关于线段树的话题。 定义 首先,线段树是一棵“树”,而且是一棵…...

HTML+CSS+JavaScript学习笔记~ 从入门到精通!

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录前言一、HTML1. 什么是HTML&#xff1f;一个完整的页面&#xff1a;<!DOCTYPE> 声明中文编码2.HTML基础①标签头部元素标题段落注释水平线文本格式化②属性3.H…...

LeetCode 430. 扁平化多级双向链表

原题链接 难度&#xff1a;middle\color{orange}{middle}middle 题目描述 你会得到一个双链表&#xff0c;其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表&#xff0c;也包含这些特殊的节点。这些子列表可以有一…...

2.5|iot|第1章嵌入式系统概论|操作系统概述|嵌入式操作系统

目录 第1章&#xff1a; 嵌入式系统概论 1.嵌入式系统发展史 2.嵌入式系统定义* 3.嵌入式系统特点* 4.嵌入式处理器的特点 5.嵌入式处理分类 6.嵌入式系统的应用领域及嵌入式系统的发展趋势 第8章&#xff1a;Linux内核配置 1.内核概述 2.内核代码结构 第1章&#xf…...

一文教会你使用ChatGPT画图

引言 当今,ChatGPT在各行各业都有着广泛的应用,其自然语言处理技术也日益成熟。ChatGPT是一种被广泛使用的技术,除了能够生成文本,ChatGPT还可以用于绘图,这为绘图技术的学习和应用带来了新的可能性。本文将介绍如何利用ChatGPT轻松绘制各种形状,为对绘图技术感兴趣的读…...

Java资料分享

随着Java开发的薪资越来越高&#xff0c;越来越多人开始学习 Java 。在众多编程语言中&#xff0c;Java学习难度还是偏高的&#xff0c;逻辑性也比较强&#xff0c;但是为什么还有那么多人要学Java呢&#xff1f;Java语言是目前流行的互联网等企业的开发语言&#xff0c;是市面…...

yum/vim工具的使用

yum 我们生活在互联网发达的时代&#xff0c;手机电脑也成为了我们生活的必须品&#xff0c;在你的脑海中是否有着这样的记忆碎片&#xff0c;在一个明媚的早上你下定决心准备发奋学习&#xff0c;“卸载”了你手机上的所有娱乐软件&#xff0c;一心向学&#xff01;可是到了下…...

内网渗透(三十九)之横向移动篇-pass the ticket 票据传递攻击(PTT)横向攻击

系列文章第一章节之基础知识篇 内网渗透(一)之基础知识-内网渗透介绍和概述 内网渗透(二)之基础知识-工作组介绍 内网渗透(三)之基础知识-域环境的介绍和优点 内网渗透(四)之基础知识-搭建域环境 内网渗透(五)之基础知识-Active Directory活动目录介绍和使用 内网渗透(六)之基…...

Unity性能优化之纹理格式终极篇

知识早班车&#xff1a;1、当n大于1时&#xff0c;2的n次幂一定能被4整除&#xff1b;证明&#xff1a;2^n 2^2*2^(n-1) 4*2^(n-1)2、4的倍数不一定都是2的次幂&#xff1b;证明&#xff1a;4*3 12&#xff1b;12不是2的次幂3、Pixel&#xff08;像素&#xff09;是组成图片…...

【Spark分布式内存计算框架——Spark SQL】9. Dataset(下)RDD、DF与DS转换与面试题

5.3 RDD、DF与DS转换 实际项目开发中&#xff0c;常常需要对RDD、DataFrame及Dataset之间相互转换&#xff0c;其中要点就是Schema约束结构信息。 1&#xff09;、RDD转换DataFrame或者Dataset 转换DataFrame时&#xff0c;定义Schema信息&#xff0c;两种方式转换为Dataset时…...

Windows 环境下,cmake工程导入OpenCV库

目录 1、下载 OpenCV 库 2、配置环境变量 3、CmakeLists.txt 配置 1、下载 OpenCV 库 OpenCV官方下载地址&#xff1a;download | OpenCV 4.6.0 下载完毕后解压&#xff0c;便可以得到下面的文件 2、配置环境变量 我们需要添加两个环境变量&#xff0c;一个是 OpenCVConfi…...

微服务架构设计模式-(16)重构

绞杀者应用程序 由微服务组成的应用程序&#xff0c;将新功能作为服务&#xff0c;并逐步从单体应用中提取服务来实现。好处 尽早并频繁的体现价值 快速开发交付&#xff0c;使用 与之相对的是“一步到位”重构&#xff0c;这时间长&#xff0c;且期间有新的功能加入&#xff…...

数据结构:归并排序和堆排序

归并排序 归并排序(merge sort)是利用“归并”操作的一种排序方法。从有序表的讨论中得知,将两个有序表“归并”为一个有序表,无论是顺序表还是链表,归并操作都可以在线性时间复杂度内实现。归并排序的基本操作是将两个位置相邻的有序记录子序列R[i…m]R[m1…n]归并为一个有序…...

怎么进入网站后台图片/重庆百度seo整站优化

数据库领域公认的标准结构是三级模式结构&#xff0c;它包括外模式、模式和内模式&#xff0c;有效地组织、管理数据&#xff0c;提高了数据库的逻辑独立性和物理独立性。用户级对应外模式&#xff0c;概念级对应模式&#xff0c;物理级对应内模式&#xff0c;使不同级别的用户…...

合肥网站开发建设/产品推广方案要包含哪些内容

面试准备 不论是校招还是社招都避免不了各种面试、笔试&#xff0c;如何去准备这些东西就显得格外重要。 运筹帷幄之后&#xff0c;决胜千里之外&#xff01;不打毫无准备的仗&#xff0c;我觉得大家可以先从下面几个方面来准备面试&#xff1a; 1. 自我介绍。&#xff08;介…...

一起做网店网站入驻收费/搜索seo优化

HTTP和MQTT协议实践一、REST协议实现1. 读取指定城市的天气预报信息2. 给指定手机号码发送验证码二、MQTT协议实现1. MQTT协议处于哪一层2. 自定义天气预报消息主题三、总结与参考资料一、REST协议实现 任务要求一 安装Java开发环境和Java IDE编程工具 Eclipse 或 IDEA&#xf…...

西安做网站选哪家公司/建站平台在线提交功能

本文实例讲述了python之wxPython的使用方法&#xff0c;分享给大家供大家参考。具体方法如下&#xff1a; 先来看看效果&#xff0c;这里加载一张图片&#xff1a;代码如下&#xff1a; #!/usr/bin/env python """hello wxPython program""" imp…...

双线主机可以做彩票网站吗/网站优化包括对什么优化

64位windows安装storm前需要先搞定zookeeper和python&#xff0c;所以下面我们3步走&#xff1a; 一、zookeeper 1、上https://zookeeper.apache.org/点击下方download到新页面&#xff0c;还得点一次中间的download&#xff0c;再选一个镜像链接http://mirrors.tuna.tsinghua.…...

手机导航网站模板/360搜索引擎首页

aapt即Android Asset Packaging Tool&#xff0c;在SDK的build-tools目录下。 该工具可以查看&#xff0c;创建&#xff0c; 更新ZIP格式的文档附件(zip, jar, apk)。 也可将资源文件编译成二进制文件&#xff0c;尽管你可能没有直接使用过aapt工具&#xff0c;但是build scr…...