java - 如何实现贪心搜索算法

Question

我的人工智能类(class)中有一个项目。我需要为我的程序实现贪心搜索算法。我的项目描述是:给出了两个名为“tree.txt”和“heuristic.txt”的文本文件。 “tree.txt”将定义搜索树，其中每一行将包含父子关系和它们之间的路径成本。每个数据将以空格分隔。

例如

A B 5

A C 3

B D 6

第一行的第一个字符将是起始节点(此处为 A)，目标节点将为“G”。

“heuristic.txt”将定义启发式 h(n) 值。每行将包含每个节点的启发值。每个数据将以空格分隔。

例如

20

B 15

C 18

输出:程序应给出解的路径和从起始节点到目标节点的路径代价。

现在我的问题是我在理论上熟悉贪心搜索，但从未在编码中实际实现它。我真的不知道从哪里开始。我们可以自由地用任何语言开发我们的程序。大多数情况下，我精通 Java 和 C#。如果有人可以给我一些想法，或者帮助我提供任何类似的示例或教程。任何形式的帮助将不胜感激。抱歉写了这么多。提前谢谢你:)))

Answer 1

我建议使用 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})

getHeuristic python 函数 pass 接受一个状态作为参数，并返回该状态的启发式值。

要了解 python 的字典类，我建议您阅读 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) 是启发式函数的值。

要实现优先级队列，您应该使用标准库 heapq 的堆

节点是一个数据结构，必须包含四个组件:

node.state:节点对应的状态空间中的状态。

node.parent:生成该节点的搜索树中的节点。

node.action:应用于父节点以生成节点的操作。

node.pathCost:是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.parent 不为空，这就是您的解决方案。

我希望这对您的项目有用。