Randomized Algorithms

 

Home
Technology
Agents
Tabu Search
Randomized Algorithms
Cellular Automata
Evolutionary Algorithms
Neural Networks
Expert Systems
Fuzzy Systems
Simulated Annealing		  

Randomized Algorithms (RAs) are used when we have to take a decision from a set of possible decisions and we have no idea which one is better. We can use a deterministic algorithm that chooses the first or the second option. Randomized Algorithms usually choose one random action and continue the search with that decision.

A classic example for RAs is the Randomized QuickSort Algorithm (RQSA). Standard QuickSort chooses the middle of the vector (whose value is x) and then moves all values from the left which are greater than x to the right and all values from the right which are lower than x to the left. The process is continued with the 2 newly obtained vectors (left and right) until the entire vector is sorted. Instead of choosing the middle of the array, the RQSA chooses one random position and then performs the swaps accordingly.