水罐启发函数为A * [英] Water jugs heuristic function for A*

问题描述

有关的经典水壶搜索问题，甚至超过3水罐，这是可用于A一些受理功能*搜索算法

For the classic water jugs search problem, even for more than three jugs, which are some admissible functions that can be used for the A* search algorithm?

编辑：

我知道 http://www.dave-reed.com /csc550.S02/HW/HW4.html ，但此功能显然是不相符的。

I know about http://www.dave-reed.com/csc550.S02/HW/HW4.html , but that function clearly is not consistent.

推荐答案

有两种通用方法如何设计一种可行的启发式。 这两个工作通过解决一个简单的问题。启发式值则在简单的问题的目标的距离。

There are two general methods how to design an admissible heuristic. Both work by solving a simpler problem. The heuristic value is then the distance to the goal in the simpler problem.

问题是由忘记负面影响简化。 例如，如果你曾经有一个水夸脱，将在需要时始终可用。

The problem is simplified by forgetting negative effects. For example, if you once had one quart of water, it will be always available when needed.

教程规划基于图的可达性启发式。

的问题是通过忽略一些细节的简化。 例如，一个简单的目标可以忽略在结束最后一个罐子的水量。

The problem is simplified by ignoring some details. For example, a simpler goal could ignore the amount of water in the last jug at the end.

您可以存储在一个模式数据库pcomputed启发式值$ P $。关键的将是简单抽象的问题，该值将是启发价值。

You could store the precomputed heuristic values in a pattern database. The key would be the simpler abstract problem and the value would be the heuristic value.

正式出台。

这篇关于水罐启发函数为A *的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！