- Поиск путей Java в общих деревьях. Часть 1/4: классы моделей
- Поиск путей Java в общих деревьях — Часть 2/4: алгоритмы (этот пост)
- Поиск пути Java в общих деревьях — часть 3/4: демонстрация
- Поиск пути Java в общих деревьях — часть 4/4: модульные тесты
В этом посте я представлю алгоритмы поиска пути:
com.github.coderodde.pathfinding.BidirectionalBreadthFirstSearchPathfinder.java:
package com.github.coderodde.pathfinding;
import com.github.coderodde.pathfinding.WeightedTree.WeightedTreeNode;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
/**
* This class implements a bidirectional breadth-first search. It alternates
* two search frontiers meeting somewhere in between.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Nov 6, 2022)
* @since 1.6 (Nov 6, 2022)
*/
public final class BidirectionalBreadthFirstSearchPathfinder
implements Pathfinder {
@Override
public WeightedPath search(WeightedTree tree, int sourceNodeId, int targetNodeId) {
Objects.requireNonNull(tree, "The tree is null.");
checkTerminalNodes(tree, sourceNodeId, targetNodeId);
WeightedTree.WeightedTreeNode sourceNode =
tree.getWeightedTreeNode(sourceNodeId);
WeightedTree.WeightedTreeNode targetNode =
tree.getWeightedTreeNode(targetNodeId);
if (sourceNode.equals(targetNode)) {
// We need to deal with this special case separately since the
// algorithm logic cannot handle it:
return new WeightedPath(tree, Arrays.asList(sourceNode));
}
Deque<WeightedTreeNode> queueForward = new ArrayDeque<>();
Deque<WeightedTreeNode> queueBackward = new ArrayDeque<>();
Map<WeightedTreeNode, WeightedTreeNode> parentMapForward =
new HashMap<>();
Map<WeightedTreeNode, WeightedTreeNode> parentMapBackward =
new HashMap<>();
Map<WeightedTreeNode, Integer> distanceMapForward =
new HashMap<>();
Map<WeightedTreeNode, Integer> distanceMapBackward =
new HashMap<>();
int bestCost = Integer.MAX_VALUE;
WeightedTreeNode touchNode = null;
queueForward.addLast(sourceNode);
queueBackward.addLast(targetNode);
parentMapForward.put(sourceNode, null);
parentMapBackward.put(targetNode, null);
distanceMapForward.put(sourceNode, 0);
distanceMapBackward.put(targetNode, 0);
while (!queueForward.isEmpty() && !queueBackward.isEmpty()) {
int distanceForward =
distanceMapForward.get(queueForward.getFirst());
int distanceBackward =
distanceMapBackward.get(queueBackward.getFirst());
if (touchNode != null
&& bestCost < distanceForward + distanceBackward) {
return tracebackPath(tree,
touchNode,
parentMapForward,
parentMapBackward);
}
int forwardSearchAreaSize = queueForward.size()
+ parentMapForward.size();
int backwardSearchAreaSize = queueBackward.size()
+ parentMapBackward.size();
// Trivial load balancing:
if (forwardSearchAreaSize < backwardSearchAreaSize) {
WeightedTreeNode currentNode = queueForward.removeFirst();
if (distanceMapBackward.containsKey(currentNode)
&& bestCost > distanceForward + distanceBackward) {
bestCost = distanceForward + distanceBackward;
touchNode = currentNode;
}
for (WeightedTreeNode neighbor : currentNode.getNeighbors()) {
if (!parentMapForward.containsKey(neighbor)) {
parentMapForward.put(neighbor, currentNode);
distanceMapForward.put(neighbor,
distanceMapForward.get(
currentNode) + 1);
queueForward.addLast(neighbor);
}
}
} else {
WeightedTreeNode currentNode = queueBackward.removeFirst();
if (distanceMapForward.containsKey(currentNode)
&& bestCost > distanceForward + distanceBackward) {
bestCost = distanceForward + distanceBackward;
touchNode = currentNode;
}
for (WeightedTreeNode neighbor : currentNode.getNeighbors()) {
if (!parentMapBackward.containsKey(neighbor)) {
parentMapBackward.put(neighbor, currentNode);
distanceMapBackward.put(neighbor,
distanceMapBackward.get(
currentNode) + 1);
queueBackward.addLast(neighbor);
}
}
}
}
throw new PathNotFoundException(sourceNodeId, targetNodeId);
}
}
com.github.coderodde.pathfinding.BidirectionalIterativeDeepeningDepthFirstSearchPathfinder.java:
package com.github.coderodde.pathfinding;
import com.github.coderodde.pathfinding.WeightedTree.WeightedTreeNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;
/**
* This class implements a bidirectional iterative-deepening depth-first search
* (IDDFS for short). It alternates two search frontiers meeting somewhere in
* between.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Nov 6, 2022)
* @since 1.6 (Nov 6, 2022)
*/
public final class BidirectionalIterativeDeepeningDepthFirstSearchPathfinder
implements Pathfinder {
private final int maximumDepth;
public BidirectionalIterativeDeepeningDepthFirstSearchPathfinder(
int maximumDepth) {
this.maximumDepth = checkMaximumDepth(maximumDepth);
}
public BidirectionalIterativeDeepeningDepthFirstSearchPathfinder() {
this(Integer.MAX_VALUE);
}
@Override
public WeightedPath search(WeightedTree tree,
int sourceNodeId,
int targetNodeId) {
Objects.requireNonNull(tree, "The tree is null.");
checkTerminalNodes(tree, sourceNodeId, targetNodeId);
WeightedTreeNode sourceNode = tree.getWeightedTreeNode(sourceNodeId);
WeightedTreeNode targetNode = tree.getWeightedTreeNode(targetNodeId);
List<WeightedTreeNode> path = searchImpl(tree,
sourceNode,
targetNode);
return new WeightedPath(tree, path);
}
private void depthLimitedSearchForwards(WeightedTreeNode node,
int depth,
Set<WeightedTreeNode> frontier,
Set<WeightedTreeNode> visited) {
if (depth == 0) {
frontier.add(node);
return;
}
for (WeightedTreeNode neighbor : node.getNeighbors()) {
if (visited.contains(neighbor)) {
continue;
}
visited.add(neighbor);
depthLimitedSearchForwards(neighbor,
depth - 1,
frontier,
visited);
}
}
private WeightedTreeNode
depthLimitedSearchBackward(
WeightedTreeNode node,
int depth,
Set<WeightedTreeNode> frontier,
Set<WeightedTreeNode> visited,
Deque<WeightedTreeNode> backwardSearchStack) {
backwardSearchStack.addFirst(node);
if (depth == 0) {
if (frontier.contains(node)) {
return node;
}
backwardSearchStack.removeFirst();
return null;
}
for (WeightedTreeNode neighbor : node.getNeighbors()) {
if (visited.contains(neighbor)) {
continue;
}
visited.add(neighbor);
WeightedTreeNode meetingNode =
depthLimitedSearchBackward(
neighbor,
depth - 1,
frontier,
visited,
backwardSearchStack);
if (meetingNode != null) {
return meetingNode;
}
}
backwardSearchStack.removeFirst();
return null;
}
private List<WeightedTreeNode> searchImpl(WeightedTree tree,
WeightedTreeNode sourceNode,
WeightedTreeNode targetNode) {
if (sourceNode.equals(targetNode)) {
return Arrays.asList(sourceNode);
}
int totalForwardDepth = maximumDepth / 2;
int totalBackwardDepth = maximumDepth - totalForwardDepth;
int currentForwardDepth = 0;
int currentBackwardDepth = 0;
boolean incrementForwardSearchDepth = true;
Deque<WeightedTreeNode> backwardSearchStack = new ArrayDeque<>();
Set<WeightedTreeNode> frontier = new HashSet<>();
Set<WeightedTreeNode> visited = new HashSet<>();
while (currentForwardDepth + currentBackwardDepth <= maximumDepth) {
visited.clear();
visited.add(sourceNode);
depthLimitedSearchForwards(sourceNode,
currentForwardDepth,
frontier,
visited);
for (int depth = currentBackwardDepth;
depth <= Math.min(currentBackwardDepth + 1,
totalBackwardDepth);
depth++) {
visited.clear();
visited.add(targetNode);
WeightedTreeNode meetingNode =
depthLimitedSearchBackward(targetNode,
depth,
frontier,
visited,
backwardSearchStack);
if (meetingNode != null) {
return buildPath(tree,
meetingNode,
sourceNode,
backwardSearchStack);
}
}
frontier.clear();
backwardSearchStack.clear();
if (incrementForwardSearchDepth) {
incrementForwardSearchDepth = false;
currentForwardDepth++;
} else {
incrementForwardSearchDepth = true;
currentBackwardDepth++;
}
}
throw new PathNotFoundException(sourceNode.getId(), targetNode.getId());
}
private List<WeightedTreeNode>
buildPath(WeightedTree tree,
WeightedTreeNode meetingNode,
WeightedTreeNode sourceNode,
Deque<WeightedTreeNode> backwardSearchStack) {
List<WeightedTreeNode> path = new ArrayList<>();
List<WeightedTreeNode> prefixPath =
searchImpl(tree,
sourceNode,
meetingNode);
path.addAll(prefixPath);
path.remove(path.size() - 1);
path.addAll(backwardSearchStack);
return path;
}
private int checkMaximumDepth(int depth) {
if (depth < 0) {
throw new IllegalArgumentException(
"The depth is negative: "
+ depth
+ ". Must be at least 0.");
}
return depth;
}
}
com.github.coderodde.pathfinding.BreadthFirstSearchPathfinder.java:
package com.github.coderodde.pathfinding;
import com.github.coderodde.pathfinding.WeightedTree.WeightedTreeNode;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
/**
* This class implements the breadth-first search.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Nov 5, 2022)
* @since 1.6 (Nov 5, 2022)
*/
public final class BreadthFirstSearchPathfinder implements Pathfinder {
@Override
public WeightedPath search(WeightedTree tree,
int sourceNodeId,
int targetNodeId) {
Objects.requireNonNull(tree, "The tree is null.");
checkTerminalNodes(tree, sourceNodeId, targetNodeId);
WeightedTreeNode sourceNode = tree.getWeightedTreeNode(sourceNodeId);
WeightedTreeNode targetNode = tree.getWeightedTreeNode(targetNodeId);
Deque<WeightedTreeNode> deque = new ArrayDeque<>();
Map<WeightedTreeNode, WeightedTreeNode> parentMap = new HashMap<>();
deque.add(sourceNode);
parentMap.put(sourceNode, null);
while (!deque.isEmpty()) {
WeightedTreeNode currentNode = deque.removeFirst();
if (currentNode.equals(targetNode)) {
return tracebackPath(tree, targetNode, parentMap);
}
for (WeightedTreeNode neighborNode :
tree.getNeighbors(currentNode.getId())) {
if (parentMap.containsKey(neighborNode)) {
continue;
}
parentMap.put(neighborNode, currentNode);
deque.addLast(neighborNode);
}
}
throw new PathNotFoundException(sourceNodeId, targetNodeId);
}
}
com.github.coderodde.pathfinding.DepthFirstSearchPathfinder.java:
package com.github.coderodde.pathfinding;
import com.github.coderodde.pathfinding.WeightedTree.WeightedTreeNode;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
/**
* This class implements a depth-first search.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Nov 6, 2022)
* @since 1.6 (Nov 6, 2022)
*/
public class DepthFirstSearchPathfinder implements Pathfinder {
@Override
public WeightedPath search(WeightedTree tree,
int sourceNodeId,
int targetNodeId) {
Objects.requireNonNull(tree, "The tree is null.");
checkTerminalNodes(tree, sourceNodeId, targetNodeId);
WeightedTreeNode sourceNode = tree.getWeightedTreeNode(sourceNodeId);
WeightedTreeNode targetNode = tree.getWeightedTreeNode(targetNodeId);
Map<WeightedTreeNode, WeightedTreeNode> parentMap = new HashMap<>();
parentMap.put(sourceNode, null);
if (sourceNode.equals(targetNode)) {
// Handle the trvial case separately, since it is not covered by
// algorithm logic:
return tracebackPath(tree, targetNode, parentMap);
}
for (WeightedTreeNode neighbor : sourceNode.getNeighbors()) {
WeightedPath path = searchImpl(tree,
targetNode,
sourceNode,
neighbor,
parentMap);
if (path != null) {
return path;
}
}
throw new PathNotFoundException(sourceNodeId, targetNodeId);
}
private WeightedPath searchImpl(WeightedTree tree,
WeightedTreeNode targetNode,
WeightedTreeNode parentNode,
WeightedTreeNode node,
Map<WeightedTreeNode,
WeightedTreeNode> parentMap) {
parentMap.put(node, parentNode);
if (node.equals(targetNode)) {
return tracebackPath(tree, targetNode, parentMap);
}
for (WeightedTreeNode neighbor : node.getNeighbors()) {
if (parentMap.containsKey(neighbor)) {
continue;
}
WeightedPath path = searchImpl(tree,
targetNode,
node,
neighbor,
parentMap);
if (path != null) {
return path;
}
}
return null;
}
}
com.github.coderodde.pathfinding.IterativeDeepeningDepthFirstSearchPathfinder.java:
package com.github.coderodde.pathfinding;
import com.github.coderodde.pathfinding.WeightedTree.WeightedTreeNode;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
/**
* This class implements a bidirectional breadth-first search. It alternates
* two search frontiers meeting somewhere in between.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Nov 6, 2022)
* @since 1.6 (Nov 6, 2022)
*/
public final class IterativeDeepeningDepthFirstSearchPathfinder
implements Pathfinder {
private final int maximumDepth;
public IterativeDeepeningDepthFirstSearchPathfinder(int maximumDepth) {
this.maximumDepth = checkMaximumDepth(maximumDepth);
}
public IterativeDeepeningDepthFirstSearchPathfinder() {
this(Integer.MAX_VALUE);
}
@Override
public WeightedPath search(WeightedTree tree,
int sourceNodeId,
int targetNodeId) {
Objects.requireNonNull(tree, "The tree is null.");
checkTerminalNodes(tree, sourceNodeId, targetNodeId);
WeightedTreeNode sourceNode = tree.getWeightedTreeNode(sourceNodeId);
WeightedTreeNode targetNode = tree.getWeightedTreeNode(targetNodeId);
Map<WeightedTreeNode, WeightedTreeNode> parentMap = new HashMap<>();
if (sourceNode.equals(targetNode)) {
parentMap.put(sourceNode, null);
return tracebackPath(tree, targetNode, parentMap);
}
for (int depth = 0; depth <= maximumDepth; depth++) {
parentMap.clear();
parentMap.put(sourceNode, null);
WeightedTreeNode found = depthLimitedSearch(sourceNode,
targetNode,
depth,
parentMap);
if (found != null) {
return tracebackPath(tree, targetNode, parentMap);
}
}
throw new PathNotFoundException(sourceNodeId, targetNodeId);
}
private WeightedTreeNode
depthLimitedSearch(WeightedTreeNode node,
WeightedTreeNode targetNode,
int depth,
Map<WeightedTreeNode,
WeightedTreeNode> parentMap) {
if (depth == 0) {
return node.equals(targetNode) ? targetNode : null;
}
for (WeightedTreeNode neighbor : node.getNeighbors()) {
if (parentMap.containsKey(neighbor)) {
continue;
}
parentMap.put(neighbor, node);
WeightedTreeNode found = depthLimitedSearch(neighbor,
targetNode,
depth - 1,
parentMap);
if (found != null) {
return found;
}
}
return null;
}
private int checkMaximumDepth(int depth) {
if (depth < 0) {
throw new IllegalArgumentException(
"The depth is negative: "
+ depth
+ ". Must be at least 0.");
}
return depth;
}
}
com.github.coderodde.pathfinding.PathNotFoundException.java:
package com.github.coderodde.pathfinding;
public final class PathNotFoundException extends RuntimeException {
public PathNotFoundException(int sourceId, int targetId) {
super("Path not found from " + sourceId + " to " + targetId + ".");
}
}
Запрос критики
Как всегда, пожалуйста, расскажите мне все, что приходит на ум.
кодродде