β

解决问题-深度优先和广度优化

人月神话的BLOG 155 阅读


在解决问题的时候,往往一个问题可能的解决方法有多个途径,对于非结构化问题解决方法里面,谈到最多的就是首先根据自我已有经验积累,提出最优假设的解决方法之一,然后再对提出的假设进行逐步的验证以最终确认问题是否解决,如果最终不能够解决问题,则往往还需要选择新的假设并继续验证。

一个人,往往解决问题的效率最关键的就是是否能够在第一次就准确的找到最可能解决问题的假设,即根据经验得出最优假设的能力往往是最关键的,而对假设的验证往往仅仅是工作量的问题。

基于以上思路,则可以看到非结构化解决问题的思路是一种类似二叉树遍历中的深度优先搜索模式。即首先基于最优假设,一直进行论证和深度搜索,只有最终验证为无法解决问题的时候再选择次优假设并进行进一步论证。那么对于这种非结构化解决问题的方法可能存在如下问题,即:

首先,当你面对一个问题的时候,如果可行的几个方案解决该问题的概率都是相同,如何选择路径?


你可以看到在这种情况下,你往往只能够使进行随机性的选择,那么这种选择和完全无目的的全部遍历没有任何区别,你最终解决问题的效率往往取决于你的运气。

其次,当我们选择了一个假设的时候,如果这个假设的最终论证需要10个大阶段或步骤,那么一定需要搜索到最底层吗?我们碰壁回头的点究竟应该选择在哪个深度?

对于前面提到的两个问题,如果进一步的思考,我们会发现,在非结构问题解决中,基于假设驱动并实验验证的方式往往还存在一定的改进和扩展空间。而这种改进空间往往就会涉及到引入广度优先搜索方式。

对于广度优先搜索的方式,其一个重点就是:

如果一个问题有三个解决思路,每个思路可能都涉及到3-5个验证步骤,那么我们会优先对三个解决方案的步骤1进行验证。通过迭代1验证完成后我们会进一步评估最可能的解决方案是哪个,然后再进一步对最可能方案展开广度遍历。

广度优先搜索的适用场景就是对于多个解决方案往往可行性概率相差无几的时候,我们为了避免以开始就陷入某一个解决方案的深度中,而在死胡同里面越走越深,我们就必须通过迭代的思路,对多个方案的关键步骤进行尝试,以进一步确定最优概率,然后再基于最优概率点向下搜索。

如上图,如果最终答案是在N点,对于假设的三个分支没有开始任何验证步骤前解决问题概率相同。

如果是深度优先:

最少需要5次:C->G->H->M-N
中间为10次:B->E->K->L->F->C->G->H->M-N
做多为13次:B->E->K->L->F->D->I->J->C->G->H->M-N

如果是广度优先:

则需要次数为7次:B->C->D->G->H->M->N

即如果你对于刚开始提出的假设没有绝对的把握是在C这个分支上的时候,采用广度优先往往是最佳适用的方法。广度优先本身是和概率结合的方法,即通过对所有分支的广度遍历,进一步明确最大概率分支,然后才是展开第二层的广度搜索。

引入广度优先本身就是一种敏捷迭代的思路,即通过广度对原有模糊的内容进一步清晰化,以方便我们决策。

那我们再来看另外一个问题:

如果刚开始通过分析,解决方案在B分支概率为80%,C分支为60%,D分支为40%。

那我们优先进行B分支的深入优先遍历和假设验证,但是当我们验证到第二层深度的时候,我们可能会发现该分支解决问题的可能性已经降低到50%,你应该是及时回头优先去验证C方案,还是说一直将B分支验证完再来考虑对C分支的假设验证?

这个问题本身值得思考,这直接影响到我们平时解决问题的效率问题,或者说我们平时很少去考虑过在提出假设并逐步验证的方法中究竟应该如何回头?或者说当我们面对一个问题的时候,我们往往并不会一开始就构思多个解决方案,并评估每个解决方案可能解决问题的概率。

深度优先+广度优先两种方法结合概率的综合使用才是非结构化解决问题方法的敏捷迭代思路。
作者:人月神话的BLOG
原文地址:解决问题-深度优先和广度优化, 感谢原作者分享。

发表评论