Как сделать поиск пучка стека оптимальным и полным ⇐ JAVA

[Anonymous]

Я читал Поиск из пучка бумаги: интеграция обратной связи с поиском луча Ронг Чжоу и Эрика А. Хансена и я пытались реализовать его в Java (см. Репозиторие Pathfinding.java в Github, страница Readme дает инструкцию при запуске приложения). Мой код заключается в следующем: < /p>
package io.github.coderodde.pathfinding.finders;

import static io.github.coderodde.pathfinding.finders.Finder.searchSleep;
import io.github.coderodde.pathfinding.heuristics.HeuristicFunction;
import io.github.coderodde.pathfinding.logic.GridCellNeighbourIterable;
import io.github.coderodde.pathfinding.logic.PathfindingSettings;
import io.github.coderodde.pathfinding.logic.SearchState;
import io.github.coderodde.pathfinding.logic.SearchStatistics;
import io.github.coderodde.pathfinding.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import io.github.coderodde.pathfinding.utils.CellType;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

/**
*
* @author Rodion "rodde" Efremov
* @version 1.0.0 (Sep 15, 2025)
* @since 1.0.0 (Sep 15, 2025)
*/
public final class BeamStackSearchFinder implements Finder {

@Override
public List findPath(GridModel model,
GridCellNeighbourIterable neighbourIterable,
PathfindingSettings pathfindingSettings,
SearchState searchState,
SearchStatistics searchStatistics) {

Deque beamStack = new ArrayDeque();
beamStack.push(new BeamStackEntry(0.0, Double.POSITIVE_INFINITY));

List optimalPath = null;
DoubleHolder U = new DoubleHolder();
U.value = Double.POSITIVE_INFINITY;

while (!beamStack.isEmpty()) {
List path;
System.out.println("hello");

try {
path = search(model,
U,
beamStack,
neighbourIterable,
pathfindingSettings,
searchState,
searchStatistics);

} catch (HaltRequestedException ex) {
return List.of();
}

if (searchState.haltRequested()) {
return List.of();
}

while (searchState.pauseRequested()) {
searchSleep(pathfindingSettings);
System.out.println("yes 1");
if (searchState.haltRequested()) {
return List.of();
}
}

if (path != null) {
optimalPath = path;
U.value = getPathCost(path, pathfindingSettings);
}

while (!beamStack.isEmpty() && beamStack.peek().fmax >= U.value) {
beamStack.pop();
}

if (beamStack.isEmpty()) {
return optimalPath == null ? List.of() : optimalPath;
}

BeamStackEntry top = beamStack.peek();
top.fmin = top.fmax;
top.fmax = U.value;
}

throw new IllegalStateException("Should not get here ever");
}

private static double
getPathCost(List path,
PathfindingSettings pathsPathfindingSettings) {

double cost = 0.0;

for (int i = 0; i < path.size() - 1; ++i) {
Cell c1 = path.get(i);
Cell c2 = path.get(i + 1);
cost += pathsPathfindingSettings.getWeight(c1, c2);
}

return cost;
}

private static List search(GridModel model,
DoubleHolder U,
Deque beamStack,
GridCellNeighbourIterable iterable,
PathfindingSettings pathfindingSettings,
SearchState searchState,
SearchStatistics searchStatistics) {

Map open = new HashMap();
Map closed = new HashMap();
Map g = new HashMap();
Map p = new HashMap();

HeuristicFunction h = pathfindingSettings.getHeuristicFunction();
Cell source = model.getSourceGridCell();
Cell target = model.getTargetGridCell();

Cell bestGoal = null;
int layerIndex = 0;

open.put(0, new PriorityQueue());
open.put(1, new PriorityQueue());
open.get(0).add(new HeapNode(source, 0.0));

closed.put(0, new HashSet());
g.put(source, 0.0);
p.put(source, null);

searchStatistics.incrementOpened();

while (!open.get(layerIndex).isEmpty() ||
!open.get(layerIndex + 1).isEmpty()) {

while (!open.get(layerIndex).isEmpty()) {

if (searchState.haltRequested()) {
throw new HaltRequestedException();
}

while (searchState.pauseRequested()) {
searchSleep(pathfindingSettings);
System.out.println("yes 2");
if (searchState.haltRequested()) {
throw new HaltRequestedException();
}
}

Cell cell = open.get(layerIndex).remove().cell;
closed.get(layerIndex).add(cell);
searchStatistics.decrementOpened();
searchStatistics.incrementVisited();

if (!cell.getCellType().equals(CellType.SOURCE) &&
!cell.getCellType().equals(CellType.TARGET)) {
model.setCellType(cell, CellType.VISITED);
}

if (cell.equals(target)) {
U.value = g.get(cell);
bestGoal = cell;
}

iterable.setStartingCell(cell);
BeamStackEntry bse = beamStack.peek();

for (Cell child : iterable) {
if (searchState.haltRequested()) {
throw new HaltRequestedException();
}
// TODO: Find out why?
searchState.resetState();

while (searchState.pauseRequested()) {
System.out.println("yes 3");
searchSleep(pathfindingSettings);

if (searchState.haltRequested()) {
throw new HaltRequestedException();
}
}

double tentativeGscore = g.get(cell)
+ pathfindingSettings
.getWeight(cell,
child);

if (tentativeGscore < g.getOrDefault(
child,
Double.POSITIVE_INFINITY)) {

double f = tentativeGscore + h.estimate(child, target);

searchSleep(pathfindingSettings);

if (bse.fmin heapNode.cell.equals(child));

nextOpen.add(new HeapNode(child, f));

g.put(child, tentativeGscore);
p.put(child, cell);
searchStatistics.incrementOpened();

if (!child.getCellType().equals(CellType.SOURCE) &&
!child.getCellType().equals(CellType.TARGET)) {
model.setCellType(child, CellType.OPENED);
}
}
}
}

PriorityQueue nextOpen = open.get(layerIndex + 1);

if (nextOpen.size() > pathfindingSettings.getBeamWidth()) {
pruneLayer(model,
nextOpen,
pathfindingSettings,
searchStatistics);
}
}

layerIndex++;
open.put(layerIndex + 1, new PriorityQueue());
closed.put(layerIndex, new HashSet());
beamStack.push(new BeamStackEntry(0, U.value));
}

for (PriorityQueue queue : open.values()) {
for (HeapNode heapNode : queue) {
Cell cell = heapNode.cell;

if (!cell.getCellType().equals(CellType.SOURCE) &&
!cell.getCellType().equals(CellType.TARGET)) {
model.setCellType(cell, CellType.FREE);
}
}
}

for (Set closedSet : closed.values()) {
for (Cell cell : closedSet) {
if (!cell.getCellType().equals(CellType.SOURCE) &&
!cell.getCellType().equals(CellType.TARGET)) {
model.setCellType(cell, CellType.FREE);
}
}
}

if (bestGoal != null) {
List path = new ArrayList();

for (Cell cell = bestGoal;
cell != null;
cell = p.get(cell)) {

path.add(cell);
}

Collections.reverse(path);
return path;
}

return null;
}

private static void pruneLayer(GridModel model,
PriorityQueue open,
PathfindingSettings pathfindingSettings,
SearchStatistics searchStatistics) {

List keepList = new ArrayList(open);

for (HeapNode heapNode : keepList) {
Cell cell = heapNode.cell;

if (!cell.getCellType().equals(CellType.SOURCE) &&
!cell.getCellType().equals(CellType.TARGET)) {
model.setCellType(cell, CellType.FREE);
}
}

keepList.sort((a, b) -> Double.compare(a.f, b.f));
keepList = keepList.subList(0, pathfindingSettings.getBeamWidth());

for (HeapNode heapNode : keepList) {
Cell cell = heapNode.cell;

if (!cell.getCellType().equals(CellType.SOURCE) &&
!cell.getCellType().equals(CellType.TARGET)) {
model.setCellType(cell, CellType.OPENED);
}
}

List pruneList = new ArrayList();
double fmin = Double.POSITIVE_INFINITY;

for (HeapNode heapNode : open) {
if (!keepList.contains(heapNode)) {
pruneList.add(heapNode);
fmin = Math.min(fmin, heapNode.f);
}
}

for (HeapNode heapNode : pruneList) {
open.remove(heapNode);
Cell cell = heapNode.cell;

if (!cell.getCellType().equals(CellType.SOURCE) &&
!cell.getCellType().equals(CellType.TARGET)) {
model.setCellType(cell, CellType.VISITED);
}
}
}

private static final class BeamStackEntry {
double fmin;
double fmax;

BeamStackEntry(double fmin, double fmax) {
this.fmin = fmin;
this.fmax = fmax;
}
}

private static final class DoubleHolder {
double value;
}
}
< /code>

воспроизводить ошибки < /h4>
Обратите внимание, что у вас будет настройка панели настроек:

Выше приведено только начиная с ширины луча 8.
Некоторые сбои сбоя.package io.github.coderodde.pathfinding.finders;

import io.github.coderodde.pathfinding.heuristics.OctileHeuristicFunction;
import io.github.coderodde.pathfinding.logic.GridCellNeighbourIterable;
import io.github.coderodde.pathfinding.logic.GridNodeExpander;
import io.github.coderodde.pathfinding.logic.PathfindingSettings;
import io.github.coderodde.pathfinding.logic.SearchState;
import io.github.coderodde.pathfinding.logic.SearchStatistics;
import io.github.coderodde.pathfinding.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import io.github.coderodde.pathfinding.utils.CellType;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class BeamStackSearchFinderTest {

private final PathfindingSettings ps = new PathfindingSettings();
private final SearchState searchState = new SearchState();
private final SearchStatistics searchStatistics =
new SearchStatistics(null,
null,
null,
null);

public BeamStackSearchFinderTest() {
ps.setDontCrossCorners(false);
ps.setAllowDiagonals(true);
ps.setFinder(new BeamStackSearchFinder());
ps.setHeuristicFunction(new OctileHeuristicFunction());
ps.setFrequency(1000);
}

@Test
public void hasSolutionPath() {
System.out.println("hasSolutionPath()");

GridModel model = new GridModel(20, 5);
model.moveTarget(17, 2);
model.moveSource(15, 2);
model.setCellType(16, 2, CellType.WALL);
ps.setBeamWidth(1);

GridNodeExpander expander = new GridNodeExpander(model, ps);

GridCellNeighbourIterable iterable =
new GridCellNeighbourIterable(model,
expander,
ps);

List pathBreadthFirstSearch =
new BFSFinder()
.findPath(model,
iterable,
ps,
searchState,
searchStatistics);

List pathBeamStackSearch =
new BeamStackSearchFinder()
.findPath(model,
iterable,
ps,
searchState,
searchStatistics);

System.out.println("BSS: " + pathBeamStackSearch.size());
System.out.println("BFS: " + pathBreadthFirstSearch.size());

assertEquals(pathBreadthFirstSearch.size(),
pathBeamStackSearch.size());
}

@Test
public void debugNoPath() {
System.out.println("debugNoPath()");

GridModel model = new GridModel(53, 33);
model.moveTarget(6, 4);
model.moveSource(3, 4);
model.setCellType(4, 2, CellType.WALL);
model.setCellType(4, 3, CellType.WALL);
model.setCellType(5, 3, CellType.WALL);
model.setCellType(5, 4, CellType.WALL);
model.setCellType(5, 5, CellType.WALL);

ps.setBeamWidth(1);

GridNodeExpander expander = new GridNodeExpander(model, ps);

GridCellNeighbourIterable iterable =
new GridCellNeighbourIterable(model,
expander,
ps);

List pathBreadthFirstSearch =
new BFSFinder()
.findPath(model,
iterable,
ps,
searchState,
searchStatistics);

List pathBeamStackSearch =
new BeamStackSearchFinder()
.findPath(model,
iterable,
ps,
searchState,
searchStatistics);

System.out.println("BSS: " + pathBeamStackSearch.size());
System.out.println("BFS: " + pathBreadthFirstSearch.size());

assertEquals(pathBreadthFirstSearch.size(),
pathBeamStackSearch.size());
}

@Test
public void suboptimal() {
System.out.println("suboptimal()");

GridModel model = new GridModel(53, 33);
model.moveTarget(7, 3);
model.moveSource(6, 5);

model.setCellType(5, 2, CellType.WALL);
model.setCellType(5, 3, CellType.WALL);
model.setCellType(6, 3, CellType.WALL);

model.setCellType(6, 4, CellType.WALL);
model.setCellType(7, 4, CellType.WALL);
model.setCellType(7, 5, CellType.WALL);

model.setCellType(7, 6, CellType.WALL);
model.setCellType(6, 6, CellType.WALL);
model.setCellType(5, 7, CellType.WALL);

ps.setBeamWidth(1);

GridNodeExpander expander = new GridNodeExpander(model, ps);

GridCellNeighbourIterable iterable =
new GridCellNeighbourIterable(model,
expander,
ps);

List pathBreadthFirstSearch =
new BFSFinder()
.findPath(model,
iterable,
ps,
searchState,
searchStatistics);

List pathBeamStackSearch =
new BeamStackSearchFinder()
.findPath(model,
iterable,
ps,
searchState,
searchStatistics);

System.out.println("BSS: " + pathBeamStackSearch.size());
System.out.println("BFS: " + pathBreadthFirstSearch.size());

assertEquals(pathBreadthFirstSearch.size(),
pathBeamStackSearch.size());
}
}


Подробнее здесь: https://stackoverflow.com/questions/797 ... d-complete