第四次课后作业 1 问题描述： 将谜题定义为：包含一个初始位置，一个目标位置，以及用于判断是否是有效移动的规则集。

Presentation on theme: "第四次课后作业 1 问题描述： 将谜题定义为：包含一个初始位置，一个目标位置，以及用于判断是否是有效移动的规则集。"— Presentation transcript:

1 第四次课后作业 1 问题描述： 将谜题定义为：包含一个初始位置，一个目标位置，以及用于判断是否是有效移动的规则集。
规则集包含两部分：计算从指定位置开始的所有合法移动，以及每次移动的结果位置。 给出表示谜题的抽象类，其中的类型参数P和M表示位置类和移动类。 public interface Puzzle<P, M> { P initialPosition(); boolean isGoal(P position); Set<M> legalMoves(P position); P move(P position, M move); }

2 Node代表通过一系列的移动到达的一个位置，其中保存了到达该位置的移动以及前一个Node。只要沿着Node链接逐步回溯，就可以重新构建出达到当前位置的移动序列。
@Immutable static class Node<P, M> { final P pos; final M move; final Node<P, M> prev; Node(P pos, M move, Node<P, M> prev) { this.pos = pos; this.move = move; this.prev = prev; } List<M> asMoveList() { List<M> solution = new LinkedList<M>(); for (Node<P, M> n = this; n.move != null; n = n.prev) solution.add(0, n.move); return solution;

3 给出谜题框架的串行解决方案SequentialPuzzleSolver，它在谜题空间中执行深度优先搜索，当找到解答方案（不一定是最短的解决方案）后结束搜索。
public class SequentialPuzzleSolver<P, M> { private final Puzzle<P, M> puzzle; private final Set<P> seen = new HashSet<P>(); public SequentialPuzzleSolver(Puzzle<P, M> puzzle) { this.puzzle = puzzle; } public List<M> solve() { P pos = puzzle.initialPosition(); return search(new PuzzleNode<P, M>(pos, null, null));

4 private List<M> search(PuzzleNode<P, M> node) {
if (!seen.contains(node.pos)) { seen.add(node.pos); if (puzzle.isGoal(node.pos)) return node.asMoveList(); for (M move : puzzle.legalMoves(node.pos)) { P pos = puzzle.move(node.pos, move); PuzzleNode<P, M> child = new PuzzleNode<P, M>(pos, move, node); List<M> result = search(child); if (result != null) return result; } return null;

5 2 作业要求： 利用并发性修改解决方案，将给出的串行方案修改为并行，可以以并行方式来计算下一步移动以及目标条件，因为计算某次移动的过程在很大程度上与计算其他移动的过程是相互独立的。