java 贪婪搜索算法的实现

我有一个项目，是对我的人工智能课程。我需要实现贪婪搜索算法为我的程序。我的项目描述是：给出了两个文本文件“tree.txt”和“heuristic.txt”。“tree.txt”将定义搜索树，其中每一行将包含父子关系和它们之间的路径成本。每个数据将用空格分隔。
例如：
阿、B 5
阿中3
B D 6
第一行的第一个字符将是开始节点（这里是A），目标节点将是“G”。
“heuristic.txt”将定义启发式h（n）值。每行将包含每个节点的启发式值。每个数据将用空格分隔。
例如：
阿20
B十五
丙十八
输出：程序应该给予从开始节点到目标的解路径和路径成本。
现在我的问题是，我熟悉贪婪搜索理论，但从来没有实现它的实际编码。我真的不知道从哪里开始。我们可以自由地开发我们的程序在任何语言。主要是，我有技能在Java和C#。如果有人能给予我一些想法，或帮助我与任何类似的例子或教程。任何形式的帮助将不胜感激。抱歉写了这么多。提前感谢：）））

我建议使用python来实现这个解决方案。在你的程序中使用一个简单的python字典来实现这个图形。下面是代码：

class Tree:

     def _init_(self,dict,heuristic):
     self.tree=tree
     self.heuristic=heuristic


     def getHeuristicValue(self,state)
     value=self.heuristic.get(state)
     return value

构造函数调用类似于：

g = Graph({'A':{'B':5,'C':3},'B':{'D':6}},{'A':20,'B':15,'C':18})

getHeuristicpython函数pass接受一个状态作为参数，并返回该状态的启发式值。
要了解python的dictionary类，我建议您阅读the tutorial
要用python实现搜索算法，你应该实现下面这个简单的伪代码：

function Tree-Search(initialNode,goalNode) returns a solution,or failure
frontier.push(initialNode) with the value of the function heuristic(initialNode.state)+the path cost to reaxh this node
while(frontier)
  node<-frontier.pop()
  if node.state==GoalNode.state
    return node
  expand node, adding the resulting nodes to the frontier
return None

对于边界，您必须使用优先级队列，因为您必须弹出具有较低值g(n)+h(n)的节点（其中g(n)是到达此节点的路径成本，h(n)是启发式函数的值）。
要实现优先级队列，您应该使用标准库堆的heap
节点是必须包含四个组件的数据结构：

node.state：节点对应的状态空间中的状态。
node.parent：搜索树中生成此节点的节点。
节点.操作：应用于父节点以生成节点的操作。
节点路径开销：是g（n），从初始状态到节点的路径的成本。

最后，要展开节点，可以使用以下python函数：

def actions(self,state):
    '''return a tuple that contain the state child of state '''
    return tuple(self.tree.get(state))

我建议您查找this来解决您的问题。
你可以简单地从node.state返回得到解，node.state是从算法的输出返回的，而node.parent不为空，这就是你的解。
我希望这对你的项目有用。

java 贪婪搜索算法的实现

1条答案

相关问题

热门标签

最新问答