Tuesday, January 19, 2010
The Tourist Problem
Prologue: The Tourist Problem was "my invention" way-back in June 1987 when I first came to NUS, Singapore. They are the first set of transparencies I wrote for the course "CS203: Data Structures". Since then, I have used it for a large variety of settings. Recently, I moved it to powerpoint, updated it, added "Hands-On-Activities" and more pedagogical enhancements.
In Week 2 of UIT2201, I covered a fast-track version of "The Tourist Problem".
The Big Picture: The big goal is to illustrate computational problem solving in computer science, problem statement, problem analysis, problem modelling, problem solving and so on.
Along the way, I wanted to illustrate several things -- (a) asking questions, (b) giving simple, obvious solutions where they exists, and (c) analyzing the solutions; (c) asking more questions to address the problems, and so on. The point is that, if we keep doing this, then at some point, we arrive at interesting version of the problem and can work on interesting solutions.
And, I wanted to debunk the myth that to do interesting computer science, you must do programming.
The Specifics: After sufficient modeling, the problem of scheduling bus trips for the tourists is modelled as a graph colouring problem. (...post to be continued...)
Subscribe to:
Post Comments (Atom)
hey everyone! Two thoughts struck me after Friday's tutorial.
ReplyDelete1. About the Youtube video, I was thinking that increaing the length of the bar could make the bending more easily. Theoretically, if the the bar is infinitely long, then the force to break it will be infinitely small.
2. When I was looking at the 'job question' in T2, I thought 'Hmm, what if these guys could do multi-tasking'. Of course, there's no limit on the number of jobs one could do at the same time, it would be meaningless since we just need one worker to do all the job. I asked prof and he motivated me to think about it. So i did and realized something, I think, is meaningful and relevant to reality. Say, we allow one worker to do at most two jobs at the same time or one tourist visit at most two places in one day etc, which is closer to reality. I then wondered if we could still use the coloring method and came up with some ideas. let me use the tourist problem to elaborate more. Suppose one tourist can visit two places in one day and we still want to find out the min days, in that case, the vertices could denote a pair of places and the edge denotes a conflict between two pairs. To be more specific, eg. we now have four pairs of places AB CD EF GH, then AB and CD would have an edge in between if a tourist wants to visit both B and D. In order to find the min days, the key is to choose the pairs carefully, for example, a sensible decison would be to put vivocity and orchard road together etc...of course, in that case, we may have to do more experiments to find the optimal answer and a systematic solution/algorithm would be more difficult to find. Nevertheless, the coloring method still works even when we allow one tourist to visit 3 or more places in one day....
Just my cents worth =)