suppose that we have an 8 puzzle problem, and the empty tile is marked by ZERO. The goal state is :
假设我们有一个8个谜题，空的瓷砖是0。目标状态是:
- 1 2 3
- 1 2 3
- 4 5 6
- 4 5 6
- 7 8 0
- 7 8 0
the initial state is:
初始状态是:
- 0 1 3
- 0 1 3
- 8 2 4
- 8 2 4
- 7 6 5
- 7 6 5
... my question is, is it possible for a child in an A* tree to "copy" or have the same state of its ancestor(s)? or will "f(n) = g(h) + h(n)" [where g(h) = # of moves made... h(n) = sum of manhattan distances of each tile] already make this impossible and therefore i don't need to worry about this?.. for example, from the initial state:
…我的问题是，一个孩子是否可以“复制”或拥有相同的祖先的状态?或者f(n) = g(h) + h(n)[g(h) = # of move made…h(n) =每瓦的曼哈顿距离的总和]已经使这个不可能，因此我不需要担心这个?。例如，从初始状态:
- 0 1 3
- 0 1 3
- 8 2 4
- 8 2 4
- 7 6 5
- 7 6 5
then the following states happen, thus making more child nodes in the A* tree
然后发生下列状态，从而在A*树中生成更多的子节点。
(action: up)
(动作:)
- 8 1 3
- 8 1 3
- 0 2 4
- 0 2 4
- 7 6 5
- 7 6 5
action: left
行动:左
- 8 1 3
- 8 1 3
- 2 0 4
- 2 0 4
- 7 6 5
- 7 6 5
action: down
行动:下来
- 8 0 3
- 8 0 3
- 2 1 4
- 2 1 4
- 7 6 5
- 7 6 5
action: right
行动:对
- 0 8 3
- 0 8 3
- 2 1 4
- 2 1 4
- 7 6 5
- 7 6 5
action: up
行动:
- 2 8 3
- 2 8 3
- 0 1 4
- 0 1 4
- 7 6 5
- 7 6 5
... then actions: left, down, right, up, left, down, right happens... thus leaving the state back to that of the initial state:
…然后动作:左、下、右、上、左、下、右……从而使国家回到最初的状态:
- 0 1 3
- 0 1 3
- 8 2 4
- 8 2 4
- 7 6 5
- 7 6 5
is this possible in an A* search of an 8 puzzle? or will f(n) take care of this problem? thanks to those who will answer, any help would be appreciated!
这可能在一个8字谜的搜索中吗?还是f(n)处理这个问题?感谢那些愿意回答的人，任何帮助都将被感激!
1 个解决方案
#1
0
You do not have to worry about the situation you are describing in your question. The beginning state is expanded in the first iteration of A*, which leads the algorithm to include that node in the CLOSED list with an associated cost (which is zero, as it is the initial state). If you find that state again as successor of any other state, the algorithm will find that state in the CLOSED list with a lower cost and it will not be expanded again, discarding that branch in the search tree.
你不必担心你的问题所描述的情况。初始状态在*的第一次迭代中得到扩展，它导致算法将该节点包含在已关闭的列表中，并带有相关的成本(这是初始状态)。如果您再次发现该状态作为任何其他状态的继承，该算法将在关闭的列表中找到一个较低成本的状态，并且它将不再被扩展，在搜索树中丢弃该分支。
If you are going to implement this problem in Java, maybe you will find useful to use an heuristic search library like Hipster. This library is open-source (see at Github) and has some examples of search problems solved with it. Including the 8-puzzle problem solved with A*.
如果您打算在Java中实现这个问题，也许您会发现使用像Hipster这样的启发式搜索库很有用。这个库是开源的(参见Github)，并有一些搜索问题的例子。包括用*解决的8字谜问题。
I hope my answer helps,
我希望我的回答能有所帮助，
#1
0
You do not have to worry about the situation you are describing in your question. The beginning state is expanded in the first iteration of A*, which leads the algorithm to include that node in the CLOSED list with an associated cost (which is zero, as it is the initial state). If you find that state again as successor of any other state, the algorithm will find that state in the CLOSED list with a lower cost and it will not be expanded again, discarding that branch in the search tree.
你不必担心你的问题所描述的情况。初始状态在*的第一次迭代中得到扩展，它导致算法将该节点包含在已关闭的列表中，并带有相关的成本(这是初始状态)。如果您再次发现该状态作为任何其他状态的继承，该算法将在关闭的列表中找到一个较低成本的状态，并且它将不再被扩展，在搜索树中丢弃该分支。
If you are going to implement this problem in Java, maybe you will find useful to use an heuristic search library like Hipster. This library is open-source (see at Github) and has some examples of search problems solved with it. Including the 8-puzzle problem solved with A*.
如果您打算在Java中实现这个问题，也许您会发现使用像Hipster这样的启发式搜索库很有用。这个库是开源的(参见Github)，并有一些搜索问题的例子。包括用*解决的8字谜问题。
I hope my answer helps,
我希望我的回答能有所帮助，