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

[Anonymous]

Я читал Поиск бумажных пучков: интегрирование обратной связи с поиском луча Ронг Чжоу и Эрика А. Хансена и я пытались реализовать его в Java (см. Репозиторие Java в Github. Мой код заключается в следующем: < /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;
}
}

Моя текущая реализация кажется очень чувствительной к ширине луча: если слишком мал, она либо возвращает неоптимальный путь, либо заканчивается без пути.

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