java - 如何建模此深度优先搜索解决方案

Question

我有一个益智游戏，它的状态取决于拼图中各个部分的排列。我正在尝试使用深度优先搜索来解决这个难题，但是我对如何解决它感到困惑。根据我的理解，深度优先搜索将搜索图形来找到解决方案，但我的难题不是图形形式。我所知道的只是当前状态以及从该状态可以实现的状态。

当我从我当前所处的状态发现所有可能的状态时，我是否应该构建这个图表？但这不是违背了目的吗 - 首先构建一个包含每种可能状态的图，然后在整个图中搜索解决方案？

我有一个方法，可以使用 Move 从当前状态探索所有可能的状态，我确信它会派上用场，除非我不知道如何使用它.

Answer 1

您不必显式构建图表。从概念上讲，您可以将问题表示为图形，其中节点是状态，边是状态之间的转换。深度优先搜索是一直跟踪一条边，直到达到结束状态，然后再移动到另一条边。所以它看起来像这样(伪代码):

def search(state):
    if is_end_state(state):
        # search down this branch finished, do something
        return something

    for move in possible_moves_from(state):
        search(apply_move(state, move))

您最终会通过递归调用和堆栈状态隐式构建图表。

请注意，如果您有循环(例如，您可以向左移动，然后向右移动以返回到完全相同的状态)，那么您将必须跟踪已经访问过的状态，否则您将永远循环。像这样的事情:

def search(state, seen_states):
    if state in seen_states:
        # already visited, don't visit again
        return 

    seen_states.add(state)

    # same as before:      
    if is_end_state(state):
        return something

    for move in possible_moves_from(state):
        search(apply_move(state, move), seen_states)

关于如何实现这一点，我建议您有seen_states是 HashSet<State>你让你的State可散列。