月度归档:

回溯算法

回溯算法是一种可以找到全部或部分解的通用算法。跟暴力穷举法相比,由于可以对搜索域剪枝,因此效率要高。所谓回溯,就是走到某处后如果发现此路不通,会立即退回到上一步,而不是像暴力法那样仍不管不顾地都试一次。因此,回溯法是一种选优搜索法,又称为试探法。

回溯算法的编写格式:

boolean backtrack(candidate) {
    // 递归终止条件
    if (isSolution(candidate)) {
        output(solution);
        return true;
    }

    // 标记当前结点(比如把当前结点标记在路径里)
    place(candidate);

    // 遍历和尝试所有下一级的结点
    for (nextCandidate : listOfCandidates) {
        // 剪枝:对于不合适的结点,直接跳过
        if (isValid(nextCandidate)) {
            // 继续深入到下一层。如果最终能找到解,返回;否则尝试下一个下级结点
            if (backtrack(nextCandidate)) {
                return true;
            }
        }
    }

    // 清除当前结点的标记(比如把当前结点从路径上移除,这意味着从其他结点还能继续来这里)
    remove(candidate);
    return false;
}

说明:

  • backtrack函数是一个调用自己的递归函数,所以要有终止递归的条件
  • 里面有一个循环,用于尝试所有下一级的结点。比如迷宫问题,当走到了某点后,继续尝试相邻的三个结点(前一个结点除外)。循环里应该有剪枝,避免不必要的递归调用开销。
  • 经常需要标记当前结点,并在尝试完从这里开始的所有可能性后清除标记。(比如,不要重复访问已标记的地方)

例题:N皇后问题(八皇后问题)

暴力穷举法:把第一个皇后放置在第一行的每个位置,然后搜索所有的解(尝试把第二个皇后放在其他所有位置,再尝试把第三个皇后放在其他所有位置……)。其实这已经不太“暴力”了,因为完全的“暴力搜索”应该是把第一个皇后也放在棋盘的所有位置,最后再去掉重复的解。

回溯法:把第一个皇后放在第一行的每个位置,由于第一行肯定不能再放置皇后,因此,尝试把第二个皇后放在第二行的每个位置,判断一下是否满足条件,把不满足条件的跳过,然后再在第三行尝试放置第三个皇后……

进一步优化:保存一个长度为N的数组,在某一列放置过皇后的话,就把相应的数组位置设置为true。这样,在下一行放置下一个皇后时,先跳过所有置为true的各列,然后再判断某位置是否符合条件(因为还有斜向的攻击)。在退出前从数组中把其列标志清除。

总结:女人真可怕……我本人的话,性格应该跟“车”比较相似。

颠覆传统的理财观念

施升辉是台湾的投资理财类书籍的作者。我在网上听了他的一个讲座(下文称施先生为“作者”,尽管我没读过他的书),以及观看了他的几个电视访谈节目,觉得他的观点很简单易行,但同时又比较有启发性。下面是一些笔记:

投资可以无脑、佛系,只要追求稳健的投资即可,而且也应该这样做。

投资应该精简。作者简化到两支股票(iDog:根据他的其他节目里的发言,应该是0050和0056这两支ETF)。不要什么投资都做,而是要集中、专注到自己所擅长的项目上。

认命才能赚钱。在股市赚5%很容易,但如果希望赚20-30%,则结果很容易赔钱。(iDog:想赚那么多,就得做风险比较高的投资,这样当然也就容易赔钱了。)大家都把钱存在银行,说明相信银行。既然如此,为什么不去买这个银行的股票呢?银行股一般比较稳健,且股息率高,比如5%。(iDog:这里有点问题。相信银行是一般不懂金融的人,懂的是相信政府对银行的扶持,比如银行会有保险,在一定金额以下,如果银行倒闭,会用保险金来还清客户的储蓄。而且,通过股息赚5%,不等于说就是在股市赚了5%,因为还有股价的起伏。但这属于“微瑕”,对一般人来说还是有启发意义的。)要通过领股息的方法投资股市的话,找那些大到不会倒闭的公司,并且长期坚持支付股息的,投资那些股息回报率比较高的,比如高于5%的那些。(iDog注:其实领股息的投资方法不见得是最优的,因为股息本身就是税后的了,比巴菲特的公司那种不发股息的公司效率更差些,除非公司不会善用这部分钱。但是,对普通人来说,按这个思路投资,会起到两种效果:一个是敢于在股市大跌的血雨腥风的时候入场买,另一个就是实现了buy-and-hold的策略。)

股票是凡夫俗子唯一可以投资的项目。但是关键在于安于比较现实的回报率,不要好高骛远。

定期存款:只存两年的生活费,其他的钱用于投资。两年生活费的储蓄是为了防止股市大跌的时候因缺钱而不得不卖出股票。

一些金融工具不是用来赚钱的,比如旅行保险(没人希望飞机掉下来去赚这笔钱)。第一栋房子就不是用来赚钱的,而是用来住的。

买股票的一个标准是:买入后晚上能睡得着觉。套牢是投资人的宿命,所以不要怕被套牢,而是要拥抱套牢。指数ETF或者高股息ETF也是不会倒闭的。对于不会选股的人,可以投资这些。对于台湾市场来说,市场联动ETF为0050(目前较高,在合适的时候买或用美元平均法定投)和0056(高股息的30家企业组成的,价格波动十分无聊,但股息回报率可达到6%)。

“出来混迟早是要还的”。在股市大跌的时候,要勇敢地冲进去买。买了当然有可能套牢,但套牢时投资人的宿命,所以不要怕。为了降低风险,就要选择套牢了也不用太害怕的投资目标,比如不会倒闭的大公司,或者大盘指数。0050(台湾Top 50公司,相当于道琼斯指数)适合波段操作,在KD为20时增加头寸,达到80时减小头寸。0056(台湾高股息股票Top 30)可以“存股”,即长期持有。

iDog注:在一次访谈节目中,施老师和“不败教主”陈重铭老师同台。陈老师对DK的20/80策略做修正如下:

  • 盘整行情:按日线图,DK<20时买;DK>80时卖
  • 上升行情:日线DK<20时买;周线DK>80时卖
  • 下降行情:周线DK<20时买;日线DK>80时卖

原因:股价上升的时候,买入的机会不会太多,因此应该看日线DK来买入,否则看周线DK的话,恐怕根本没有机会;在卖出时,则看周线DK来尽量不要轻易地卖出。下降行情同理。盘整行情则最适合做这种波段操作,故日线即可。施老师的回应:比如下降行情中,日线DK>80的时候,有可能还是处于套牢状态,在这种情况下,他是不会卖的,毕竟还有股息可领。陈老师表示同意。

附录:投资者贱芭乐的DK操作法:他是采用波段操作,主要看周线DK。这样,一方面不需要像看日线那样必须每天盯着看,另一方面又不用像看月线那样一年交易不了一两次。看周线的话,完成一次买卖大约需要四五个月。

  • 选股范围:从0050的50支股票里选那些优秀公司的股票,防止出现风险过大的情况(比如公司倒闭等)
  • 交易方法:按周线图的DK来交易:处于低位出现金叉时买入,高位出现死叉时卖出。有时候会出现DK线条纠结在一起的情况,金叉和死叉频繁出现。在出现这种不明确的情况时,就不要操作这支股票。

iDog:关于存股:多年前在日本混的时候,我广泛涉猎各种投资书籍杂志,读到过这种思路。就是跟存钱一样,改为存股票。也就是对投资人来说,不是把注意力放在股票价格上,而是股票数量上。这里有以下的道理:

  • 存钱vs存股:存钱会受到通货膨胀的侵蚀,也就是说,表面上看起来是零风险,实质上是100%的贬值风险。而存股票的话,在宏观上看是可以抵御通货膨胀的,而且还可以享受到总体经济发展带来的成果。当然,微观上看,会有个股和某些个时间点上的账面损失。
  • 注重股票的价格vs股票的数量:我们都知道,股票的价格只是大家认为它值那么多钱,而不是它的真正价值。因此,股票的价格是比较主观的,感性的,和缺乏理智的。而股票的数量则真正反映了你占有的资源的多少。因此,与其在股市动荡的时候跟着时喜时忧的,不如“宠辱皆忘”,一门心思地增加自己持有的股票数量。当然,这里有个问题要注意:股价不是完全的没有道理,如果公司的业务出现问题,股价一定会下降的。此时,是不是要乘机买入更多的股票(或者出清手里持有的股票),主要取决于该公司能否克服这个问题。如果不管三七二十一地一味低价买入,那么公司倒闭了的话,只能是一大把的毫无价值的废纸。因此,用“存股”的策略时,应该存那些稳健的股票或指数。

作者本人以前在证券公司工作,后来由于市场和业绩情况被裁员。之后为自己投资时,为了追求较高的回报率而使得投资组合的风险较大,且很容易落后于大盘。他意识到,要想睡好觉,只要跟大盘同样即可。因此,他就把股票都卖掉,换成了指数ETF。巴菲特对普通人以及他自己的夫人的投资建议也是买指数基金。作者现在每月平均可拿到6-7万元的股息,子女也已成年,故生活悠闲,自称“乐活大叔”。

他的建议是,只要配息超过5%,并且不会倒闭(比如0056这种指数ETF),就可以放心大胆地买入并持有。假如这些都能崩溃的话,新台币本身也会不再有任何意义,因此不需要担心。(iDog注:货币就是某种大众全员的信仰,否则,则不过是废纸而已。这种想法让我想起在日本生活时的事情。如果你买房子的时候问房产经纪:如果发生大地震倒塌了会怎样呢?他一般会告诉你:如果这种情况发生的话,肯定不只是你自己的房子甚至你这栋楼倒塌,而是一个大范围的倒塌,因此不用担心。也就是说,有点法不责众的感觉。如果某ETF里的公司普遍倒闭的话,当然基本上意味着整个经济体都要崩溃了,因此,有钱没钱基本上都没什么区别了。当然其实,还是可以通过拥有黄金和海外资产等方式实现风险分散,从而在一定程度上抵御这种无法抗拒的灾难的。所以说,如果只是着眼于比如台湾等某一个地区的金融市场的话,格局还是小了一点儿。:-) )

他在1990年,把股市里赚到的钱用于在台北市买房,也因此而避开了之后的股灾,所以才能有今天的生活。几年前他又买了一套房(不在台北),为了抵御老年介护的风险(需要介护时卖掉房子,否则就作为资产存下来)。

给年轻人的建议:每月从工资里必须拿出6000元(新台币),一年就有72,000元,可以买3000单位的0056。这样持续6年,就可获得500,000元。如果是年轻夫妻的话,二人共有100万元,可算是人生的第一桶金。一个人的话,每月拿出1万元,6年后也会有100万元。此时,可作为首付在台北的周边地区买房(台北市太贵)。对于第一套房子的观点是,把它看作是生活必需品,而不是投资物件。不要买太贵的,比如年轻人不需要有电梯的楼房,而且在新北市的话也不需要养车(不用买车位)。买了房子后,有钱不要急着还清房贷(因为利率相对很低),而是继续之前的投资。

对房子的观点:目前台北地区显然租比买合算(iDog:我觉得几乎所有华人多的地区都是如此),但60岁以上的人,房东多不愿意继续租(iDog注:我想主要有如下因素:老年人由于没有工资收入,有付不起房租的风险;有在房子里死亡的风险,对今后出租有负面效果。),因此,如果能保证在60岁时能买得起房子的话,就不需要早买了,否则,为了以防万一,还是应该尽早买一个比较安心。第一个房子就是用于自住,能买得起最重要,而不是传统的“location;location;location”的条件(iDog注:三个location的原则主要是对于投资性的房地产。对自住房没那么重要,相反,你喜欢住哪里更重要一些。比如交通便利的地方地脚好,但你可能嫌吵。)。对于年轻人来说,离车站远一点,没有电梯,不要停车场,价格就会便宜下来,在新北市,还是能找到1000万以下的房子的。(iDog:以东京来比较的话,1000万新台币——也就是大约4000万日元——的房子算是比较大和比较好的了。看来大台北地区的房子还是十分贵的。)按照经济学规律,少子化会带来房价的下降。买房子就是为了以防万一。

给退休人士的建议(假设有自己的房子,子女已成年):夫妻二人生活费每年50万元(没有出国旅游的情况下足够),资金需要1100万元。配置方法:1000万元投资股息率5%的股票,用于赚取每年50万元的生活费;100万元为生活紧急预备资金,相当于两年的生活费,在遇到股灾的时候避免不得不卖出股票。

投资理财的道路上,不要相信任何人,包括自己的爸爸。自己的爸爸当然不会害自己,但他的观点就一定对吗?(iDog注:我也是这样认为的,有时候在论坛上会见到年轻人问自己积攒下的多少加元应该怎样投资的问题,我都会说要去学习投资,直到自己清楚该怎样投资为止,而不要随便相信任何人的建议。我不但不会相信任何人,而且连非指数型的基金都不信任。这都是在日本时通过大量的涉猎学到的。现在国内似乎私募、基金、ETF等比较热,我也时而被推荐买入这些,我都是不假思索地谢绝。实际情况是,只有自己才不会欺骗自己的,顶多是学艺不精,但在这种情况下可以投资指数啊。)

2008年到2020年间,没有出现过股灾(iDog注:网上经常有下跌了区区的2%左右就称为“断崖式下跌”的,这属于一惊一乍型,或者外行硬冲内行型。但2020年3月的跌幅超过了20%。),但股灾一定会出现的,尽管没人知道什么时候会出现。一些年轻人比较急功近利,追求高回报,这样就难免趋向于投机。这样的话,如果碰到一次股灾,可能就会把以前努力赚到的那些钱都赔光。因此,要强调稳健型投资,原则是“稳稳赚,慢慢赚,久久赚。”(iDog注:巴菲特说投资最重要的就是不赔钱,跟这里说的是一个道理。虽说不赔钱比较难,但我们至少可以做到少赔钱。)

不要过度相信长期的复利效果。如果每年赚10%,20年后会变成原来的6.72倍。但这里有个假设是长期的每年都赚10%,这是不容易的。如果下跌了50%,要涨回去就得涨100%,而要涨到下跌前的金额加10%,就需要涨120%。由于股灾总会到来,因此不要过度相信长期的复利效果。如果股市里赚了钱,就要把钱用掉,因为用掉的钱才是自己的(iDog注:这可能是个哲学问题。这样说的人的主要想法是:钱不过是一个数字或者一堆没有价值的纸,只有换成有价值的东西才算是有意义。其实,这也不过是换了一种存在形式而已。比如,换成房子或者黄金,也不过是某种有形的东西,某种可以用货币来衡量的东西。因此,没什么本质的区别,而且有形的东西保存起来还麻烦,不如账户里的金钱不过是一串数字,不需要自己特意去保存。另,卖掉的股票应当看作是某家公司的一部分权益,因此,与之相比,房子或黄金不见得更有意义。当然,如果把金钱投资于自己,比如学习新技能等等,则是另一回事。这样可能是真的有意义了吧?)。快速用掉钱的方法之一就是买房地产,而且房子是相对保值的,不像股票那样起起落落。(iDog注:一般股市大涨的时候,房地产市场往往不会太热,在股市疯狂的时候,国内时有“卖房炒股”的人。因此,股票投资如果赚了钱,卖掉一些股票并买房子的话,就相当于对投资组合的再平衡。)卖掉股票后,不要用储蓄的形式保存财富,因为有通货膨胀的因素。房地产是比较好的方式之一。

投资理财越简单越好,精力可以用于生活中更有意义的事情上。作者本人由于有房子,而且被动收入足够日常开销,因太闲而到大学里去学习写剧本。

以被动收入生活要满足两个条件:

  • 买必要的保险。没有保险的话,比如生一场大病,就会让被动收入化为乌有。(iDog注:指那些真正的保险,不是那种以理财为名义的莫名其妙的保险。)
  • 有自己的房子。如果租房子,万一被房东赶出去(iDog注:这说明台湾的相关法律对租客的保护不太充足?),就面临必须自己去买房子的问题,这样,被动收入就化为乌有(iDog注:这里应该是指买房子需要投入一大笔钱,这样就消减了自己赚取被动收入的资产规模,因此被动收入就会减少甚至消失。但是,总可以去找其他房子租吧?可能是指老年人,不容易租到房子的情况吧。)。要把保险费看作扔掉的钱(iDog:破财免灾),不要用保险的形式投资。保险种类的广度要大(就是各种情况都保到),但深度不用太大(否则开销太大)。

另,作者似乎是在2003年时被公司裁员(当时市场正是低点),而那也是我作为一个年轻人开始对投资理财产生兴趣的一年。之前则一直是关心IT技术和修行等等,对股票持负面态度(当时正值网络泡沫崩溃的时候,电视里也总是一些耸人听闻的市场下跌的消息。),后来可能是出于家庭责任感而开始逐渐思想变得成熟了吧。人生就是有各种各样的际遇。