Finding combination of trainstops through Europe

Jop Verbeek 0
Viewed 36

I am currently working on a school project. The objective is to find a route through Europe from trainstation to trainstation, from country to country where the names of the consecutive trainstations have to start with the letters of the alphabet consecutively and a country can only be used once. To give an example route:(Amsterdam Central, Netherlands) --> (Berlin, Germany) --> (Carcasonne, France) etc. Countries also need to be neighbouring countries. We have received a dataset in which countries and some of their specific stations are mentioned. Some of the countries don't have a large selection of stations, making it important that a certain letter is used with a certain country, because only a small selection first letters will be present for this specific country. Can someone maybe provide me with some guidance as to how I can tackle this problem. I am currently coding in python.

cheers!

search graph algorithm
2 Answers
- Sort countries in order of increasing number of letter choices
- Loop C over countries in order of increasing number of letter choices
    - Place C in position for a random letter that it provides
    - IF neighbouring positions have been populated, but they are NOT neighbours geographically
        - THEN choose a different letter for those available in C
ravenspoint0

I would use a constraint solver for this. (I'm familiar with CP-SAT because I use it at work, but you have options.)

For each letter from A to Z, create a variable whose domain is the set of stations whose name starts with that letter. Create 26 corresponding country variables and, for each corresponding station variable and country variable, add a table constraint to ensure that they describe the same thing (so the table contains entries like ("Amsterdam Central, Netherlands", "Netherlands"), though you have to translate into integer indices). Add an all-different constraint on the country variables. For each pair of consecutive country variables, add a table constraint that they be neighbors.

The solver contains a powerful deduction engine that will surely pick through the possibilities much faster than brute force or simple heuristics.

David Eisenstat0
Related