AI算法是一种重要的启发式算法,主要用于选择两点之间的最佳路径,A的实现也通过评估函数实现
  F=G + H
  G代表从这一点到起点的成本
  H是从此点到终点的曼哈顿距离。
  F是G和H的和,最佳路径是选择最小的F值并进行下一步(更多详细信息将在后面描述)
  曼哈顿距离
  Paste_Image.png
  上图中从熊到树叶的曼哈顿距离是由蓝线表示的距离,其中没有考虑障碍物。如果上图中每个框的长度为1,则此时熊的曼哈顿距离为9。
  开始(X1,Y1),结束(X2,Y2),H=| X2-X1 | + | Y2-Y1 |
  我们也可以通过几何坐标点来计算曼哈顿距离,或者以上图为例,左下角是(0,0)点,熊的位置是(1,4),树叶的位置是(7,1),则H=| 7-1 | + | 1-4 |=9。
  打开,关闭列表
  以上面的图片为例。例如,开始时,熊的位置将被添加到CLOSE列表中,熊可移动的点将被添加到OPEN列表中,熊周围的八个节点为F=G + An评估操作(例如H),然后在8个节点中选择F值最小的节点,然后从OPEN列表中删除该节点并将其添加到Close列表。从那时起,此节点8周围的每个节点都会执行评估操作,然后按顺序进行计算。因此,每个人可能都不太了解它。我将在下面详细解释。
  *算法示例
  Paste_Image.png
  从头到尾,我们使用A-star算法找到最佳路径
  Paste_Image.png
  我们将每个正方形的长度定义为1,则从起点到5位置的成本为1,从3到1.4的成本为1.41。定义好之后,我们来看上图,然后计算
  Paste_Image.png
  第一步,我们将起点周围的点添加到“打开”列表中,然后执行评估操作。计算结果如上所示。在这里,您会看到一个指向起点的小箭头。此箭头指向父节点,并且打开列表G值是基于此计算的,这意味着我需要从前一个父节点运行到此点的总成本。如果点不相同,则G值不同。经过计算,我们在上图中找到了1个点。 F值为7.41,这是最小的值,因此我们选择此点并从OPEN列表中删除1点,然后将其添加到CLOSE列表中,但是当我们下降时,我们发现大约1点,2点和3要点如何应对三个出发点。首先,起点已添加到CLOSE,并且他不需要执行此操作。这是CLOSE列表的作用,我们还可以在2和3处对他执行操作。对于点的计算,当我们从1点移动到2点时,他需要的价格是G值将变为2.41, H值不会改变。 F=2.41 + 7=9.41。这个算法主要用于智能写作,我们发现此值大于原始F值,我们无法将其更改(将父节点指向1,并将F值更改为9.41,因为我们一直在努力使F值最小化),并且相同适用于3分。
如果您有互联网问题,也可以咨询我,谢谢!如果你也想一起学习人工智能,欢迎留言交流。


评论关闭
IT干货网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!