编程世界之外的经典难题
时间:2022-08-28 23:00:01
我们要讨论的第一个经典问题是一个需要过河的农民面临的问题。读者以前可能遇到过类似的问题。
怎样过河
一个农民带着一只狐狸、一只鹅和一袋玉米过河。农民有一艘划艇,只能容纳他自己的一个。不幸的是,狐狸和鹅都饿了。狐狸和鹅不能单独呆在一起,因为狐狸会吃鹅。同样,鹅也不能单独和那袋玉米放在一起,因为鹅会吃玉米。农民怎么能把一切都送过河呢?
图1.1展示了这个问题的场景。如果读者以前从未遇到过这样的问题,他们可以花几分钟仔细研究如何解决它。如果你以前遇到过这样的问题,你也可以回忆起它的解决方案,看看你是否能独立解决它。
图1.1 狐狸、鹅和一袋玉米。船一次只能携带相同的物品。狐狸不能和鹅单独呆在同一边,鹅不能和玉米单独呆在同一边
很少有人能在没有任何提示的情况下解决这个问题。作者也承认自己没有这种能力。以下是人们解决这个问题的常见想法。因为农民一次只能携带一件物品,他需要多次往返才能将所有物品送到对岸。第一次过河时,如果农夫带走狐狸,鹅会和那袋玉米单独呆在一起,肯定会吃玉米。类似地,如果农民选择带走那袋玉米,狐狸就会和鹅单独呆在一起,鹅也难逃被吃掉的厄运。因此,农民必须在第一次旅行中带鹅过河,从而出现如图1所示.2所示场景。
图1.2 解决狐狸、鹅和玉米问题必然采取的第一步。但是,从这一步开始,所有后续的步骤看上去都将以失败告终
到目前为止,一切都很正常。但在第二次过河时,农民必须带走狐狸或玉米。然而,无论农民这次带走了什么,当农民从另一边回到最后一件物品时,第二次旅行带来的物品必须与鹅单独呆在另一边。这意味着狐狸和鹅,鹅和玉米。因为这两种情况都是不可接受的,所以这个问题似乎无法解决。
如果读者以前见过这个问题,很可能还记得解决方案的关键要素。正如前面提到的,农在第一次旅行时带走鹅。在第二次旅行中,我们假设农民带走了狐狸。但他并没有让狐狸和鹅一起呆在对岸,而是在返回时把鹅带回了近岸。然后,农民把玉米带到对岸,把狐狸和玉米放在一起,然后回来。农四次过河时,农夫终于把鹅带走了。图1.展示完整的解决方案。
这个问题很难,所以大多数人从来没有想过把物品从另一边带回到另一边。有些人甚至认为这个问题是不公平的,说:你没有说我可以带回来!这是真的,但在描述这个问题时,这个问题并没有说禁止从另一边带回来。
图1.3 狐狸、鹅和玉米问题的逐步解决方案
想象一下,如果事先明确说明物品可以从对岸带回来,这个问题就会很容易解决:
农民有划艇来回搬运物品,但每次只能容纳农民自己和他的三件物品之一。
有了这个解释,很多人都能解决这个问题。这说明了解决问题的一个重要原则:如果你没有意识到所有可以采取的行动,你很可能无法解决问题。这些动作可以称为操作。许多问题可以通过列出所有可能的操作来解决。在找到可行的方案之前,我们只需要测试这些操作的每个组合。综上所述,就是用更正式的术语重新陈述一个问题,往往可以找到以前被我们忽的解决方案。
首先,我们忘记了这个问题的解决方案,然后以更正式的方式解释这个特定的问题。首先,我们列出了约束条件。这个问题的关键约束如下。
1.农民一次只能在船上放一件物品。
2.狐狸和鹅不能单独放在同一边。
3.鹅和玉米不能单独放在同一边。
这个问题是约束条件重要性的一个很好的例子。如果我们去除所有的约束条件,这个问题就毫无难度。如果我们消除了第一个约束,我们可以简单地一次携带三件物品过河。即使一次只能在船上放两件物品,狐狸和玉米也可以先过河,然后带鹅过河。如果我们去掉第二个约束(但保留另外两个约束),我们必须小心。先带鹅过河,再带狐狸过河,最后带玉米过河。因此,如果我们忘记或忽视任何约束,就相当于遇到小林丸号。
接着,我们列出所有的操作。陈述这个问题的操作可以采用多种不同的方式。我们可以创建一个特定的列表,列出所有可以采取的操作。
1.操作:将狐狸带到河对岸。
2.操作:将鹅带到河对岸。
3.操作:将玉米带到河对岸。
然而,我们必须记住,以形式化的方式重新陈述问题的目标是更好地找到解决方案。除非我们已经解决了这个问题,并发现隐藏可能的操作(即将鹅带回附近),否则我们无法通过上述操作找到这个操作。因此,我们应该尝试列出更基本的(或参数化的)操作。
1.操作:将船从岸边划到另一边。
2.操作:如果船是空的,从岸上装载一件物品。
3.操作:如果船不空,将物品卸到岸上。
通过用最基本的术语来考虑这个问题,上面的操作列表可以让我们很容易地解决这个问题,所以我们不会认为把鹅从另一边带回近岸是一个奇妙的想法。如果我们列举所有可能的移动序列,当每个序列违反约束条件之一或重复之前看到的配置时,终止序列,最终得到图1.解决这个问题。通过对这一问题的约束和操作的正式重新陈述,成功地避免了其内在的困难。
经验和教训
狐狸、鹅狐狸、鹅和玉米中学到什么?
以更正式的方式重新陈述问题是一项非常好的技能,它可以让我们对问题有更好的洞察力。许多程序员试图与其他程序员讨论问题,不仅因为对方可能有答案,而且因为清为清楚地陈述问题往往会激发有用的新想法。重新陈述问题相当于与其他程序员讨论问题,但现在是一个人装饰两个角落。
更深远的意义是,认识到思维问题可能与思维解决方案具有相同的工作效率,甚至更好。在许多情况下,通往解决方案的正确方法本身就是解决方案。
瓷砖滑块有许多不同的规格,正如我们后来看到的,它提供了一个特定的解决方案。以下是3×对瓷砖滑块问题3版本的描述。
滑动8块
一个3×3.网格中放置8块瓷砖(编号为1~8),其余为空。起初,网格的配置非常混乱。瓷砖可以滑入相邻的空间,使其原始位置为空。这个问题的目标是在网格中滑动瓷砖,使它们从左上角有序地排列在网格中。
图1.4显示了这个问题的目标。如果读者以前从未遇到过这样的问题,他们可以花一些时间来考虑如何解决它。大量的滑动瓷砖问题模拟程序可以在互联网上找到,但最好用扑克牌或索引卡在桌子上进行测试。.5显示了推荐的初始配置。
图1.4 8块瓷砖版瓷砖滑块的目标配置,空间表示相邻瓷砖可以移动到空间
图1.5 瓷砖滑块问题的一个特定初始配置
这个问题与前面讨论的农民、狐狸、鹅和玉米完全不同。过河的困难在于可能会忽略其中一个可行的操作。这种情况不会发生在这个问题上。对于任何特定的配置,空间周围最多有4块瓷砖,可以移动到这个空间。这种描述列出了所有可能的操作。
这个问题的难度在于解决方案所需的漫长操作环节。一系列的滑动操作可能会将某些瓷砖滑到其目标位置,并将其他瓷砖移到正确的位置,或者将某些瓷砖滑到目标位置,并将其他瓷砖滑到远离目标位置。因此,很难确定任何特定的操作是否向最终目标迈进了一步。很难形成策略,因为没有办法衡量进度。许多人通过随机滑动来解决这个问题,希望能够滑动到最终的目标配置。
然而,瓷砖滑块的问题仍然有策略。为了展示其中一种方法,我们可以考虑一个长方形而不是正方形的小网络。
滑动5块
有一个2×3.网格中有5块瓷砖(4~8),其余1个空间。起初,这些瓷砖排列得很混乱。瓷砖可以滑动到相邻的空间,使其原始位置成为空间。这个问题的目标是使网格中的瓷砖排列有序,4号瓷砖出现在网格的左上角,然后依次等待。
读者可能会注意到这些瓷砖是4到8号,而不是1到5号。读者很快就会知道为什么会这样安排。
虽然是和8块瓷砖滑块一样的基本问题,但显然只有5块瓷砖简单多了。试着完成如图1所示.6所示配置。
如果你尝试几分钟,你很可能会找到一个解决方案。我开发了一种特定的技能,从少量的瓷砖滑块问题开始。这个技能,加上我们将来要讨论的,可以用来解决所有的瓷砖滑块问题。
图1.6 2×3版瓷砖滑块的具体起始配置
基于对一组瓷砖位置形成环路的观察,我称这一技巧为串列。在这些位置加上空间,形成一系列瓷砖,可以在这个环路中旋转,同时保持这些瓷砖的相对顺序。图1.7演示了由四个位置组成的最小可能串列。在最初的配置中,1可以滑动到空格,2可以滑动到1移动后留下的空格,最后3可以滑动到2移动后留下的空格。这样,空间与1相邻,使串列继续旋转。因此,这些瓷砖可以有效地旋转到任何位置。
图1.7 “串列”,与空格相邻的瓷砖开始形成了一条瓷砖路径,在游戏过程中可以像一列火车一样滑动
同时,我们可以使用一系列的瓷砖来保持它们之间的相对关系。现在让我们回到前面的2×网格配置3。虽然这个网格中没有一块瓷砖位于它最终的正确位置,但有些瓷砖靠近它们需要在最终配置中靠近的瓷砖。例如,在最终配置中,4将出现在7上,这两块瓷砖目前相邻。如图1.如8所示,我们可以用一个包含6个位置的串列将4和7移动到最终正确的位置。当我们完成这个操作时,剩下的瓷砖几乎都处于正确的位置,只需要再移动一下8就可以了。
图1.8 从配置1出发,经过2次沿规划的“串列”旋转之后来到配置2,然后只要滑动1次就可以产生最终的配置3
这种技巧是怎么解决所有瓷砖滑块问题的呢?考虑最初的3×3配置。我们可以用包含6个位置的串列移动相邻的1和2,使2和3相邻,如图1.9所示。
图1.9 从配置1出发,瓷砖沿规定的“串列”旋转到达配置2
这样1、2和3就相邻了。在8个位置的串列中,我们就可以旋转1、2和3了,使它们到达最终的正确位置,如图1.10所示。
图1.10 从配置1出发,瓷砖经过旋转之后到达配置2,这样瓷砖1、2和3位于正确的最终位置
注意瓷砖4~8的位置。这些瓷砖的配置正好与前面的2×3网格的例子相同。这是一个至关重要的观察。把瓷砖1~3放在正确的位置之后,我们就可以把剩余的瓷砖看成是一个更小、更容易解决的独立问题。注意,为了使这种方法可行,必须要解决一整行或一整列的瓷砖。如果我们把瓷砖1和2放在正确的位置,但3仍然置于别处,那样就无法在不移动左上角两块已经就绪的瓷砖的情况下,把任何瓷砖移动到右上角位置。
这个技巧也可以用于解决规模更大的瓷砖滑块问题。常见的最大尺寸是15块瓷砖,也就是4×4的网格。这样的问题也可以用分解法来解决:首先把瓷砖1~4移动到正确的位置,这样就只剩下一个3×4的网格,然后再完成最左列的瓷砖,这样就只剩下一个3×3的网格。此时,就只剩下8块瓷砖需要移动了。
经验和教训
我们可以从瓷砖滑块问题中学到什么呢?
由于瓷砖移动的次数相当之多,因此无法在初始配置时就规划一个完整的解决方案。但是,无法规划完整的解决方案并不意味着就无法采取策略或技巧系统性地解决问题。在解决编程问题时,有时候会出现无法看到通向解决方案的清晰道路的情况,但这绝不能成为跳过计划和采用系统性方法的借口。更好的办法是采用一种策略,而不是通过简单地反复尝试和失败来解决问题。
我是通过对较小的问题进行研究时发现这种“串列”技巧的。在编程中,我常常会使用这种类似的技巧。在面临一个复杂的问题时,我常常会对这个问题的削减版本进行试验。这些试验常常能够产生有价值的思路。
另一个经验是问题的细分通常并不是非常明显的解决之道。由于移动一块瓷砖不仅影响这块瓷砖本身,还会影响接下来可能发生的移动,人们可能觉得瓷砖滑块问题必须在一个步骤中完成,而不能分阶段解决。因此,花时间研究怎样对问题进行细分通常是非常合算的。即使无法找到一种清晰的细分,仍然有助于增强对这个问题的理解,可以促进这个问题的解决。在解决问题时,头脑里已经拥有一个特定的目标总比随机的尝试要好得多,无论最终是否能够实现这个目标。
数独游戏作为一种在报纸和杂志上出现的益智游戏,其流行程度已经达到了惊人的地步,并且已经发展成一种基于网络和手机的游戏。数独拥有许多不同的版本,但这里只简单讨论传统的版本。
完成数独方块
一个9×9的网格,其中部分方格填有数字(1~9),玩家必须填满剩余的空格,并满足下面这个约束条件:对于每一行和每一列,每个数字恰好只出现1次。而且,对于粗框内的每个3×3区域,每个数字也恰好只出现1次。
如果读者以前曾经玩过这个游戏,很可能已经知道应该采用什么策略在最短的时间内完成一个空格。我们首先观察如图1.11所示的方块,关注最关键的起始策略。
数独游戏的难度差异极大,它们的难度取决于需要填充的空格数量。按照这种衡量方法,这是一个相当容易的问题,因为已经有36个空格已经填好,只需要再填写45个空格就可以完成任务了。问题在于,我们应该首先填充哪个空格呢?
图1.11 一个很简单的数独方块问题
记住,这个问题包含了约束条件。在每一行、每一列以及粗框内的每个3×3区域中,9个数字必须都正好出现1次。这些规则决定了我们应该从哪里着手。最中间的3×3区域的9个方格已经有8个填好了数字。因此,正中心的那个空格只可能填入这个3×3区域的其他方格没有出现的那个数字。我们应该从这个空格开始解决这个问题。这个区域所缺少的数字是7,因此我们在最中间的那个空格中填入7。
填好了这个数字之后,注意最中间那列的9个值已经有7个已经填好,只剩下2个空格,必须填上这一列所缺少的两个值:3和9。与这个列有关的约束条件允许把这两个值放在任意一个位置,但是注意3已经在第三行出现过,9已经在第七行出现过。因此,我们应该把9填在中间那列的第三行,把3填在中间那列的第七行。图1.12对这些步骤进行了概括。
图1.12 解决示例数独问题的开始步骤
我们不打算完成整个方块的填写,但前面这几个步骤已经说明了重要的一点,就是搜索那些可能出现的值最少的空格。在最理想的情况,就是只剩下一个空格。
经验和教训
我们在数独问题中所学到的主要经验就是应该寻找问题约束性最强的部分。虽然约束条件往往使问题难以着手(还记得狐狸、鹅和玉米问题吗),但它们也可以简化思路,因为它们消除了很多选择。
尽管我们不会在本书中详细讨论人工智能,但还是要简单地提一下,在人工智能中解决某些类型的问题时有一个称为“最大约束变量”的规则。它表示在一个问题中,当我们向一些不同的变量赋一些不同的值来满足约束条件时,应该从约束性最强的变量开始。换用更通俗的说法,就是那些可能采用的值具有最少的变量。
下面是这种思维方式的一个例子。假设有一组工友计划一起吃午饭,并且想要找一家每个人都喜欢的餐厅。问题在于,每个工人对于整个小组的决策都会施加某种程度的影响。例如,Pam是个素食主义者,Todd不喜欢中国菜等。如果目标是最大限度地减少寻找餐厅的时间,首先应该询问对餐厅最挑剔的那个工人。例如,如果Bob对很多食物都过敏,首先列出他可以进食的餐厅列表是非常合理的。像Todd不喜欢中国菜这样的癖好应该放在最后考虑,因为这个困难是很容易克服的。
这个技巧往往也可以用于编程问题。如果问题的某个部分具有很强的约束条件,很可能应该从这一部分开始着手,这样就不必担心把时间花在将来可能会返工的任务上了。一个相关的推论是:应该从最显而易见的那部分任务开始着手。如果可以解决这个部分的问题,就可以在此基础上继续执行其他可以完成的任务。通过审视自己的代码,可能会激发自己的想象力,从而解决剩余部分的问题。
对于上面这几个问题,读者以前可能也看到过。但是对于本章的最后一个问题,除非以前曾经阅读过本书,否则绝不可能见过,因为这是我自己“发明”的。请认真阅读,因为这个问题的描述稍微有点复杂。
一种敌对的外星生物Quarrasi登陆到地球上,你在战斗中被它们抓获并关押在飞船里。你设法打倒了看守,尽管它们体形庞大并且长有触角。但是,为了逃离飞船(仍然在地面上),必须打开巨大的舱门。开门的指令非常奇怪,它是用英语的形式显示的,但非常难弄。为了打开舱门,必须沿着轨道滑动3个条状的Kratzz,从右侧的接收器滑动到位于门尽头的左侧接收器,距离大约3m。
这个任务相当简单,但是必须避免触发警报。警报的工作原理如下:每个Kratzz就是一个或多个星形的水晶力量宝石,称为Quinicrys。每个接收器具有4个传感器,如果一个纵列中Quinicrys的数量为偶,它们就会被点亮。如果被点亮的传感器的数量正好为1,就会发出警报。好消息是每个警报都配备了一个抑制器,只要按下这个按钮,就可以防止警报发出声音。如果可以同时按下所有的抑制器,问题就非常简单了,但是没有办法做到这一点,因为人类的胳膊过于短小,不比长长的Quarassi触角。
根据上面的描述,怎么才能在不触发任一警报的前提下滑动Kratzz打开舱门呢?
图1.13展示了初始配置,3个Kratzz都位于右侧的接收器。为了清晰起见,图1.14展示了一种不好的思路:把最上面那个Kratzz滑动到左侧接收器会导致右侧接收器处于报警状态。你可能想到用抑制器来避免报警,但是要记住,你刚刚把最上面的Kratzz移动到左侧接收器,够不着相距3m的右侧接收器上的抑制器。
图1.13 Quarrasi锁问题的初始配置。必须滑动当前位于右侧接收器的3个Kratzz条,在不触发任何一个警报的情况下把它们滑动到左侧的接收器。当偶数个星形的Quinicrys出现在上面的纵列时,就会点亮一个传感器,如果正好有一个被连接的传感器被点亮,就会触发警报。抑制器可以防止警报发声,但你只能控制自己所站那一侧的抑制器
图1.14 处于报警状态的Quarrasi锁。你刚刚把最上面的Kratzz滑动到左侧的接收器,因此够不到右侧的接收器。右侧警报的第2个传感器被点亮,因为出现在那个纵列的Quinicrys数量为偶,现在正好是一个传感器被点亮,所以就会触发报警
在继续尝试之前,先花点时间研究这个问题,设法确定一个解决方案。这取决于看问题的着眼点,此问题并没有看上去那么难。认真地说,要在尝试之前先对它进行思考!
考虑好了吗?现在是不是能够想出一个解决方案?
为了回答这个问题,可以选择两条可能的路径。第一条路径就是不断尝试,不过它是错误的做法:尝试用各种方式移动这几个Kratzz,一旦达到警报状态时就返回到前一步骤,直到最终通过一系列的移动,成功地打开锁。
第二条路径是认识到这个问题实际上是个机关。你从前可能没看到过这种机关,它实际上就是披着伪装外衣的狐狸、鹅和玉米问题。尽管警报的规则是以通用的方式描述的,但是与这种特殊的锁有关的组合却是有限的。如果只考虑3个Kratzz,我们只需要知道接收器上的哪些Kratzz组合是可以接受的。如果我们把这3个Kratzz分别命名为top、middle和bottom,那么会触发报警的组合是“top和middle”以及“middle和bottom”。
如果我们把top重新命名为狐狸,把middle重新命名为鹅,把bottom重新命名为玉米,这样所有的麻烦组合都与狐狸、鹅和玉米问题一样了,也就是“狐狸和鹅”和“鹅和玉米”。
因此,这个问题的解决方式与狐狸、鹅和玉米问题相同。我们把middle(鹅)滑动到左侧的接收器,再把top(狐狸)滑动到左侧,当我们移动top(狐狸)时摁住左侧警报的抑制器;接着,我们把middle(鹅)滑动回右侧的接收器;然后,我们把bottom(玉米)滑动到左侧;最后,我们把middle(鹅)再次滑动到左侧,这样就打开了锁。
本文节选自《像程序员一样思考(修订版)》
本书适合初级、中级的各种语言的程序员,需要掌握问题解决方法和算法的程序员以及计算机专业的学生。本书不会告诉你在特定情况下如何做,但是,它会帮助读者培养自己的问题解决能力。特别适合对编程深入研究的读者。