Читать книгу Algorithms For Dummies - John Paul Mueller, John Mueller Paul, Luca Massaron - Страница 43
Going random and being blessed by luck
ОглавлениеSolving a search problem using brute-force techniques (described in “Avoiding brute-force solutions,” earlier in this chapter) is possible. The advantage of this approach is that you don’t need any domain-specific knowledge to use one of these algorithms. A brute-force algorithm tends to use the simplest possible approach to solving the problem. The disadvantage is that a brute-force approach works well only for a small number of nodes. Here are some of the common brute-force search algorithms:
| Technique | Description | Cons | Pros |
|---|---|---|---|
| Breadth-first search | Begins at the root node, explores each of the child nodes first, then moves down to the next level. It progresses level by level until it finds a solution. | Must store every node in memory, which means that it uses a considerable amount of memory for a large number of nodes. | Can check for duplicate nodes to save time and always comes up with a solution. |
| Depth-first search | Begins at the root node and explores a set of connected child nodes until it reaches a leaf node. It progresses branch by branch until it finds a solution. | Can’t check for duplicate nodes, which means that it might traverse the same node paths more than once. | It’s memory efficient. |
| Bidirectional search | Searches simultaneously from the root node and the goal node until the two search paths meet in the middle. | It’s time efficient and uses memory more efficiently than other approaches, and it always finds a solution. | Complexity of implementation, translating into a longer development cycle. |
