About • Technologies • Installation • Execution • License • Authors
This is a class project implemented in the context of the Parallel and Distributed Computing course, 2022/2023, at Instituto Superior Técnico. Its purpose is to give students a hands-on experience in parallel programming on both shared-memory and distributed-memory systems, using OpenMP and MPI, respectively.
The idea of this assignment is to write a sequential and two parallel implementations of a program that computes the shortest route to visit a given set of cities, the well-known traveling salesperson problem. This optimization problem falls in the NP-Hard complexity class, meaning that all known solutions to solve it exactly imply an exhaustive search over all possible sequences.
This section shows the installation steps for a generic linux-based system (fully tested on the Kali Linux distribution).
- Install the technologies required by the program
sudo apt update && sudo apt upgrade
sudo apt install build-essential
- Build the executable files (one for each version of the project)
make clean
make build
This section explains how to run each version of the project:
- Shell command
cd <version_dir>
./tsp <cities_file> <max_value>
This project is licensed under the MIT License - see LICENSE file for details.
| Name | GitHub ID | |
|---|---|---|
| André Nascimento | ArckenimuZ | andreffnascimento@tecnico.ulisboa.pt |
| João Veríssimo | Swag4Yolo | joao.verissimo@tecnico.ulisboa.pt |
| Pedro Henriques | PedroCarvalhoHenriques | pedro.carvalho.henriques@tecnico.ulisboa.pt |