We would simply be moving through the various states computed by the heuristic in order to reach the goal state from the starting one. If we could do that we would not need to be doing a search. There is no guarantee this heuristic function will return a particular state that is closer to a goal state than any other one. To do this we use a heuristic function which tells us how close we are to a goal state. The idea behind a heuristic search is that we explore the node that is most likely to be nearest to a goal state. In these cases, we say to be working with an heuristic: a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals. The ideal situation is that we can manage a complete information about the best way to reach the solution, but in almost every interesting case all we can get is an intuition/approximation about how much cost to reach the goal. When we are looking for a "short" path connecting the starting point and the solution, we count how many transitions have been applied in the path (the length of the path), but in other more general cases we need some way to measure the cost of the different options to choose the best one. In this case we say that we make an informed search. But if we would have any global information about the structure of the space, maybe we could take decisions of the correct direction to go faster form the initial state to the solution. we have no knowledge about the space, and we make a blind search.
#IF NETLOGO HOW TO#
If all the information we have about the state space is local, that is, we only know how to reach new states from previous ones by direct application of transitions, BFS algorithm (or similar ones) is the best we can do. For this reason, although the algorithm returns an optimal sequence of actions that reachs the solution (in the sense that it has the minimum number of actions), in the process to build this sequence the algorithm can perform a huge number of steps (and, consequently, spend a huge number of time to reach the solution).
In that post we presented a very simple algorithm called Breath First Search ( BFS) providing a sorted way of browsing the space of states in a blind way.
Usually, we will work with problems that look for solutions as sequences of actions that transform initial states, that are not solutions of the problem, into final states, that are solutions of the problem. In a previous post we have explored the idea of solving problems by projecting them on state spaces and then using a search algorithm to find the solution.
0 kommentar(er)
