Beam Search、树搜索与 MCTS 规划

import java.util.*;
public class Main {
    static void near(double expected,double actual) {
        if (!Double.isFinite(actual) || Math.abs(expected-actual)>1e-9*Math.max(1,Math.abs(expected)))
            throw new AssertionError(expected+" != "+actual);
    }
    static void check(boolean ok) { if(!ok) throw new AssertionError(); }
    static void bad(Runnable r) {
        try { r.run(); } catch(IllegalArgumentException e) { return; }
        throw new AssertionError("invalid input accepted");
    }
record Edge(int to,double logp) {}
    record Candidate(int node,double score) {}
    static OptionalDouble beam(List<List<Edge>> graph,int start,int goal,int width,int depth) {
        if(graph==null||start<0||goal<0||start>=graph.size()||goal>=graph.size()||width<1||depth<0)
            throw new IllegalArgumentException("configuration");
        for(List<Edge> edges:graph) {
            if(edges==null) throw new IllegalArgumentException("row");
            for(Edge e:edges) if(e==null||e.to()<0||e.to()>=graph.size()||!Double.isFinite(e.logp())||e.logp()>0)
                throw new IllegalArgumentException("edge");
        }
        List<Candidate> frontier=List.of(new Candidate(start,0));
        Comparator<Candidate> rank=Comparator.comparingDouble(Candidate::score).reversed().thenComparingInt(Candidate::node);
        for(int d=0;d<depth;d++) { // 深度上限保证有环图也终止；这不是UCT访问回传。
            List<Candidate> next=new ArrayList<>();
            for(Candidate c:frontier) {
                if(c.node()==goal) {next.add(c);continue;} // 完成项保留，不继续生成动作。
                for(Edge e:graph.get(c.node())) {
                    double score=c.score()+e.logp();
                    if(!Double.isFinite(score)) throw new IllegalArgumentException("overflow");
                    next.add(new Candidate(e.to(),score));
                }
            }
            next.sort(rank); // 按当前累计分数剪枝，并非按未知最终成功率排序。
            frontier=new ArrayList<>(next.subList(0,Math.min(width,next.size())));
            if(frontier.isEmpty()) break;
        }
        return frontier.stream().filter(c->c.node()==goal).mapToDouble(Candidate::score).max();
    }
    public static void main(String[] args) {
List<List<Edge>> g=List.of(List.of(new Edge(1,-.1),new Edge(2,-.2)),List.of(new Edge(3,-10)),List.of(new Edge(3,-.1)),List.of());
        near(-10.1,beam(g,0,3,1,2).orElseThrow());
        near(-.3,beam(g,0,3,2,2).orElseThrow());
        near(0,beam(g,3,3,1,0).orElseThrow());
        check(beam(g,0,3,2,0).isEmpty());
        check(beam(List.of(List.of(new Edge(0,0))),0,0,1,4).isPresent());
        check(beam(List.of(List.of(),List.of()),0,1,1,3).isEmpty());
        bad(()->beam(g,0,3,0,2));
        bad(()->beam(List.of(List.of(new Edge(0,Double.NaN))),0,0,1,1));
        System.out.println("PASS 8 cases");
    }
}