This project aims to compare the performance of some of the most well-known NP problems with machine learning (ML) models. Currently, the focus is on two NP problems: the Travelling Salesman Problem (TSP) and the N-Queens Problem.
- Travelling Salesman Problem (TSP): The goal is to find the shortest possible route that visits each city exactly once and returns to the origin city.
- N-Queens Problem: The objective is to place N queens on an N×N chessboard so that no two queens threaten each other.
The purpose of this project is to evaluate and compare the efficiency and performance of traditional NP problem-solving methods with modern machine learning approaches. By doing so, we aim to understand the strengths and weaknesses of each approach in solving complex computational problems.
The N-Queens problem is showing very good preliminary results with the use of convolutional blocks and fully connected blocks in the model architecture. This indicates that the model can effectively learn and generalize the constraints of the N-Queens problem. On the other hand, the Travelling Salesman Problem is not showing significant progress with a direct machine learning approach utilizing attention blocks, Transformer blocks, and residual blocks. This suggests that the current ML model architecture may not be well-suited for solving the TSP, highlighting the need for further research and possibly different techniques or architectures to address this challenge.