This project was developed as part of a school assignment focused on NP-complete problems and graph theory algorithms.
The objective was to study different algorithmic strategies to solve a complex optimization problem and compare their behavior in terms of solution quality and execution time.
The project implements four algorithms based on graph theory concepts, each using a different strategy to solve the same NP-complete problem.
- Model an NP-complete problem using graph theory.
- Implement multiple algorithmic approaches to solve it.
- Analyze the trade-off between optimality and computational cost.
- Compare exact and approximate methods.
This algorithm searches for the optimal solution by exploring the complete solution space.
- Guarantees the best possible solution
- Computationally very expensive
- Execution time grows rapidly with problem size
This method is mainly used as a reference to evaluate the quality of approximate algorithms.
The constructive algorithm builds a solution step by step by adding elements according to a predefined rule.
Characteristics:
- Fast execution
- Produces a valid solution quickly
- Solution quality depends on the construction strategy
This algorithm starts from an initial solution and iteratively improves it by exploring its neighborhood.
Characteristics:
- Heuristic approach
- Improves an existing solution
- May converge to a local optimum rather than the global optimum
GRASP (Greedy Randomized Adaptive Search Procedure) is a multi-start metaheuristic combining greedy construction and local search.
Process:
- Generate a randomized greedy solution
- Improve it using local search
- Repeat the process multiple times and keep the best solution found
Characteristics:
- Balances exploration and exploitation
- Produces high-quality solutions
- Faster than exact methods for large instances
| Algorithm | Optimal Solution | Execution Time | Scalability |
|---|---|---|---|
| Exact Algorithm | ✅ Yes | ❌ Very slow | ❌ Poor |
| Constructive | ❌ Not guaranteed | ✅ Fast | ✅ Good |
| Local Search | ❌ Not guaranteed | ⚡ Medium | ✅ Good |
| GRASP | ❌ Not guaranteed | ⚡ Medium | ✅ Very good |
- NP-Complete Problems
- Graph Theory
- Exact Algorithms
- Heuristic Methods
- Local Search
- Metaheuristics
- GRASP (Greedy Randomized Adaptive Search Procedure)
This project highlights the fundamental trade-off between solution optimality and computational efficiency when solving NP-complete problems.
While exact algorithms guarantee optimal results, heuristic and metaheuristic approaches provide practical solutions for large problem instances.
School project developed as part of an algorithmics and graph theory course at ISEN Nantes.
TARIN Dorian
POIRIER Paul
GIROLT Alexandre
SOQUET Antonin