cayleypy.algo.BeamSearchAlgorithm

class cayleypy.algo.BeamSearchAlgorithm(graph: CayleyGraph)

Beam search algorithm for finding paths in Cayley graphs.

This class implements the beam search algorithm to find paths from a given start state to the central state of a Cayley graph. It can use various heuristics (predictors) to guide the search and supports meet-in-the-middle optimization.

__init__(graph: CayleyGraph)

Initialize the beam search algorithm.

Parameters:

graph – The Cayley graph to search on.

Methods

__init__(graph)	Initialize the beam search algorithm.
search(*, start_state[, destination_state, ...])	Tries to find a path from start_state to destination state using Beam Search algorithm.
search_advanced(start_state[, ...])	Advanced beam search using PyTorch with non-backtracking capabilities.
search_simple(*, start_state[, predictor, ...])	Tries to find a path from start_state to central state using simple Beam Search algorithm.

search(*, start_state: Tensor | ndarray | list, destination_state: Tensor | ndarray | list | None = None, beam_mode: str = 'simple', predictor: Predictor | None = None, beam_width: int = 1000, max_steps: int = 1000, history_depth: int = 0, return_path: bool = False, bfs_result_for_mitm: BfsResult | None = None, use_child_scores: bool = False, verbose: int = 0) → BeamSearchResult

Tries to find a path from start_state to destination state using Beam Search algorithm.

The following beam search modes are supported:

• “simple” - classic beam search algorithm that finds paths from start state to central state. Uses meet-in-the-middle optimization if bfs_result_for_mitm is provided. Supports path restoration if return_path=True.

• “advanced” - enhanced beam search with non-backtracking capabilities. Supports configurable history depth to avoid revisiting states. Uses PyTorch for efficient batch processing.

Parameters:

• start_state – State from which to start search.

• destination_state – Target state to find. Defaults to central state for “simple” mode.

• beam_mode – Type of beam search (see above). Defaults to “simple”.

• predictor – A heuristic that estimates scores for states (lower score = closer to destination). Defaults to Hamming distance heuristic.

• beam_width – Width of the beam (how many “best” states we consider at each step).

• max_steps – Maximum number of search steps/iterations before giving up.

• history_depth – For “advanced” mode, how many previous levels to remember and ban from revisiting.

• return_path – For “simple” mode, whether to return path (consumes much more memory if True).

• bfs_result_for_mitm – For “simple” mode, BfsResult with pre-computed neighborhood of central state for meet-in-the-middle optimization. Defaults to None.

• use_child_scores – For “simple” mode, whether to score states using Predictor.score_children (see search_simple()). Defaults to False.

• verbose – Verbosity level (0=quiet, 1=basic, 10=detailed, 100=profiling).

Returns:

BeamSearchResult containing found path length and (optionally) the path itself.

search_advanced(start_state: Tensor | ndarray | list, destination_state: Tensor | ndarray | list | None = None, *, beam_width: int = 1000, max_steps: int = 1000, history_depth: int = 0, predictor: Predictor | None = None, verbose: int = 0) → BeamSearchResult

Advanced beam search using PyTorch with non-backtracking capabilities.

This method implements an improved beam search algorithm that supports: - Non-backtracking constraints (avoiding revisiting states) - Batch processing for efficiency - Configurable history depth for state banning

Parameters:

• start_state – State from which to start search.

• destination_state – Target state to find. Defaults to central state.

• beam_width – Width of the beam (how many best states to consider).

• max_steps – Maximum number of search steps.

• history_depth – How many previous levels to remember and ban from revisiting.

• predictor – Predictor object for scoring states. If None, uses Hamming distance.

• batch_size – Batch size for model predictions.

• verbose – Verbosity level (0=quiet, 1=basic, 10=detailed, 100=profiling).

Returns:

BeamSearchResult with search results.

search_simple(*, start_state: Tensor | ndarray | list, predictor: Predictor | None = None, beam_width=1000, max_steps=1000, return_path=False, bfs_result_for_mitm: BfsResult | None = None, use_child_scores: bool = False) → BeamSearchResult

Tries to find a path from start_state to central state using simple Beam Search algorithm.

Parameters:

• start_state – State from which to start search.

• predictor – A heuristic that estimates scores for states (lower score = closer to center). Defaults to Hamming distance heuristic.

• beam_width – Width of the beam (how many “best” states we consider at each step).

• max_steps – Maximum number of iterations before giving up.

• return_path – Whether to return path (consumes much more memory if True).

• bfs_result_for_mitm – BfsResult with pre-computed neighborhood of central state to compute for meet-in-the-middle modification of Beam Search. Beam search will terminate when any of states in that neighborhood is encountered. Defaults to None, which means no meet-in-the-middle (i.e. only search for the central state).

• use_child_scores – Whether to score states on the next layer with Predictor.score_children applied to states on the current layer, instead of applying the predictor to the states on the next layer themselves. Scores are the same, but the predictor is called once per state of the current layer instead of once per state of the next layer, which is much cheaper for models having one output per generator (Q-models). Defaults to False, which means the predictor is applied to states on the next layer.

Returns:

BeamSearchResult containing found path length and (optionally) the path itself.