Travelling salesman problem
Heuristics approaches use a set of guiding rules for selection of the next node. But since heuristics result in approximations, they will not always give the optimal solution, although high quality admissible heuristics can find a useful solution in a fraction of the time required for a full brute force of the problem. An example of a heuristic for a node would be a summation of how many unvisited nodes are "close by" a connected node. This could encourage the salesman to visit a group of close by nodes clustered together before moving onto another natural cluster in the graph. See Monte Carlo algorithms and Las Vegas algorithms