![]() Apply all the valid transitions to this state and obtain its children states.Start from the initial condition/state of the problem.Also, it is usual that several representations can be valid for one single problem, choosing correctly between them can be fundamental for the simplicity of the solution and the effectiveness of the search algorithm to be applied.Įssentially, the process that we will implement in this post (known as Breath-First Search, or BFS) will pass through the following steps: In these problems some precautions have to be in mind: states must store all the information that is important for the problem, and transitions have to be realistic in the problem and they must allow to reach the goal from the starting point. In our problem the transitions are the same independently of the state where they will be applied to, but sometimes there is a general set of valid transitions and their applicability will depend on the specific state to be applied to.Īlthough in this basic problem the states and transitions (together, they form the representation of the problem) can be directly obtained from the text of the problem, one can find cases where neither states nor transitions are so clear. Defining the valid transitions: in this case it is easy too, our valid transitions are the three permitted operations of the problem (and they will be represented as: \(*3\), \(+7\), \(-2\)).You don't need to be strict with this, only to know what kind of information you will need to represent your problem and being sure that your state space is closed under the transitions (operations) to be defined in the next point, that is, if you take a state in your space and apply any of the valid transitions, you obtain a (probably new) state in your space. Defining the state space: in this case is very obvious, our states will be the different numbers that, eventually, we can reach by using the allowed operations.In order to solve this problem as a search problem in a state space we need to make some previous work: We would like to know the shortest (or one of the shortest if there are several ones) sequence of operations for this goal.įor example, if we want to reach \(23\) starting from \(5\), one possible solution is: Suppose that you want to start from a first number and reach a second one by using only some allowed operations, specifically multiplying by \(3\), adding \(7\), or subtracting \(2\). Let's start presenting the problem to be solved: BFS is one of the search algorithms that belongs to the group of blind search algorithms that, essentialy, all can do is to distinguish a non-goal state from a goal one. You can find a more theoretical point of view of search problems in this post or in this one. For that, we will start working with a very basic problem that can be solved as a search in an adequate way and then we will move to solve some other, bigger and more interesting, problems by using the same general solution. In this post we will provide an agent based model that solves BFS in a generic way (as generic as it can be done with a standard NetLogo programming style).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |