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

6 为了避免无限循环，在串行版本中引入了一个Set对象，其中保存了之前已经搜索过的所有位置。在ConcurrentPuzzleSolver中使用ConcurrentHashMap来实现相同的功能。这种做法不仅提供了线程安全性，还避免了在更新共享集合时存在的竞态条件。 ConcurrentPuzzleSolver中使用了一个内部类SolverTask，这个类扩展了PuzzleNode并实现了Runnable。大多数工作都是在run中完成的：首先计算下一步可能到达的所有位置，并去掉已经到达的位置，然后判断（这个任务或者其他某个任务）是否已经成功完成，最后将尚未搜索过的位置提交给Executor。

7 public class ConcurrentPuzzleSolver<P, M> {
private final Puzzle<P, M> puzzle; private final ExecutorService exec; private final ConcurrentMap<P, Boolean> seen; protected final ValueLatch<PuzzleNode<P, M>> solution = new ValueLatch<PuzzleNode<P, M>>(); public ConcurrentPuzzleSolver(Puzzle<P, M> puzzle) { this.puzzle = puzzle; this.exec = initThreadPool(); this.seen = new ConcurrentHashMap<P, Boolean>(); if (exec instanceof ThreadPoolExecutor) { ThreadPoolExecutor tpe = (ThreadPoolExecutor) exec; tpe.setRejectedExecutionHandler(new ThreadPoolExecutor.DiscardPolicy()); } private ExecutorService initThreadPool() { return Executors.newCachedThreadPool();

8 public List<M> solve() throws InterruptedException {
try { P p = puzzle.initialPosition(); exec.execute(newTask(p, null, null)); // block until solution found PuzzleNode<P, M> solnPuzzleNode = solution.getValue(); return (solnPuzzleNode == null) ? null : solnPuzzleNode.asMoveList(); } finally { exec.shutdown(); } protected Runnable newTask(P p, M m, PuzzleNode<P, M> n) { return new SolverTask(p, m, n); protected class SolverTask extends PuzzleNode<P, M> implements Runnable { SolverTask(P pos, M move, PuzzleNode<P, M> prev) { super(pos, move, prev);

9 public void run() { if (solution.isSet() || seen.putIfAbsent(pos, true) != null) return; // already solved or seen this position if (puzzle.isGoal(pos)) solution.setValue(this); else for (M m : puzzle.legalMoves(pos)) exec.execute(newTask(puzzle.move(pos, m), m, this)); } 并发方法引入了一种新形式的限制并去掉了一种原有的限制，新的限制在这个问题域中更合适。串行版本的程序执行深度优先搜索，因此搜索过程将受限于栈的大小。并发版本程序执行广度优先搜索，因此不会受到栈大小的限制。 如果不存在解答，那么ConcurrentPuzzleSolver就会永远的等待下去，getSolution一直阻塞下去。 通过记录活动任务数量，当该值为零时将解答设置为null，如下：

10 public class PuzzleSolver<P, M> extends ConcurrentPuzzleSolver<P, M> {
PuzzleSolver(Puzzle<P, M> puzzle) { super(puzzle); } private final AtomicInteger taskCount = new AtomicInteger(0); protected Runnable newTask(P p, M m, PuzzleNode<P, M> n) { return new CountingSolverTask(p, m, n); class CountingSolverTask extends SolverTask { CountingSolverTask(P pos, M move, PuzzleNode<P, M> prev) { super(pos, move, prev); taskCount.incrementAndGet(); public void run() { try { super.run(); } finally { if (taskCount.decrementAndGet() == 0) solution.setValue(null);