cayleypy.algo.BeamSearchAlgorithm

class cayleypy.algo.BeamSearchAlgorithm[source]

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)[source]

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, verbose: int = 0) → BeamSearchResult[source]

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.
verbose – Verbosity level (0=quiet, 1=basic, 10=detailed, 100=profiling).

Returns:

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

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) → BeamSearchResult[source]

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).

Returns:

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