AIMech AI
Home / Curated / Algorithms / MA*

MA*

Algorithms AIMech:MAStar DRAFT
A memory-controlled heuristic tree-search algorithm that stores separate lower bounds for absent and all successors, expands promising continuations, backs up successor costs, and prunes selected high-cost leaves while retaining bounds for regeneration.
Identity Notes & Concept Scope Current ignored-inclusive identity review on 2026-10-16 at base 0da1b27de4ee552bc8fb16a083d0f91d2a093142 examined1241 records,4921 identity occurrences and3760 normalized values, plus945 exact search occurrences in215 distinct content groups across four recorded roots. No candidate or context normalized collision was found for the recorded probes. MA* is curated as displayed ordinary-tree OPEN/CLOSED search with successor lower bounds and F-driven pruning; it remains distinct from the other member of this pair, MREC, SMA*, ITS, RBFS, RTAA* and amortized SVGD. Full current neighbor and inherited search-context readings are explicitly attributed in the discovery report; this is bounded absence evidence, not global novelty. Shared current source responsibility is main911, which remains partial; all27 original source items and separate main7/main912 responsibilities survive.

Claims & Grounded Evidence

6 Claims
Mechanism #separate-successor-bounds
For each node n, MA* stores g(n), depth d(n), and a remaining-cost estimate h(n,m) for each successor. It defines hf(n) as the minimum over successors absent from the explicit tree and hF(n) as the minimum over all successors; f(n)=g(n)+hf(n) is used for expansion selection and F(n)=g(n)+hF(n) for backed-up cost and pruning.
Mechanism #selection-and-continuation
Select the OPEN node with minimum f, breaking ties toward greater depth, and save its value as GL. Generate its next most promising absent successor. If that child has f<=GL, continue directly from it; otherwise perform bottom-up revision and the memory check before returning to global selection. A node with no ungenerated successors leaves OPEN for CLOSED.
Mechanism #pathmax-and-branch-backup
For a generated child m of n and q in S(m), pathmax raises h(m,q) to at least h(n,m)-c(n,m). Bottom-up revision increases a parent branch estimate h(q,p) to hF(p)+c(q,p) when that value is larger, recalculates the parent hF and F, and propagates the revision upward. Retained branch bounds carry information about subsequently pruned descendants.
Mechanism #base-pruning-rule
If count exceeds MAX after revision, repeatedly select the OPEN leaf with greatest F, breaking ties toward shallower depth. If its F equals the root F, stop pruning and return to selection; otherwise remove it, decrement count, reopen its parent from CLOSED if needed and recompute that parent’s hf and f. Base MA* does not stop pruning merely because count has fallen to MAX.
Scope #source-memory-measure
MAX denotes extra search storage. The paper states count<=MAX+|C*|, with |C*| defined as the greatest length of a path whose f value is at most the optimal solution cost C*. This is a source-specific search-state count statement, conditional on the relevant quantity being finite, rather than a strict total-memory or byte cap.
Scope #memory-endpoint-boundary
With sufficiently large MAX, pruning is avoided and the source describes A*-like operation with one successor generated at a time. With MAX=0 it describes an iterative-deepening-like procedure whose backed-up successor ordering differs from the cited IDA* comparator. These endpoint comparisons do not make the complete parameterized MA* procedure an alias of A* or IDA*.

⚠️ Curated Limitations & Negative Results

Artificial Intelligence Ontology (AIO) Grounding

Explicit AIO Snapshot Assessment: No Match

Rationale: The retained concepts are resource-controlled heuristic search algorithms. The inspected pinned AIO candidates describe supervised/learning tasks, neural or language models/layers, graph representations and mathematical functions; shared words such as graph, memory, recursive or minimum do not establish an exact, broader, narrower or substantive related match.

Search Scope: Historical branch358 snapshot: pinned AIO commit397851c547d1c4d8f06ef184f63c1d40bc86937a, SHA256 8f741d71408c93f15c62607106aa46f6edbc4e070c5546ed3ae111ada6e65cf6. All442 CLASS identity/synonym fields mechanically compared and class labels read;22 selected full nodes and all133 incident relations inspected. Other definitions and external definition-source papers were not all reread. This is a bounded pinned-snapshot mapping proposal requiring reassessment at eventual curation.
Examined AIO Candidate Rejection Reason
AIO:Classification AIO specifies supervised grouping of things. Neither retained algorithm is a classifier.
AIO:DecisionTree AIO defines a classification decision model; a heuristic search tree or AND/OR solution graph is not that classifier.
AIO:GraphConvolutionalNetwork The class is a deep neural network using graph structure, not a heuristic search procedure over problem states.
AIO:GraphConvolutionalPolicyNetwork This is a graph-convolutional reinforcement-learning graph generator. Neither candidate trains or deploys that policy network.
AIO:GraphLanguageModel A language model operating on graph-structured language inputs/outputs is not the candidate search procedure.
AIO:Layer A neural/deep-learning topology component is not a stateful search algorithm.
AIO:MachineLearningTask The defining process builds methods that learn from data. Neither candidate requires such learning; cost-bound revision is not sufficient to assert this relation.
AIO:MathematicalFunction A mathematical input/output rule does not identify these stateful search algorithms. Their evaluation functions are components, not the curated concept itself.
AIO:MaximumLayer Elementwise tensor merging in a neural layer is unrelated to selecting a highest-cost pruning candidate or a possible AND cost aggregation.
AIO:MemoryAugmentedLLM External readable/writable memory in an LLM is distinct from managing search nodes/arcs under memory pressure.
AIO:MemoryCellLayer A cell layer with internal state/weights is not retained frontier or solution-graph storage.
AIO:MinimumLayer Elementwise tensor merging in a neural layer is not search bound minimization.
AIO:Model The class denotes an abstract system representation. The candidates are procedures operating on search representations, not the represented system/model.
AIO:Network The class denotes interconnected entities. A problem graph can be such a representation, but that does not make the algorithm traversing it a Network or substantiate a mapping.
AIO:NeuroSymbolicLLM Neither candidate is an LLM combining neural language modeling and symbolic reasoning.
AIO:Preprocessing Neither algorithm is defined as formatting or transforming raw data for a machine-learning model.
AIO:ProbabilisticGraphicalModel The AIO class represents conditional dependence among random variables. MAO* acyclic AND/OR cost decomposition does not require a probabilistic graphical model; MA* also does not.
AIO:ReasoningLLM Heuristic search is not evidence that the algorithms are large language models or a specific LLM reasoning component.
AIO:RecursiveLLM Recursive neural architectures learning syntactic composition differ from search recursion/retained bound propagation.
AIO:RecursiveLanguageModel A deep recursive language network with neural layers is not either search procedure.
AIO:ReinforcementLearning Neither candidate is defined by learning from reward through exploration/exploitation. Selecting promising branches is insufficient for this mapping.
AIO:TrainingStrategy Neither source procedure trains a machine-learning model, and its memory/pruning policy is not the AIO preprocessing/training class.

Evidence Sources & Primary Literature

1 Source
Source ID Publication / Document Type / Access Reference & Checksum
chakrabarti1989
P. P. Chakrabarti, S. Ghose, A. Acharya, S. C. de Sarkar
primary paper
full_text
ID: doi:10.1016/0004-3702(89)90010-6
sha256:199bddda6954…

Curation Provenance

Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-16T04:23:47Z
Updated: 2026-10-16T04:23:47Z
Source File: data/curated/MAStar.yaml