Applying AI and Incomplete Solution Principles to Solve NP-hard Problems in the Real-Time Systems

Abstract:- In this paper a question of using artificial intelligence principles and an incomplete solution approach were explored for solving NP hard problems in the real-time systems using the maximum clique finding problem as an example. The incomplete solution is used to analyze different best known algorithms in the real-time environment, while artificial intelligence principles were implemented in a form of a meta-algorithm containing other problem specific algorithms. Experiments conducted in this paper have demonstrated that the meta-algorithm in a randomly generated graphs environment required up to 3 times less time to find a solution in a certain range of graphs than the best known general type algorithm, and was never slower in other ranges. Key-Words:- NP-hard problem, maximum clique, artificial intelligence, incomplete solution