Publication date: 
Petr Váňa from the Department of Computer Science, Robert Pěnička and scientist Vojtěch Vonásek of the Department of Cybernetics at the Faculty of Electrical Engineering took part in a developer contest organized by the technology company in October, during which they had to solve the Traveling Salesman Problem. Their job was to design an algorithm that would offer the cheapest air connections between the selected areas. The trio has succeeded in the international competition of more than 500 teams of 50 nationalities with 8697 issued solutions.

The Traveling Salesman Problem is considered to be one of the most challenging tasks (it belongs to a group of problems called NP-hard* problem). The traveler must visit all the assigned cities without a predetermined order. This raises the basic question of what is the most effective way to visit all of these cities. What makes this problem challenging is a huge number of possible combinations - for example, there are over 180,000 combinations for visiting 10 different cities. In order for the salesman to find the right combination, he would have to try them all, so modern technologies and algorithms are used to address them.

This year,, a technology company focused on the search and sale of airline tickets, came up with a similar task. announced a programming contest, during which participants had to find the ideal algorithm for a passenger who wants to visit N areas and exactly one city in each area. In addition, he would had to stay there only for a single day then travel to the next stop from the same airport.

The winning solution uses the Breadth-first search algorithm (BFS), which is commonly used for look-up in combinatorial tasks. Such a task can be, for example, a board game of chess in which the algorithm would run through possible future move combinations.