Master's degree in Modelling for Science and Engineering
Combinatorial Algorithms for graphs
Additional information and tools
- A* Algorithm:
- Routing problem: Barcelona-Sevilla; the data map of spain can be downloaded from
Here you can find my solution of the Barcelona-Sevilla problem for reference
(recall that it depends globally on the distance formula).
in the setting of the memory structure recommended in the assignment.
- For testing the program, you can use the much smaller file catalunya.csv.zip (51.9Mb)
(it has only 3472620 nodes and 201235 ways and it has the same format as the file
Valid nodes ID for start and goal are: 771979683 (in Girona) and 429854583 (in Lleida).
- To develop the program you can use the even much smaller data
SabadellNodes.csv and SabadellStreets.csv
(the files's format is specified inside the files in a comment line).
The disadvantage in using this data is that the reading part of the program is different from the one needed to deal with the assignment.
- Dijkstra Algorithm:
- Solve and implement the solution of the example Flight Agenda in the document Dijkstra's Application.
- As data you can use the following two files (if you have already done the assignment with some other data, please do not continue reading):
- Flight201301u.zip contains a flight time table taken from
but with serious modifications (which implies that the flights are no longer true). Among the simplifications, we assume that all flights operate every day.
Each line contains:
- Departure airport code;
- Arrival airport code;
- Departure time (in departure airport time zone);
- Arrival time (in arrival airport time zone);
- Number of days: 1 means that it arrives the day after, 2 means that it arrives two days after.
- Elapsed time as HHHMM. For example 00150 means 1 hour, 50 minutes.
Caution: This big list of flights contains more than one connected component: that is, not all possible trips can be done. For example:
- MCG is an isolated point.
- ZEL is just connected to YKT and vice-versa.
- Airports.zip contains information about the airports.
In particular, from the airport code you can extract the city or name of the airport.
The file is taken from:
As assignment you can find the flight agenda for the following itineraries (all of them with departure at 9am):
- Itinerary 1:
- Departure: REU, "Reus Air Base","Reus"
- Arrival: ILD, "Lleida-Alguaire Airport","Lleida"
- Itinerary 2:
- Departure: AAA, Anaa Airport in French Polynesia.
- Arrival: GKA, Goroka Airport in Papua New Guinea.
- Itinerary 3:
- Departure: GDT, "JAGS McCartney International Airport","Cockburn Town","Turks and Caicos Islands"
- Arrival: JGO, "Qeqertarsuaq Heliport","Qeqertarsuaq Airport","Greenland"
Heuristics and problem representation
- Heuristics: Intelligent Search Strategies for Computer Problem Solving, Judea Pearl
Addison-Wesley Pub (Sd) | ISBN: 0201055945 | 1984-04 | djvu (ocr) | 399 pages | 3.66 Mb
Chapter 1; Pages 3-13 and 27-31.
- Hanoi Towers
Overview of optimization algorithms: Deterministic and heuristic
Deterministic optimization for nonlinear problems (constrained and non-constrained)
- Gradient descent ("steepest descent")
- Newton and Quasi-Newton methods
- Conjugate gradient methods
- Levenberg Marquardt
- Karush-Kuhn-Tucker conditions for constrained optimization
- Penalty and Barrier Methods for constrained optimization
Solve the following Rosenbrock’s function exercise.
Optional Assignment (to train the skills in a canonical-academic problem)
Maximization of a (complicate and artificial) function by a genetic algorithm.
A possible migration model.
- Basic bibliography
- Some interesting links from the wikipedia page
Write a program that solves the N Queens Problem by means of a simulated annealing algorithm for N ≥ 8.
The N Queens Problem consists in placing N queens in an N x N chess board so that no queen is threatening any other queen
(queens threaten any queen in the same row, column or diagonal).
Ant colony algorithms
- Basic bibliography
- Concrete examples
A traveling salesman must visit all cities appearing in the
table of distances between European cities
starting and ending in Barcelona. He travels by car. Use an ACO to compute the optimum route according to driving distance
(take edge probabilities of the form stated in page 249 of the [Dorigo, Blum] paper).
The list of assignments that will be proposed is the following:
(pass is more than 49 points)
|Map routing (A* algorithm)
||December 12, 2021
||January 9, 2022
||February 6, 2022
||February 6, 2022
||Together increment the final mark up to 20 points
|Ant Colony Algorithm|