[algogeeks] Re: Bus routing algorithm
Hi, I guess this is standard graph theory problem. Treat your map as a directed graph. Give weight to each edge one for Cost of journet and another for running time. Give weight to each node as waiting time.. you can sum up the waiting time and running time for journey time calculation. My assumptions of Minimum cost and Journey are cost and journey between all the Bus Stations. Now apply All Pairs Shortest Path Algorith by having a cost martix. I am not much clear about the 3rd Requirement, 3. Min. the number of bus changes Please explain. On 6/17/08, Yingjie Xu [EMAIL PROTECTED] wrote: In fact it's the same if we give a measure to each edge... On Tue, Jun 17, 2008 at 7:23 AM, Gene [EMAIL PROTECTED] wrote: Your problem statement is incomplete. _What_ is to have min cost, min travel time, and/or min number of changes? On Jun 14, 11:09 pm, howa [EMAIL PROTECTED] wrote: Hi, Consider a map, with N bus stations, and there are total L bus lines operating on this set of stations 1. Each line follow a particular path, it might not be symmetric (i.e. the path from placeA= placeB might be different from placeB to placeA) 2. Some statations are shared by several lines; but not all lines will stop at a particular station 3. Different lines has different cost even from the same origin and destination, (i.e. Line 100. placeA = place B = $1USD, while for Line 101, placeA = placeB =$1.5USD) 4. Different lines of bus has different inter-arrival time (e.g. Line 100 need to wait 10 minutes in average, Line 101 need to wait 6 minutes in average) Now, you are requested to think of an algorithm, which get the 1. Min. cost 2. Min. traveling time (waiting time and running time) 3. Min. the number of bus changes What kind of algorithm should I explore if I want to solve the above problem? (If exact solution is not possible, are there any simpler implementations which should get some average-to-good result, e.g. GA algorithm?) Thanks -- If you received this communication by mistake, please don't forward it to anyone else (it may contain confidential or privileged information), please erase all copies of it, including all attachments, and please let the sender know it went to the wrong person. Thanks. -- PRADEEP MACHARLA www.ccpu.com --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Programing problem
Hi, if ( commnad sequence is bad ) whether to include it area calculation or not?? On 10/5/07, piruk [EMAIL PROTECTED] wrote: Hi. How to solve this task? Areameter is a turtle-like self-propelled vehicle controlled by sequences of commands transmitted over a radio channel. Initially the vehicle is oriented in some fixed direction, let's say to the North. Commands instruct Areameter how far to move in the current direction and where to turn after the move. Allowed turns are +90 or -90 degrees relative to the current direction. By positive turn we mean turning to the right (clockwise). A command sequence is good if it brings the vehicle to the starting point and starting orientation after tracing a closed non self- intersecting path. On coming back to the starting point Areameter should emits the area (number of square units) of the territory walked around. Write a program to perform Areameter's task of calculating the area from the sequence of received commands. Input The standard input stream contains a sequence of test cases specified as follows: The first line contains a positive integer n, number of test cases. A test case is simply one good command sequence spread over one or more lines. Each command sequence consists of alternating move and turn commands. Move command is represented by a positive integer; turn command is represented by single character '+' or '-'. End of command sequence is coded by giving 0 for move command. Commands are separated by at least one white-space character. You can assume the input is well-formed and contains only good command sequences. There are no a priori constraints on the sequence length. The values of moves and the resulting area are all within integer representation. Output For each test case the program should output one text line containing a number: the area in square units. Example Input 3 3 + 3 + 3 + 3 + 0 2 + 2 + 3 - 3 - 1 + 2 + 3 + 3 + 1 - 3 + 2 - 1 + 0 2 + 2 - 1 - 1 + 1 + 3 + 3 + 2 - 2 - 4 - 4 + 2 + 2 + 1 - 1 - 2 + 1 + 1 - 1 + 7 + 2 - 1 + 0 Output 9 16 27 -- PRADEEP MACHARLA Ph:08040141194 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Please Vote For TajMahal online voting 16days15Hpurs Left To vote
click www.new7wonders.com and vote online For Election of new 7 wonders, please vote for Taj Mahal and make it a wonder Your vote counts! Help make history... and vote as many number of times as possible. and make voting itself an history. -- PRADEEP MACHARLA Ph:09411121457 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---