4
$\begingroup$

I've encountered scheduling problems in my algorithms class before like the type we use vertex cover to solve.

Recently I was asked this question and did not even know what algorithmic technique to use to answer it!

There are two trains, which run between stations and share a portion of track. For instance train 1 runs between stations A B C D E F G H and train 2 runs between stations I J K B C D E F L M so the trains share the track between B C D. At each end of the track the train turns around and goes the other way on its track. The trains go from station to station in 1 unit time. I need to prevent the trains from crashing head on on the shared track, I have the power to stop either train at any station and restart it again when I please.

How can I solve this problem without using a ton of if else clauses, what CS principles should I be using here?

edit

Some background, the first solution I wrote was just a simple check to see if the other train was on the shared track before sending the other train out. That seemed ad hoc to me and I'm sure it did to the company I interviewed for as well.

I figure there must be an algorithm or at least a school of thought for this type of problem, after all how do they build extensible systems for managing shared runway space at an airport, or managing traffic flow at stop lights.

My intuition is that this is a very introductory problem to a school of thought in computational problem solving I have not yet encountered.

I might be wrong, but could anybody clear the air for me?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ This problem is similar to mutual exclusion, with the common portion of tracks as a shared resource. One difference is that it is actually safe for both trains to be in the shared section if they are traveling in the same direction, provided that the trailing train is stopped at a station as long as the leading train has not yet left the next one. $\endgroup$
    – Klaus Draeger
    Commented Aug 21, 2015 at 14:55
  • 2
    $\begingroup$ shane, you say nowhere in the question that all stations must be served, or how often. For instance, one trivially safe solution is to have train 1 run its track, and start 2 when 1 arrives. When 2 finishes, start 1 for its tour back, and so on. You do not exclude such solutions, so it's not clear what your question is. $\endgroup$
    – Raphael
    Commented Aug 21, 2015 at 16:23
  • $\begingroup$ Hm, okay this was not noted in the original question either, however I assumed for practicality we want each train to run as much as possible (to avoid delays and provide good service). I understand now that this is a critical section, and perhaps the problem only goes as far as to identify what exactly the critical section is and block a train while that critical section is occupied, the critical section being when a train is on the critical section headed towards the other train. Perhaps this does not lend itself to such a discussion as I originally thought. $\endgroup$
    – shane
    Commented Aug 21, 2015 at 16:29
  • $\begingroup$ If you're looking for related work, it's worth mentioning that train scheduling itself is a fairly large, widely-studied filed. $\endgroup$
    – SamM
    Commented Feb 18, 2016 at 9:51

2 Answers 2

Reset to default
0
$\begingroup$

If you calculate the cycle, as there are only two trains and distance between every station is one, you could simply run them in order and appoint wait in some station to avoid crash.

If you have to implement some unfortunate events (first one stops for some reason, reschedule it to run on itd own time).

With two trains it will work without problems.

Otherwise use semaphores (it fits even literally ;)

There is no explicitly given synchronisation problem, so nasty trick works.

Improve this answer
$\endgroup$
0
$\begingroup$

A related and well studied area is threading/multiprocessing. Your initial solution is a simple lock; the critical section of tracks can only be used by one train at a time. To extend this while avoiding deadlocks (two trains waiting in each other) or starvation (a train waits forever), you would want to use some more sophisticated locking mechanism and scheduler.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This strikes me to be more of a comment than an answer. (Deadlocks clearly can't happen here, as every train can only ever wait on one shared portion of the track.) $\endgroup$
    – Raphael
    Commented Aug 21, 2015 at 8:13
  • $\begingroup$ @Raphael His question seems to be, "What techniques are used on similar problems, specifically extending to larger systems like airports and traffic lights?" $\endgroup$
    – Kittsil
    Commented Aug 21, 2015 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.