JBoss.org Community Documentation

- Prev
- Next

## Chapter 12. Exact methods

## 12.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 data sets) and are therefore mostly useless.

## 12.2. Brute Force

### 12.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 these scalability graphs from the Benchmarker:

### 12.2.2. Configuration

Using the brute force algorithm is easy:

    <solver>

      ...

      <bruteForce>

      </bruteForce>

    </solver>

## 12.3. Depth-first search

### 12.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.

### 12.3.2. Configuration

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

- PrevChapter 11. Hyperheuristics
- Top of page
- Front page
- NextChapter 13. Benchmarking and tweaking