Master's degree in Modelling for Science and Engineering
Combinatorial Algorithms for graphs
- General definitions and searches on graphs
- Dijkstra Algorithm for optimum paths on graphs
- A* Algorithm: Heuristic search for optimum paths on graphs
- A* Algorithm:
- Routing problem: Barcelona-Sevilla; the data map of spain can be downloaded from
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).
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.
- 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 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 Genetic Algorithm application for COVID-19 pandemic.
You also need an efficiency aiming implementation of the Runge-Kutta-Fehlberg-Simo of orders 78 in Cnot++ (version 2.2).
Note on 20210103: There have been a lot of changes in the file (in general improving the advice),
but be aware that we have changed the figured real data (the new one agrees better with the discretization, and so it makes the exercise easier).
- Basic bibliography
- Some interesting links from the wikipedia page
You are a zookeeper in the reptile house.
One of your rare South Pacific Tufted Wizzo lizards (Tufticus wizzocus) has just had EIGHT babies.
Your job is to find a place to put each baby lizard in a nursery.
However, there is a catch, the baby lizards have very long tongues.
A baby lizard can shoot out its tongue and eat any other baby lizard before you have time to save it.
As such, you want to make sure that no baby lizard can eat another baby lizard in the nursery (burp).
For each baby lizard, you can place them in one spot on a grid.
From there, they can shoot out their tongue up, down, left, right and diagonally as well.
Their tongues are very long and can reach to the edge of the nursery from any location.
Figure 1 shows in what ways a baby lizard can eat another.
Figure 1 (A) the baby lizard can attack any other lizard in a red square. Thus it can be seen that a baby lizard can eat another lizard to its top, bottom, left right or diagonal. (B) In this setup both lizards can eat each other.
In addition to baby lizards, your nursery has some trees planted in it.
Your lizards cannot shoot their tongues through the trees nor can you move a lizard into the same place as a tree.
As such, a tree will block any lizard from eating another lizard if it is in the path.
Additionally, the tree will block you from moving the lizard to that location.
Figure 2 shows some different valid arrangements of lizards
Figure 2 Both nurseries have valid arrangements of baby lizards such that they cannot eat one another.
(A) with no trees, no lizard is in a position to eat another lizard.
(B) Two trees are introduced such that the lizard in the last column cannot eat the lizard in the second or fourth column.
Write a program in C that will take as input the number (from 0 to 8) and positions of trees in the grid,
and returns a valid configuration for the 8 baby lizards computed by using simulated annealing.
Idea of the algorithm:
The lizards are initially placed in random rows and columns such that each lizard is in a different row and a different column.
During each turn, an attacked lizard is chosen and a random column is picked for that lizard.
If moving the lizard to the new column will reduce the number of attacked lizards on the board, the move is taken
(so the energy function is the number of attacked lizards).
Otherwise, the move is taken only with a certain probability, which decreases over time.
Questions to be addressed in the report
- Why is simulated annealing a good algorithm for this problem? (think about complexity and other considerations).
- What would be reasonable temperature decrease schedules to use for this problem? Include equations and function graphs for each schedule that you test.
- Experiment with the different temperature schedules you found and conduct a comparative analysis, running your algorithm on different problems (that is, different number and positions of trees).
Motivate your answer with a table showing some measure of performance on your test problems (for example, steps taken) for your different schedules.
Include a conclusion on which schedule seems superior with supporting statistics and illustrations.
- In addition to using simulated annealing, could you also have used genetic algorithms to solve this problem? If so, how would you have done it (just explain, you do not have to code), if not, then why?
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)
||January 10, 2021
||February 16, 2021
||January 10, 2021
||February 16, 2021
||Together increment the final mark up to 20 points
|Ant Colony Algorithm|
- To comply with the university evaluation rules:
- The compulsory assignment of Map routing (A* algorithm) is to be done in pairs.
- All other assignments (compulsory or optional) are individual.
- The assignments will be delivered in Campus Virtual. Further instructions will be given.
- For each assignment a report must be written including:
- introduction stating the problem and the algorithm to solve it,
- the code of the program,
- the results of running the program and
- If necessary there will be interviews to evaluate and discuss some of the assignments.
- The quality of the code of the program will be taken into account for the marks of the assignments and discussed in the interviews (if any).