Extended Breadth-First Search Algorithm
This addresses a bottleneck in AI search algorithms for researchers and practitioners dealing with large-scale state-space problems, but appears incremental in nature.
The paper tackles the problem of classical search algorithms being impractical for large state spaces by introducing an algorithm that enables handling huge state spaces and incorporates a more easily embeddable heuristic concept.
The task of artificial intelligence is to provide representation techniques for describing problems, as well as search algorithms that can be used to answer our questions. A widespread and elaborated model is state-space representation, which, however, has some shortcomings. Classical search algorithms are not applicable in practice when the state space contains even only a few tens of thousands of states. We can give remedy to this problem by defining some kind of heuristic knowledge. In case of classical state-space representation, heuristic must be defined so that it qualifies an arbitrary state based on its "goodness," which is obviously not trivial. In our paper, we introduce an algorithm that gives us the ability to handle huge state spaces and to use a heuristic concept which is easier to embed into search algorithms.