如何模拟这个深度第一搜索解决方案

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

我是否应该建立这个图表，因为我发现了我目前所处状态的所有可能状态？但是，这不会破坏目的 - 首先用各种可能的状态构建图表，然后搜索整个图表以找出解决方案？

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

来源

2015-10-12 Brejuro

您不必显式构建图形。在概念上，您可以将问题表示为图形，其中节点是状态，边是状态之间的转换。深度优先搜索是一直跟随边缘，直到达到最终状态，然后再移动到另一边。所以它看起来是这样的（伪）：

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哈希的。

来源

2015-10-12 17:44:05 Claudiu

因此，基本上这只会搜索一条路径，然后倒带，直到找到解决方案？我如何判断当前状态中是否存在可能的状态之一？我的意思是，如果我将棋子移位得足够多，我会得到重复的状态，并且会永久循环。 – Brejuro

@Brejuro：查看更新。你只需要跟踪已经看到的状态，如果你已经看到它，就不要去那里。通过保持一套。 – Claudiu

感谢您的帮助，将它作为图形进行建模是否合理？就像我在添加节点和边缘一样？我计划也实现其他搜索算法，所以我不确定使用图形实现是否有用。 – Brejuro

听起来像深度先是我的错误方式。如果你有一个国家，并且你知道你可以从那个国家得到的所有国家，那么首先宽度可能会更合适。有了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); 
    } 
}

如果你想要去的深度优先搜索，然后只需将队列更改为一个堆栈，但那么你将不得不应对周期。

如果您的队列项目是一个包含当前状态路径而不仅仅是当前状态的包装，那么您可以轻松到达为最短路径穿过的深度和路径（或者至少第一最短路径如果存在多条相同深度的路线，则会发现路线。）

来源

2015-10-12 20:12:54 digitaljoel

如何模拟这个深度第一搜索解决方案

回答

相关问题