48
edits
Changes
Jump to navigation
Jump to search
Line 9:
Line 9: + + Line 41:
Line 43: + + + +
heuristics
*They must work for any given input or network.
*They must work for any given input or network.
*They must have a single start point, and a single finish point.
*They must have a single start point, and a single finish point.
There is, another, a second type of algorithm - whereas most algorithms provably evaluate the most desirable end-state (for example, it is possible to mathematically prove that Dijkstra's algorithm gives the shortest route from one point to another), others are known as 'heuristic algorithms'. These are algorithms that, although giving a fairly good result, cannot provably give the best solution. While this may seem inferior, some problems are very different or even impossible to map out using normal algorithms, so heuristic ones are superior.
==Examples of Algorithms==
==Examples of Algorithms==
Prim's algorithm is used to find the minimum spanning tree when only some of a network is visible.
Prim's algorithm is used to find the minimum spanning tree when only some of a network is visible.
===Bin-filling algorithm===
The Bin filling algorithm is used to find the most efficient way of combining several differently sized objects into a space(s) with a certain size. An example would be the problem of packing objects into the boot of a car; the bin-filling algorithm is in fact a mathematically formulated version of the rule of thumb 'put the big things in first'; but in can be used for many other problems - loading cars onto ferries, sending messages via [[routers]] on the [[internet]], etc. It is a heuristic algorithm, as it does not give a provably maximal solution (the only way to do this, until Vijay Vazirani invented a new form of [[approximation algorithm]], was to arrange the objects in every conceivable order).
==See also==
==See also==
*[[Computability]]
*[[Computability]]