有些问题之所以很困难有可能并不是问题本身很困难，而是自己没有把问题定义清楚。有时候把一个要解决的问题定义清楚问题本身就解决了一大半。这篇笔记是想通过一个简单的例子，介绍一下在人工智能或者机器学习领域中如何定义一个问题，顺便介绍一下解决这个问题的办法。
问题很简单，是一个导航问题，如图是罗马尼亚的地图，从Arad城市到Bucharest寻找最佳路径。
OK 把这个问题分解一下：
1、问题的初始状态是什么（Initial State）?
在Arad城市
2、行动（Action）是什么？
从一个状态（城市）移动到下一个状态（城市）。
3、结果（Result）呢？
状态变成在另一个城市了
4、这个状态是目标状态吗？需要测试一下（Goal test）。
是目的地Bucharest吗？是或不是
5、如何评价选择的路径（Path cost）？
路径的总里程
问题理解清楚了，接下来就是路径算法了，我们再把问题简化一下：
将问题想象成一个树枝（解决这个问题的办法跟之后介绍的“决策树”机器学习方法很像），初始地是头部，目的地是右下角。
怎么到达右下角最后一个目的地呢？ 先介绍一种简单的算法，名字叫做“Breadth First” 故名思意就是“最短步数优先”。算法就会如图所示，先找只有需要走一步的城市（“2”和“3”），然后找需要走两步的（城市“4”，“5”，“6”，“7”）.... 每走一步都会判断是否到达目的地，最后找到最佳路径1->3->7。
那如果找到了不止一条路呢？那算法就会将每个路径的总里程（Path cost）进行对比，选择路程最短的。“总里程”就是解决方案的评价标准。
这种算法虽然简单，但是非常耗时，比如上图找了7个路径最终才找到最佳路径，如果分支很多计算量就会成倍增加。
另外一个比较“聪明的”的算法是“Cheapest First” ，这个算法首先要知道每个城市（状态）离目的地的直线距离（这个需要标注），当每走一步之后就会选择预测距离（已走距离+距目的地直线距离） 最短的城市。
比如上图所示，红色数字表示城市离目的地的距离。我们从城市“1”出发，按照“Cheapest First”原则，第一步将会到城市“2”因为“2”的预测距离（0+2=2）要比“4”的预测距离（0+5=5）大。第二步会选择走到“3”（预测距离 2+2 =4小于到“5”的预测距离）。这个算法两步就找到了最佳路径。
OK，如何定义问题和解决这个问题算法介绍完了，是不是很简单，你能分别利用上面介绍的两种算法在地图上找到从Arad城市到Bucharest的最短路径吗，能演示每一步怎么走的吗？
--------------
文章首发steemit.com 为了方便墙内阅读，搬运至此，欢迎留言或者访问我的Steemit主页
网友评论