The difference between the stochastic and heuristic algorithm

Question

Extending the question of streetparade , I would like to ask what is the difference, if any, between the stochastic and heuristic algorithm.

Is it possible to say that the stochastic algorithm is actually one of the types of heuristic?

Answer 1

TTBOMK, "stochastic algorithm" is not a standard term. The "randomized algorithm", however, is probably implied here.

Randomized: Uses randomness somehow. There are two options: Monte Carlo algorithms always end in a limited time, but do not guarantee the optimal solution, while Las Vegas algorithms are not necessarily guaranteed at any finite time, but promise to find the optimal solution. (Usually they should also have a finite expected runtime.) Examples of general Monte Carlo algorithms: MCMC, simulated annealing and testing of Miller-Rabin primitives. Quicksort with a randomized rod selection is the Las Vegas algorithm, which always ends in a finite time. An algorithm that does not use randomness is deterministic .

Heuristic: It is not guaranteed to find the correct answer. An algorithm that is not heuristic is accurate .

Many heuristics are sensitive to the "random" properties of the input data that do not affect the true solution, for example, order elements are considered in the First-Fit heuristic for a packaging problem. In this case, they can be considered as randomized Monte Carlo algorithms: you can randomly rearrange the inputs and repeat them, always preserving the best answer you will find. OTOH, other heuristics do not have this property - for example, the First-Fit-Decreasing heuristic is deterministic, because it always sorts the elements first in decreasing size order.

If the set of possible outputs of a particular randomized algorithm is finite and contains a true answer, then it is "guaranteed" for a sufficiently long time to ultimately find it (in the sense that the probability of not being found is arbitrarily small, but never 0). Please note that this is not so automatic that some rearrangement of the inputs to the heuristic will lead to an exact answer - in the case of First-Fit it turns out that this is true, but this was proved only in 2009.

Sometimes stronger statements can be made about the convergence of randomized algorithms: they usually go along the lines: “For any given small threshold d, after t steps, we will be within d the optimal solution with probability f (t, d),” and f (t, d) increases from t and d.

Answer 2

Stand approaches are usually used to speed up solutions and test approaches for solving complex NP problems.

• Stochastic algorithms use randomness

  They use all the combinations, but not in order, but instead they use random ones from the whole range of possibilities, hoping to hit the solution more quickly. Implementation is very fast and single iteration is also fast (constant time)

• Heuristic Algorithms

  They do not collect combinations randomly, but are based on some knowledge of the process used, the set of input data, or use. Thus, they significantly reduce the number of combinations only for those that are likely to be a solution, and use only those, but usually all of them until a solution is found.

  The complexity of the implementation depends on the problem, the only iteration is usually much slower than the stochastic approach (constant time), therefore the heuristic is used only if the number of possibilities decreases to the actual speed up, because even if the complexity of the algorithm with the heuristic is usually much lower, sometimes the constant time is large enough to even slow down the work ... (at run time)

Stand approaches can be combined