JBoss.org Community Documentation

- Prev
- Next

## Chapter 11. Exact methods

## 11.1. Overview

Exact methods will always find the global optimum and recognize it too. That being said, they don't scale (not even beyond toy problems) and are therefore mostly useless.

## 11.2. Brute Force

### 11.2.1. Algorithm description

The Brute Force algorithm creates and evaluates every possible solution.

Notice that it creates a search tree that explodes as the problem size increases. Brute Force is mostly unusable for a real-world problem due to time limitations, as proven by this scalability graph from the benchmarker:

### 11.2.2. Configuration

Using the brute force algorithm is easy:

    <solver>

      ...

      <bruteForce>

      </bruteForce>

    </solver>

## 11.3. Depth-first search

### 11.3.1. Algorithm description

Depth-First Search is an improvement over Brute Force, as it regularly prunes away an entire subset of solutions which cannot have a better solution than the best solution already found at that point. for example: at index 15, it can prune away all unvisited solutions with queen A on row 0, because none will be better than the solution of index 14 with a score of `-1`.

Notice that it (much like Brute Force) creates a search tree that explodes as the problem size increases. Depth-First Search is mostly unusable for a real-world NP-complete problem due to time limitations.

Technically, this Backtracking Depth-First Search with pruning is a form of Branch And Bound, although Branch and Bound is often more flexible in its pruning.

### 11.3.2. Configuration

Depth-first search is not yet implemented. Patches welcome.

- PrevChapter 10. Evolutionary algorithms
- Top of page
- Front page
- NextChapter 12. Benchmarking and tweaking