Choosing the Best Heuristic for a NP-Problem

Abstract

Nowadays computers are used to solve incredibly complex problems. But in order to manage a problem we should develop an algorithm. Sometimes the human brain is not able to accomplish this task. Moreover, exact algorithms might need centuries to solve a formidable problem. In such cases heuristic algorithms that find approximate solutions but have acceptable time and space complexity play indispensable role. In present, all known algorithms for NP-complete problems are requiring time that is exponential in the problem size. Heuristics are a way to improve time for determining an exact or approximate solution for NP-problems. In our paper we want to analyze what are the possible heuristics available for NP-problems and we explain the characteristics and performance of each heuristic. Finally we analyze efficient heuristic out of all available heuristics for different NP-problems. One objective is that, after applying different heuristics for a particular NP-problem, a set of guidelines can be given that how a particular category of heuristics is better for a particular set of problems.