如何为这个深度优先搜索解决方案建模

Question

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

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

我有一个方法可以使用 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 可哈希。

Answer 2

在我看来，深度优先是错误的做法。如果你有一个状态，并且你知道从那个状态可以到达的所有状态，那么广度优先可能更合适。使用 BFS，您会知道第一个解决方案是最短的解决方案。

如果您确定有解决方案，那么您就不必担心无限递归，因为陷入循环的任何路径最终都不会是最短的，它们只会导致不必要的工作。

使用队列的迭代解决方案可行。

/** pseudocode **/
Queue q = new LinkedList();
q.put(myState)
while ( !q.isEmpty()) {
  State s = q.remove();
  if ( endState.equals(s)) {
    return something;
  }
  for ( State newState : s.getNextStates()) {
    q.add(newState);
  }
}

如果你确实想进行深度优先搜索，那么只需将队列更改为堆栈，但你将不得不处理循环。

如果您的队列项是一个包装器，其中包含到当前状态的路径，而不仅仅是当前状态，那么您可以轻松地到达最短路径（或至少是第一个）所遍历的深度和路径如果有多条相同深度的路线，则发现最短路线。）

如何为这个深度优先搜索解决方案建模

How to model this Depth First Search solution

java

search

artificial-intelligence

graph

depth-first-search