Blog

人工能力智能(ACI)

Content #

“人工能力智能”,即人工智能可以在最低程度的监督下完成复杂的目标和任务。

人工智能和通用人工智能这些词我们常能听到,但我们还需要一个概念来描述它们之间的一个中间阶段。在这个阶段,现代图灵测试已经成功,但系统还没展现出那种失控的“超级智能”。人工能力智能就是这个阶段的简称。

人工能力智能代表着人工智能发展的下一个重要阶段。

在这一阶段,人工智能系统不仅可以识别和生成与特定语境相契合的新颖的图像、音频和语言,还能实时与真实用户进行交互。它凭借增强的记忆能力,能在较长时间内维持这些能力的一致性,并能够利用其他数据来源,如第三方的知识、产品或供应链组件数据库等。这样的系统能利用这些资源,把多个行动安排整合成长期的计划和方案,以追求更为复杂和开放的目标,比如设立并运营一个亚马逊市场商店。所有这一切都将极大地扩展人工智能工具的使用,提升其执行一系列广泛的复杂实用任务的能力。这便是真正具备能力的人工智能。

From #

book:浪潮将至

Content #

人工智能(AI)、通用人工智能(AGI)与人工能力智能(ACI) #

人工智能是引导机器学习类人能力的科学。通用人工智能是人工智能发展的高级阶段,那时人工智能系统将能够使用所有的人类认知技能,且其表现将超越最聪明的人。人工能力智能是人工智能通向通用人工智能的重要中间节点,这一节点正迅速向我们逼近;人工能力智能将广泛应对各种复杂的任务,但距离完全通用的智能水平仍有很长的路要走。

第一部分 技术人 #

技术的扩散过程是由需求增加和成本降低这两大力量共同催化的。两者都使得技术不断变得更好、更便宜。科学与技术之间的长期复杂互动孕育出新知识、新突破和新工具,它们不断发展、强化,重新组合、融合,释放出巨大的生产力,驱动未来的发展。随着更多技术的普及和成本的降低,新的、更便宜的下游技术也应运而生。例如,优步的商业模式离不开智能手机,而智能手机的功能依赖于GPS(全球定位系统),GPS离不开卫星,卫星靠火箭实现,火箭离不开燃烧技术,而燃烧技术的实现可以追溯到语言和火。

第二部分 下一场浪潮 #

目前而言,重要的是系统能够做什么,而不是它是否具有自我意识、理解能力或类人智能。关注到这一点,我们才能真正看清我们所面临的挑战:每一天,系统的能力都在不断增强,能做的事情也越来越多。

从某种意义上说,全球GDP(国内生产总值)的很大一部分都是通过基于屏幕的人工智能界面来实现的。目前的主要挑战在于如何推进人工智能开发者所称的“分层规划”,即将多个目标、子目标和能力整合到一个无缝的流程中,服务于一个单一的目标。一旦分层规划得以实现,人工智能的能力将进一步获得显著提升,它将能够被嵌入一个企业或组织及其所有的历史数据和实际需求中,从而能够执行诸如游说、销售、制造、招聘、计划等任务。简言之,公司能做的所有事情,人工智能都能胜任,只需一小队人类管理者来负责监督、复核、实施,并与人工智能共同担任CEO。

人工能力智能(ACI)

生命技术 #

卡尔森曲线

机器人挽救了局面

即将到来的技术浪潮的4个特征 #

  1. 首要特征,便是技术的高度非对称性影响。

你不必力量相当、规模相当地进行对抗,新技术会使得那些看似强大的势力暴露出以前难以想象到的弱点和破绽。

  1. 这些技术发展迅猛,呈现出一种超级进化性

它们以惊人的速度迭代、改进,并不断拓展至新的领域。

  1. 它们往往具有通用性,能够服务于多种不同的目的。
  2. 与任何以往的技术相比,它们越来越展现出一定程度的自主性。

人工智能带来的非对称性风险

第八章 势不可当的驱动力 #

  1. 大国竞争与我们和AlphaGo的那段经历有关。事实上,技术领域的较量一直以来都是地缘政治的常态。各国都深刻认识到,跟上其他国家的步伐至关重要,技术创新意味着权力。
  2. 现有的全球研究生态系统。该系统大力推崇公开出版,鼓励人们释放好奇心,并倡导人们不遗余力地追求新思想。
  3. 技术所带来的巨大经济利益,以及对解决全球性社会挑战的迫切需求。
  4. 还有一种不可忽视的驱动力——个体的自我追求。

第三部分 国家的失败 #

国家不仅要确保这种集权能促进和平与繁荣,还要确保它能通过一系列制衡和再分配手段及制度规范得到有效遏制。为实现此目标,国家必须在两种极端之间达到微妙的平衡。一方面,我们必须预防极端集权可能导致的反乌托邦式局面;另一方面,我们也必须接受国家权力的持续干预以维护社会秩序。我们常理所当然地认为这种平衡很容易实现,但实际并非如此。

考虑到社会流动性降低、不平等加剧以及政治暴力事件频发,以及这些现象之间持续存在的相互关联,上述趋势就更加令人感到担忧。100多个国家的数据显示,一个国家的社会流动性越低,就越容易出现诸如骚乱、罢工、暗杀、革命运动和内战等动荡事件。当感觉自己陷入困境,同时目睹他人占据所有回报时,人们便会产生愤怒。

第十章 脆弱性放大器 #

NHS(英国国家医疗服务体系)突然全面停顿事件

历史上,技术进步总是在攻防之间进行着一种精妙的博弈。尽管攻防之间的平衡时有波动,但总体而言维系着相对的均势:每当有新型炮弹或网络武器问世,总会迅速涌现出有效的反制手段。火炮既能摧毁城墙,也能击溃敌军。如今,强大、不对称且通用的技术终将落入那些意图破坏国家稳定的人手中。尽管防御能力随时间不断增强,但是这些技术的本质趋向于强化攻势:它们传播广泛、速度迅猛、接入简易。一台普通的笔记本电脑就足以存储能够改变世界的算法;很快,这些技术将不再依赖上一波技术浪潮和互联网所倚重的那种庞大、集中的基础设施了。区别于箭矢乃至高超声速导弹,人工智能和生物制剂将以前所未有的低成本、高效率、自主性迅猛发展。因此,除非采取重大干预措施重塑当前局势,否则在未来数年,掌握这些技术的人数将达到数百万。

第十一章 国家的未来 #

三星集团的收入占韩国经济的20%。对如今的韩国人来说,三星几乎就是一个并行的政府,影响着人们的日常生活。然而,由于错综复杂的利益关系以及不断出现的企业和政府丑闻,韩国与三星集团之间的权力平衡既脆弱又模糊。或许有人认为三星和韩国的发展轨迹是个特例,但在未来,这样的“特例”有望成为常态。鉴于技术能力的广泛聚集趋势,新一代企业有望承接一系列原本由政府提供的服务,例如教育、国防,甚至可能包括货币和执法等领域。以eBay和PayPal的争议解决系统为例,该系统目前每年处理约6 000万起争议,处理量是美国整个法律体系的3倍,其中90%的争议是仅通过技术手段得到解决的。未来将有更多类似的转变。

从某种意义上说,科技已经催生了一种新型的现代“帝国”。即将到来的技术浪潮将让这一趋势提速,为那些创造和控制技术的人带来极大的权力和财富。在政府资源日益紧张的背景下,新的私人利益团体将填补政府服务的空缺。

真主党到底是什么性质呢?它是一个国家还是非国家组织?是极端组织还是盘踞一方的传统势力?事实上,它是一个在国家机构内外都有影响力的奇特“混合体”。它既有国家的特征,又不完全是一个国家,它能够根据自身利益选择性承担某些责任和开展某些活动,这往往给整个国家和更广泛的地区带来可怕的后果。像真主党这样的组织并不多见,它是在地区特有的紧张局势中发展起来的。然而,即将到来的技术浪潮有可能会推动更多类似的、有国家特征的小型实体出现。与权力的集中化趋势相反,这实际上可能引发一种“真主党化”现象,使得世界进一步分裂和部落化。在这个世界里,每个人都能够获取最新的技术,可以选择自己的生活方式,也更有机会在不需要庞大民族国家组织支持的情况下,维持自己的生活水平。

简言之,随着即将到来的技术浪潮广泛释放新的能力,那些目前依赖规模和集中化的现代社会和社会组织的关键部分,可能会面临深刻变革,失去其原有权力优势。现实权力的重新分配,将使得各种社群能够按照自身意愿生活。

From #

《浪潮将至》 [英]穆斯塔法·苏莱曼 [英]迈克尔·巴斯卡尔

book:金融思维

Content #

经济金融化:不可逆转的趋势

◆ 什么是经济金融化经济金融化就是在一个国家的经济活动,无论是政府、企业,还是家庭与个人的经济活动中,金融变得越来越重要,人们的日常生活也越来越依赖于金融。

◆ 金融化:越来越多的财富通过金融渠道创造出来

◆ 在中国,经济金融化具体体现在以下几个方面。第一,金融业增加值占GDP(国内生产总值)的比重大幅度上升。

◆ 中国金融业高速增长的结果就是金融业增加值占GDP的比重从1978年的2.1%上升到了2017年的7.97%。2017年,中国金融业增加值占GDP的比重已经超过美国。

◆ 第二,A股上市公司的净利润总额中,绝大部分来自金融业的上市公司。

◆ 第三,大量制造业企业不专心做主业,而去从事金融活动。

◆ 第四,金融业平均工资水平远远超过全国平均工资水平。

◆ 第五,金融业从业人口迅速增长。

◆ 第六,财产性收入成为收入分配的重点。财产性收入是与工资性收入相对而言的,财产性收入就是利用财产产生的收入,包括利息、股利、房租、股价上涨产生的资本增值等。

◆ 第七,在经济活动中,负债成为普遍现象。

◆ 社会经济关系的金融化金融化的趋势还体现为社会经济关系的日益金融化。随着经济金融化程度的加深,社会上的各种经济关系越来越多地以金融关系体现出来,即社会上的经济关系越来越多地表现为债权人与债务人之间的债权债务关

◆ 系、股东与公司之间的股权股利关系。在保险业中,投保人与承保公司之间的关系其实也是债权债务关系,因为投保人交给保险公司一笔保费,保险公司就产生了或有负债。

◆ 在现代经济中,金融业的扩张是难以遏制的,经济金融化已经是一个不可逆转的趋势。这不仅是由现代经济的特点与金融业的特点决定的,也是由人性决定的。第一,金融业是现代经济的核心,经济要发展,必须有强大的金融业。

◆ 第二,金融业的高收益具有巨大的吸引力。

发达的国家都有发达的金融业

◆ 金融业的发达首先体现为金融市场的发达,而金融市场的发达程度主要体现在金融市场的广度与深度。金融市场广度的标志之一是市场参与者类型的多样性。

◆ 金融市场发达程度的另一个体现是市场的深度,即市场中是否存在足够大的经常交易量,从而可以保证某一时期、一定范围内的成交量变动不会导致市价的失常波动。换句话说,金融市场的规模足够大,所以不太容易发生整体性的暴涨暴跌。

为什么全世界的富人们越来越富

◆ 我们通常用基尼系数衡量一个国家的收入差距与财富差距。基尼系数以0~1的数字表示,如果一个国家的基尼系数等于0,则这个国家绝对平均;如果等于1,那么这个国家的收入与财富就完全归一个人。我们通常把基尼系数等于0.4视作收入分配差距的警戒线,也就是说,基尼系数到0.4,这个国家的贫富和收入差距问题就比较严重了,到0.5就相当严重了。美国的基尼系数大概是0.47,这说明收入与贫富差距问题很严重。

◆ “了不起的盖茨比曲线”《了不起的盖茨比》这部名著的最后一句话是这样的:“我们奋力前行,逆流而上,但不断地被浪潮推回到过去。”这句话的意思就是,我们奋力向上发展,却因为不断地遭受挫折而无法前进。在对很多国家进行研究的基础上,加拿大经济学家迈尔斯·克拉克提出“了不起的盖茨比曲线”理论。获得2008年诺贝尔经济学奖的普林斯顿大学教授保罗·克鲁格曼也认为,确实存在“了不起的盖茨比曲线”。这条曲线说明,在贫富差距与收入差距越大的社会,父辈的收入水平与财富状况对子女的收入水平与财富状况的影响越大。这意味着,收入的代际流动性越低,子女处于父辈的经济阶层的可能性就越高。社会越不平等,个人的经济地位就越由其父母的经济地位决定,出身普通的平民要想翻身改变自己的命运就越难。用中国传统的话来说,现实社会已经是“龙生龙,凤生凤,老鼠生子会打洞”。

培养金融思维

◆ 罗宾逊夫人曾经说过一句名言:“学习经济学的主要目的就是,不受经济学家们的欺骗。”

“无债一身轻”真的好吗

◆ 中国工业化的资金来源主要有两个:一是在城镇,企业的所有利润全部上交,由政府统一分配;二是在农村,在向农民征收农业税(当时称为“交公粮”)之外,利用统购统销与工农业产品价格“剪刀差”对农村与农民再次收税。统购统销就是农民所生产的农副产品,只能按照国家规定的价格统一卖给供销合作社;农民从事生产所需要的农具、化肥、农药等所有工业品,统一按照国家规定的价格从供销合作社购买。工农业产品价格“剪刀差”就是在统购统销过程中,政府将农副产品的收购价格定得很低,而将工业品的价格定得很高,人为地造成城市与农村之间的严重不等价交换。从1953年开始实行统购统销到1978年改革开放的大约25年间,国家通过工农业产品价格“剪刀差”,到底从农村拿走多少财富呢?专家们从不同的角度进行了计算,其中最高估计是10 000亿元,最低估计是7 500亿元。“剪刀差”导致在那20多年的时间里,农村的农产品等各种资源源源不断地流入城市,而政府对农村与农业又没有进行任何投资,最终导致中国农村与农民一贫如洗、农业极端落后。但是,正是中国农村、农业与农民这一巨大的奉献,为新中国的工业建设提供了原始积累。1973年8月24日,在还清了所有国内外债务之后,周恩来总理宣布,“我们既无外债,又无内债”。[插图]对此,全中国人民都很自豪。但其实,从金融的角度来看,“既无外债,又无内债”的做法是不对的,它造成了很严重的后果,而“三农”问题就是后果之一。如果当时我们具备金融思维,发行国债,借钱搞建设,“三农”问题可能就不会这么严重。

◆ 合理的负债到底有什么好处呢?

◆ 对于企业来说,借债可以让企业少缴税,因为借债的利息开支是在税前扣除的。假如你的企业今年的销售收入是100亿元,你向银行贷款100亿元,利率是10%,企业的所得税率是40%。如果企业没有其他收入与开支,那么你的应税收入就是销售收入减去利息开支,也就是90亿元,按40%的税率,要交36亿元的税。如果你没有任何借款,那么你的应税收入就是100亿元,就要交40亿元的税。因为有100亿元的贷款,少交了4亿元的税,在金融学里,这叫作“税盾”。

◆ 其次,借债可以获得杠杆收益,就是用别人的钱赚钱,所以借债也叫使用杠杆。这个杠杆用得好的话,可以获得很高的收益。华尔街的投资银行非常赚钱,2008年金融危机的时候,高盛的3万多名员工,从前台到CEO,平均年薪达几十万美元。为什么华尔街的投资银行这么赚钱?其中一个很重要的原因,就是它们大量负债,用别人的钱赚钱。金融危机前,华尔街的投资银行使用高达33倍的杠杆,也就是说在用来投资的34美元中,只有1美元是它们自己的,另外的33美元都是借来的。我们可以算一算,33倍的杠杆下,回报率会是多少。假如借债的年利率是10%,你用自己的1美元加借来的33美元进行投资,33美元一天的利息大概是0.01美元。假如美国股市当天上涨1%,你用34美元投资,就可以赚0.34美元,减去0.01美元的利息,净利润是0.33美元,因为你只用了自己的1美元,所以你的回报率,也就是净资产收益率就是33%。

◆ 在物价上涨的情况下,借债可以在一定程度上帮助抵消物价上涨的影响,减少财富的缩水程度。通货膨胀就是物价上涨,它会导致我们的财富缩水。假如2017年的通货膨胀率是2%,那么2017年1月1日花100元可以买到的东西,到2017年12月31日,你要花102元才能买到,这实际上就是1月1日的100元到12月31日变成了大概98元,你的财富缩水了2元。假如2017年1月1日你向银行借了100万元,借期一年,年利率8%,到12月31日的时候,本金加利息你总共要还银行108万元。但是因为有2%的通货膨胀,到12月31日的时候,你还给银行的这108万实际上只相当于105.84万元。所以,在物价上涨比较快的时候,一定不要把钱存在银行里,或者把钱借给别人,而是要向银行借钱。

◆ 负债的4个层次我们可以把负债划分为4个层次,划分的依据就是借债的成本与投资的回报,而借债的成本就是借债的利率。如果你的借债成本小于投资回报,那么你的借债就是合理负债。第一级负债为初级负债,即负债利率< CPI。前面说过,CPI即消费者物价指数,它可以衡量物价上涨的幅度。如果你借贷的利率低于物价上涨的幅度,那就是初级负债。可以说,初级负债是“稳赚不赔”的,实际上是出借方在倒贴借入方。如果有机会借到这样的债,千万不要因为傻傻相信“无债一身轻”这种说法而放弃。现实生活中有没有借债利率低于CPI的情况呢?当然有,例如没有任何手续费或者服务费的无息车贷,提供给大学生的助学贷款也是零利息或者只收取很低的利息。第二级为次级水平,就是CPI <借债利率< GDP增速。我们可以将GDP增速理解为整个国家所有行业所有人的平均投资回报率,也可以大致理解为整个国家所有行业所有人的收入的平均增长率。2018年,中国的GDP增速大概是6.6%,如果你借债的利率小于6.6%,那么借债就仍然是有利可图的。目前中国的通货膨胀率是2%左右,GDP增速是6.6%,所以任何大于2%但小于6.6%的借债利率都是非常合理,也可以说是非常优惠的利率。如果有这样的机会,也不要错过。对企业而言,通常只有国有企业或者有很强关系的民营企业才可能获得这样优惠的贷款利率。对个人来说,如果你没有什么门路的话,一生当中唯一能够从银行得到的这样的优惠贷款可能只有房贷或者公积金贷款。所以,如果你要买房,通常情况下,贷款购房比全款购房好。第三级为中级水平,即GDP增速<借债利率< M2(广义货币)增速。人们通常将M2增速理解为钞票的印刷速度。2018年,M2的增速大约为9%,GDP的增速是6.6%。一般来说,中级水平的负债仍然在可以控制、可以接受的范围之内,如果资金利用好的话,还可以赚取一定的利润。第四级为重度水平,负债利率>M2增速。如果借债的利率大于近期的钞票印刷速度,就属于重度水平的负债。如果印钞票的速度都已经追不上你欠债的速度了,你只能自求多福。

金融就是资金的融通

◆ 金融就是跨时间、跨空间的资金融通

◆ 金融的本质是信用

金融的组成要素之一:如同大超市的金融市场

...

sub:useMemo

Content #

useMemo 的 API 签名如下:

useMemo(fn, deps);

fn 是产生所需数据的一个计算函数。通常来说,fn 会使用 deps 中声明的一些变量来生成一个结果,用来渲染出最终的 UI。

useMemo executes the callback function and returns a memoized value. React uses this value until the callback function executes again. During each render cycle, React compares the contents of the dependency array and reruns the callback function if there are changes.

用户名搜索(useMemo) 用useMemo来实现useCallback

useRef实现计时器

Content #

假设你要去做一个计时器组件,这个组件有开始和暂停两个功能。很显然,你需要用 window.setInterval 来提供计时功能;而为了能够暂停,你就需要在某个地方保存这个 window.setInterval 返回的计数器的引用,确保在点击暂停按钮的同时,也能用 window.clearInterval 停止计时器。那么,这个保存计数器引用的最合适的地方,就是 useRef,因为它可以存储跨渲染的数据。代码如下:

import React, { useState, useCallback, useRef } from "react";

export default function Timer() {
  // 定义 time state 用于保存计时的累积时间
  const [time, setTime] = useState(0);

  // 定义 timer 这样一个容器用于在跨组件渲染之间保存一个变量
  const timer = useRef(null);

  // 开始计时的事件处理函数
  const handleStart = useCallback(() => {
    // 使用 current 属性设置 ref 的值
    timer.current = window.setInterval(() => {
      setTime((time) => time + 1);
    }, 100);
  }, []);

  // 暂停计时的事件处理函数
  const handlePause = useCallback(() => {
    // 使用 clearInterval 来停止计时
    window.clearInterval(timer.current);
    timer.current = null;
  }, []);

  return (
    <div>
      {time / 10} seconds.
      <br />
      <button onClick={handleStart}>Start</button>
      <button onClick={handlePause}>Pause</button>
    </div>
  );
}

我们使用了 useRef 来创建了一个保存 window.setInterval 返回句柄的空间,从而能够在用户点击暂停按钮时清除定时器,达到暂停计时的目的。

...

显示Blog实例(useEffect, useState)

Content #

某个组件用于显示一篇 Blog 文章,那么这个组件会接收一个参数来表示 Blog 的 ID。而当 ID 发生变化时,组件需要发起请求来获取文章内容并展示:

import React, { useState, useEffect } from "react";

function BlogView({ id }) {
  // 设置一个本地 state 用于保存 blog 内容
  const [blogContent, setBlogContent] = useState(null);

  useEffect(() => {
    // useEffect 的 callback 要避免直接的 async 函数,需要封装一下
    const doAsync = async () => {
      // 当 id 发生变化时,将当前内容清楚以保持一致性
      setBlogContent(null);
      // 发起请求获取数据
      const res = await fetch(`/blog-content/${id}`);
      // 将获取的数据放入 state
      setBlogContent(await res.text());
    };
    doAsync();
  }, [id]); // 使用 id 作为依赖项,变化时则执行副作用

  // 如果没有 blogContent 则认为是在 loading 状态
  const isLoading = !blogContent;
  return <div>{isLoading ? "Loading..." : blogContent}</div>;
}

这样,我们就利用 useEffect 完成了一个简单的数据请求的需求。在这段代码中,我们把 ID 作为依赖项参数,这样就很自然地在 ID 发生变化时,利用 useEffect 执行副作用去获取数据。如果在之前的类组件中要完成类似的需求,我们就需要在 componentDidUpdate 这个方法里,自己去判断两次 ID 是否发生了变化。如果变了,才去发起请求。这样的话,逻辑上就不如 useEffect 来得直观。

...

sheet:Search

二分搜索 #

  • poj3258(River Hopscotch) 特殊情况需要专门判断,搜索的结果放在left,left与right不会相等。
  • poj3104(Drying) 体会二分搜索的思路,假定可在drytime分钟内全部烘干,算出所有衣服总共需要使用烘干机的时间,看这个时间是否会在drytime范围以内。
  • poj1759(Garland) 从数列的前两项就可往下推,第1项已知,第2项需要二分查找(实数域)。
  • bailian1064(Cable master) 实数域二分查找,避免四舍五入的技巧。

回溯 #

  • bailian4131(Charm Bracelet) 01背包问题,用回溯法实现。
  • luogu2819(图的 m 着色问题) 练习图的m着色问题。
  • hdu2553(N皇后问题) m叉树回溯,显约束为不同行,隐约束为不同列、不同斜线。显约束控制解空间大小,隐约束是在搜索解空间过程中判定可行解或最优解的。
  • hdu2553(N皇后问题) 排列树回溯,显约束为不同行、不同列,隐约束为不同斜线。解空间更小。
  • bailian2982(Sudoku) 回溯法搜索数独的解法。 数独中网格编号的处理。回溯过程中只要找到解法,就直接返回,无需继续往下搜索。
  • bailian1190(生日蛋糕) 为了更有效的剪枝,需要算出最小体积和面积的前缀和。还要能够根据剩余体积来估计剩余面积。
  • bailian1011(Sticks) 1)枚举长度。木棒的总长度为sumlen,最长木棒的长度为maxlen。因为切割后最长为maxlen,那么原木棒的长度必然大于或等于maxlen。如果原木棒只有一根,那么原木棒的长度就是sumlen。如果原木棒多于一根,那么原木棒的长度一定小于或等于sumlen/2。从maxlen到sumlen/2,从小到大枚举所有可能的原木棒长度,通过深度优先搜索尝试能否组合成原木棒,如果尝试成功,则当前木棒的长度为原木棒的最小可能长度。 2)组合顺序。对木棒长度从大到小排序,如果从小到大排序则会超时。因为小木棒比大木棒灵活性更好,所以先考虑较长的木棒,然后用较短的木棒组合成原棒,更容易成功。

BFS #

  • Full Tank(bailian3761) 优先队列分支限界法。涉及两个维度的图最短路径,一个是费用,一个是地点。可以把当前节点对应的油量抽象成多个节点(例如在位置0有1升油是一个节点,在位置0有2升油是一个节点)​,把费用看作边,那么最少费用就可以类似 Dijsktra算法那样不断地加入节点。于是得到一个扩展节点的策略:每次都加 1升油;如果依靠加的油足够走到下一个节点,就走到下一个节点(减去路上消耗的油,花费不变)​;在广度优先搜索中将所有可扩展的节点都加入优先队列中,如果到达终点,则返回花费。算法优化:用一个数组dp[i]​[j]表示在节点i、当前油量为j时的最小花费。在当前节点及油量对应的花费更小时才生成节点,生成的节点会少很多.
  • Pushing Boxes(bailian1475) 推箱子问题。嵌套BFS,用到多个数据结构。
  • Nightmare Ⅱ(hdu3085) 双向BFS,用到了曼哈顿距离,迷宫不能逐个字符读入,要以字符串读入。

启发式搜索 #

to be at sea

Content #

迷茫,困惑,一头雾水。

Everyone seems so passionate about what they’re doing But I’m a t sea with the company lingo.

From #

take the plunge

Content #

决定奋力一博,决定冒险一试。

I’m going to take the plunge and sign up for those dance lessons.

If you’ve been thinking about buying shares, now could be the time to take the plunge.

From #