Год выпуска: 2013 Автор: Vishal Kesri Издательство: LAP Lambert Academic Publishing Страниц: 76 ISBN: 9783659425080
Описание
NP-complete problem is a fascinating kind of problem because till now no one has discovered the polynomial-time algorithm to solve it and also no one has proved that no polynomial-time algorithm can exist for any NP-complete problem. It is an open research problem since it was first posed in 1971 to prove P?NP. This book specially focused on two NP-complete problems. 1. N-Queens problem: In Year 1848 chess player Max Bezzel had first time propose this problem in the form of 8-queens problem. And more than 100 year researcher try to solve n-queens problem but it’s still not completely solved. One implement algorithm describe in this book, which is able to provide one unique solution of n-queen problem in quadratic time. 2. Sum of subset problem: It is another NP-complete problem and one implement algorithm describe in this book which is able to provide all the solution to sum of subset problem and it takes less number of steps as compare to backtracking naive algorithm.
