| Author |
|
GM ThunderCat 
Moderator Group
GM
Joined: 11 Dec 2009
Location: Everywhere
Status: Offline
Points: 2157
|
 Posted: 25 Jan 2012 at 18:34 |
|
The phrase "capacitated vehicle routing problem with time windows" - brings back such lovely memories...
|
 |
Createure
Postmaster General
Joined: 07 Apr 2010
Location: uk
Status: Offline
Points: 1191
|
Posted: 25 Jan 2012 at 18:39 |
Also I just realised I was correct in the "very large" part of the number example but incorrect in saying it was a factorial thing - it does seem to be an exponential of some for looking at the straight line on a log-linear plot of the first few terms. If anyone wants to prove they are more switched on/than me today give me a mathematical description for the sequence that starts: 1, 2, 6, 20, 70, 252, 926 And I will give you 1,000 cows if you can do it - math teim.  p.s. the answer for n=100 is: 267823007376670171763904352500539254130289039388032841724230
|
|
Ander
Postmaster General
Joined: 24 Apr 2011
Status: Offline
Points: 1269
|
Posted: 25 Jan 2012 at 19:10 |
(2n!)/((n!)(n!))
500 cows to google and 500 to wikipedia 
|
|
Createure
Postmaster General
Joined: 07 Apr 2010
Location: uk
Status: Offline
Points: 1191
|
Posted: 25 Jan 2012 at 19:19 |
 Ander wrote:
(2n!)/((n!)(n!))
500 cows to google and 500 to wikipedia |
Nice try, not quite though. Assuming you meant (2n)! / 2*(n!) you get the sequence: 1 2 6 60 840 Or probably just a case of "wrongipedia" - answer is (2n)!/(n!)^2
Edited by Createure - 25 Jan 2012 at 19:32
|
|
Ander
Postmaster General
Joined: 24 Apr 2011
Status: Offline
Points: 1269
|
Posted: 25 Jan 2012 at 19:29 |
Why assumed 2*?  I meant (n!)*(n!). Since there is no option to write 'n! squared', I just chose to put it (n!)(n!)
I didnt mean to hijack the exciting thread. Too brainy for me. Please carry on you sparky folks!
Edited by Ander - 25 Jan 2012 at 19:33
|
|
lisao
New Poster
Joined: 23 Jan 2012
Status: Offline
Points: 10
|
Posted: 25 Jan 2012 at 19:29 |
It is twelve years since I did any pathfinding, it is a very fascinating problem. Easy on a casual look, but very complex if you have processor and/or memoryconstraints. The solution should be (2n!) / (2n!)^2. The central part of pascals triangle.
Edited by lisao - 25 Jan 2012 at 19:30
|
|
Createure
Postmaster General
Joined: 07 Apr 2010
Location: uk
Status: Offline
Points: 1191
|
Posted: 25 Jan 2012 at 19:34 |
| Why assumed 2*? I meant (n!)*(n!). |
Didn't really get to thinking about that part of it tbh - your mistake was (2n!) isn't (2n)! Just bracket confusion going on. TC seems very quietly confident about all this schabang. As I've just proved even relatively simple examples of pathfinding have the ability to confound people like me relatively rapidly when scaled up. Mucho respect.
Edited by Createure - 25 Jan 2012 at 19:42
|
|
Ander
Postmaster General
Joined: 24 Apr 2011
Status: Offline
Points: 1269
|
Posted: 25 Jan 2012 at 19:40 |
Createure wrote:
everyone is right... just bracket confusion.
|
No, lisao is wrong!
lisao wrote:
The solution should be (2n!) / (2n!)^2. The central part of pascals triangle. |
It should be (2n!) / (n!)^2
|
|
Nesse
Forum Warrior
Joined: 03 Oct 2010
Location: England
Status: Offline
Points: 406
|
Posted: 25 Jan 2012 at 20:25 |
|
No, you misunderstand me, Creature and Stormcrow!
What I am saying is NEVER MIND finding the closest, fastest or most direct route. That would not be the way it would be done in medieval times anyway. Instead, to go between ANY two points, not necessarily adjacent, choose one direction, until another direction is shorter. Or to make it even simpler, use only four directions. Then, going from (167,148) to (16,3) you would choose both
A) first the straight line from (167,148) to (167,3), then straight line (167,3) to (16,3)
or
B) first the straight line from (167,148) to (16,148), then straight line (16,148) to (16,3)
Then calculate which of those two is fastest (that's evaluating the terrain effects in 2*(151+145) squares, give or take four, but that should not take long, since the traveled route in all swuares except the end squares is exactly one square).
Oh, and then add the diagonals, making it marginally more difficult to find which two lines are "closest", and using traveled distance sqrt(2) per square for the diagonal.
But what would be fun would be using your own waypoints - maybe it would take research to establish the waypoint for caravans from that town?
|
|
Nesse
Forum Warrior
Joined: 03 Oct 2010
Location: England
Status: Offline
Points: 406
|
Posted: 25 Jan 2012 at 21:04 |
|
And yes, I get the pascal triangle bit too, but apart from not being the likely procedure for a caravan commander it is also too restrictive - you would like to travel in straight lines across same kind of terrain, turning at a well defined angle going from one terrain to another, rather than going stepwise square-by-square. There are obviously algorithms for that too, which I am sure Thundercat is infinitely (or at least n!) more familiar with than I am.
But what I'm trying to say is: don't overdo the "fastest" bit in fastest route! Also an extremely crude algorithm for finding a POSSIBLE route would be a good start and a welcome change from the flying caravans of today.
We, or at least I, would not expect my caravan drivers to do any better than stumbling along, and eventually getting there unless hijacked on the way. I might consider setting an ambush in a strategic position that wealthy caravans might pass, but interception I wouldn't even contemplate unless I had much faster units to send out to follow the enemy's footprints.
Edited by Nesse - 25 Jan 2012 at 21:05
|
|
Tweet
Pathfinding - how hard is it?
Topic Options