Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

best algorithm for given problem

shortest path

  • Please log in to reply
1 reply to this topic

#1 artartart

artartart

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 14 May 2008 - 06:39 AM

In the plane with integer coordinates, there are X start points and Y endpoints (X=Y). There are also some obstacles in the plane (unwalkable points). The task is to find path from each X to exactly one Y (each Y can be endpoint for exactly one X) such as the sum of all paths ar minimized.

The size of plane is 10^6 x 10^6, max number of start points is 20. There may be 200 rectangular obstacles. Time limit is 10 seconds, memory limit 4GB

I'm considering using A* algorithm to compute shortest paths from each X to each Y, but I'm afraid that it wont be sufficient couse 20x20 times use of A* could be a bit time consuming.

Maybe there is some better algorithm for finding paths from each X to each Y?

Posted Image

Edited by artartart, 14 May 2008 - 06:56 AM.

  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 14 May 2008 - 07:53 AM

You may want to find the closest Y for each X. If there are any conflicts, find the first and second closest Y for each X, look for a non-conflict mix. Repeat as necessary.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Also tagged with one or more of these keywords: shortest path

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download