Time to finish route heuristic problem
Moderators: phlip, Moderators General, Prelates

 Posts: 115
 Joined: Wed Sep 23, 2009 10:52 pm UTC
Time to finish route heuristic problem
Say you're want to go from point a to point b which is comprised of X steps.
Let's say each step takes one second to complete and every step you have a constant chance (Y%) of being sent back to point a(you do not lose time being sent back). You do have the option of spending Z seconds and changing point a to your current position. You can do this an unlimited amount of times.
This is a general case, but for the sake of making a concrete example, let's say Y=5, z=5, and steps =100. How often then do you think Point A should be moved during the trip and during what intervals? How would you model this problem?
At the extremes, we could move Point A every single step we can take, but that would take ~520 seconds to do. The best case, would be if we never moved Point A and just ran through, that would take 100 second but the chance of that happening is .95^100~=.5%. Not too good odds. How would you set up this risk vs reward heuristic to get the best numbers on average?
Edit: Not hw, actually based on watching a SDA video of "pokemon yellow". Some guy ran through a cave without a single encounter but he did it segmented for the purposes of his sanity.
Let's say each step takes one second to complete and every step you have a constant chance (Y%) of being sent back to point a(you do not lose time being sent back). You do have the option of spending Z seconds and changing point a to your current position. You can do this an unlimited amount of times.
This is a general case, but for the sake of making a concrete example, let's say Y=5, z=5, and steps =100. How often then do you think Point A should be moved during the trip and during what intervals? How would you model this problem?
At the extremes, we could move Point A every single step we can take, but that would take ~520 seconds to do. The best case, would be if we never moved Point A and just ran through, that would take 100 second but the chance of that happening is .95^100~=.5%. Not too good odds. How would you set up this risk vs reward heuristic to get the best numbers on average?
Edit: Not hw, actually based on watching a SDA video of "pokemon yellow". Some guy ran through a cave without a single encounter but he did it segmented for the purposes of his sanity.
Re: Time to finish route heuristic problem
Suppose your policy is to move point A once you've moved by L steps. The probability of making it at least S steps in an individual attempt without getting sent back (0 <= S <= L) is (1Y)^{S}, so the average number of steps made per attempt is 1 + (1Y) + (1Y)^{2} + ... + (1Y)^{L1}, which can be rewritten as (1  (1Y)^{L})/Y. Since the probability of an attempt being successful is (1Y)^{L}, the average number of attempts made for the segment is (1Y)^{L}, and the average time taken for the segment is ((1Y)^{L}  1)/Y + Z. There are X/L segments to get through, so the total average time taken is X/L * (((1Y)^{L}  1)/Y + Z).
There is no possible formula for choosing L to minimize this time, unfortunately, so you just have to try different values to see which one is best.
There is no possible formula for choosing L to minimize this time, unfortunately, so you just have to try different values to see which one is best.
Re: Time to finish route heuristic problem
NINJA'd by Goplat  but he seems to be working solely from a "Save once and once only" standpoint, whereas I'm assuming an arbitrary number of saves. See below:
So in other words, you have a "start point", and "end point" and a "current position" between the two. Let's call the distance from the start point to the end point n, and the distance from the current position to the end point m  this is based solely on where the last "save" was made, and independent of where the original start point was, since we're assuming the probability of a "reset" on any given step is independent of all other factors.
We have a strategy S(m, n), that tells us whether to "save" depending on where we and the save point are relative to the end point, so we can calculate E(m, n  S)  the expected amount of time it will take you to get to the end point, given your strategy. Thankfully, because of the way this is set up, we can write that in a pretty straightforward way:
If S(m, n) = "save", then E(m, n  S) = t_save + E(m, m) < in other words, the time it takes us to put down a save point, plus the time we would expect to take given that we're now starting from that save point. Let's call this E_1(m, n)
If S(m, n) = "don't save", then E(m, n  S) = t_step + p E(n, n) + (1  p) E(m  1, n) < in other words, the time it takes to make the step, plus the contribution from having to go back to the start point times the probability of having to do so, plus the expected time it will take us from the next step onwards times the probability that we don't get sent back. Let's call this E_0(m, n)
Some things to note are:
* m <= n
* We can simplify by writing everything in terms of a single step time, i.e. t_step = 1 and t_save is calculated in terms of "step times".
* E(0, n) = 0, since once we reach the end point there will always be zero time left to reach the end point, independent of our strategy
So now what can we do? Well, we have a set of boundary conditions, so we can work backwards from them, adding in the assumption that we always want to minimise E(m, n  S)  so we want to choose S such that we place the save points at the best possible locations to minimise our expected time. In other words, S(m, n) = "save" when E_1(m, n) < E_0(m, n) and S(m, n) = "don't save" when E_1(m, n) > E_0(m, n). What happens if they're equal? It doesn't change our expected time, so we could pick a "better safe than sorry" option and always save in those cases, or we could go with "he who hesitates is lost" and never save. Since I am, by nature, a cautious person, I'll go with the former.
The first thing you can notice pretty quickly is that after we've saved, we will always take a step  we know we don't need to save again. So S(n, n) = "don't save" and E(n, n  S) = E_0(n, n) which we can use to show that E(n, n  S) = 1/(1p) + E(n1, n  S). And that means that E(1, 1  S) = 1/(1p), i.e. if there's only one step you need to take, the expected amount of time it will take you to get to the end point is the inverse of the probability that you successfully make the step without being sent back  which makes sense, so our formulas are working fine so far.
We can also go one step further, which is to say that E_1(1, n) = t_save + 1/(1p) < if we save on the last step, then the expected amount of time is just the time it takes to save plus the previously calculated expected time of taking one step.
At this point, it gets a little tricky since we have to essentially do a sort of twodimensional induction  the values E(m, n  S) depend directly on the other values for E(m', n  S) for 0 >= m' >= n, but also on E(m, n  1  S), so you have to do a bunch of manipulations between the various values of m at a given n, then feed those into the "next layer up" of n + 1. And those all depend on t_s and p.
I'll try to post some more on this later.
So in other words, you have a "start point", and "end point" and a "current position" between the two. Let's call the distance from the start point to the end point n, and the distance from the current position to the end point m  this is based solely on where the last "save" was made, and independent of where the original start point was, since we're assuming the probability of a "reset" on any given step is independent of all other factors.
We have a strategy S(m, n), that tells us whether to "save" depending on where we and the save point are relative to the end point, so we can calculate E(m, n  S)  the expected amount of time it will take you to get to the end point, given your strategy. Thankfully, because of the way this is set up, we can write that in a pretty straightforward way:
If S(m, n) = "save", then E(m, n  S) = t_save + E(m, m) < in other words, the time it takes us to put down a save point, plus the time we would expect to take given that we're now starting from that save point. Let's call this E_1(m, n)
If S(m, n) = "don't save", then E(m, n  S) = t_step + p E(n, n) + (1  p) E(m  1, n) < in other words, the time it takes to make the step, plus the contribution from having to go back to the start point times the probability of having to do so, plus the expected time it will take us from the next step onwards times the probability that we don't get sent back. Let's call this E_0(m, n)
Some things to note are:
* m <= n
* We can simplify by writing everything in terms of a single step time, i.e. t_step = 1 and t_save is calculated in terms of "step times".
* E(0, n) = 0, since once we reach the end point there will always be zero time left to reach the end point, independent of our strategy
So now what can we do? Well, we have a set of boundary conditions, so we can work backwards from them, adding in the assumption that we always want to minimise E(m, n  S)  so we want to choose S such that we place the save points at the best possible locations to minimise our expected time. In other words, S(m, n) = "save" when E_1(m, n) < E_0(m, n) and S(m, n) = "don't save" when E_1(m, n) > E_0(m, n). What happens if they're equal? It doesn't change our expected time, so we could pick a "better safe than sorry" option and always save in those cases, or we could go with "he who hesitates is lost" and never save. Since I am, by nature, a cautious person, I'll go with the former.
The first thing you can notice pretty quickly is that after we've saved, we will always take a step  we know we don't need to save again. So S(n, n) = "don't save" and E(n, n  S) = E_0(n, n) which we can use to show that E(n, n  S) = 1/(1p) + E(n1, n  S). And that means that E(1, 1  S) = 1/(1p), i.e. if there's only one step you need to take, the expected amount of time it will take you to get to the end point is the inverse of the probability that you successfully make the step without being sent back  which makes sense, so our formulas are working fine so far.
We can also go one step further, which is to say that E_1(1, n) = t_save + 1/(1p) < if we save on the last step, then the expected amount of time is just the time it takes to save plus the previously calculated expected time of taking one step.
At this point, it gets a little tricky since we have to essentially do a sort of twodimensional induction  the values E(m, n  S) depend directly on the other values for E(m', n  S) for 0 >= m' >= n, but also on E(m, n  1  S), so you have to do a bunch of manipulations between the various values of m at a given n, then feed those into the "next layer up" of n + 1. And those all depend on t_s and p.
I'll try to post some more on this later.
pollywog wrote:I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
Re: Time to finish route heuristic problem
Ok, the next piece of the puzzle is to realise that for the strategy S which minimises the expected times at all steps, E(m, n  S) <= E_0(m, n) and also E(m, n  S) <= E_1(m, n), with the equalities happening when we choose that relevant strategy.
For example, let's calculate S(m, 2) and E(m, 2  S) for m = 0, 1, 2. We know that:
* E(0, 2) = 0
* E(1, 1) = 1/(1p)
Also, E(n, n  S) = E_0(n, n) (i.e. never save twice) = 1 + pE(n, n  S) + (1  p)E(n  1, n  S) so E(n, n  S) = 1/(1  p) + E(n  1, n  S) and hence E(2, 2  S) = 1/(1  p) + E(1, 2  S)
E_1(1, 2  S) = t_save + E(1, 1  S) = t_save + 1/(1  p)
E_0(1, 2  S) = 1 + (1  p)E(0, 2  S) + pE(2, 2  S) = 1 + 0 + p(1/(1  p) + E(1, 2  S))
So now, using the first line of this post, we can save that E(1, 2  S) <= E_0(1, 2  S) = 1 + p/(1  p) + pE(1, 2  S) which implies that E(1, 2  S) <= 1/(1  p) + p/(1  p)^2, with equality when E_0 < E_1, which we can show happens when t_save >= p/(1  p)^2.
From that, we can then say that:
S(1, 2) = "save" if t_save <= p/(1  p)^2
And hence that:
E(1, 2  S) = t_save + 1/(1  p) if t_save <= p/(1  p)^2, or 1/(1  p) + p/(1  p)^2 otherwise.
And we also have:
E(2, 2  S) = 1/(1  p) + E(1, 2  S)
Past this, it looks like it gets into some nasty induction, which I'm not sure how well it can be simplified/automated. I'll keep on with it, just out of interest sake.
For example, let's calculate S(m, 2) and E(m, 2  S) for m = 0, 1, 2. We know that:
* E(0, 2) = 0
* E(1, 1) = 1/(1p)
Also, E(n, n  S) = E_0(n, n) (i.e. never save twice) = 1 + pE(n, n  S) + (1  p)E(n  1, n  S) so E(n, n  S) = 1/(1  p) + E(n  1, n  S) and hence E(2, 2  S) = 1/(1  p) + E(1, 2  S)
E_1(1, 2  S) = t_save + E(1, 1  S) = t_save + 1/(1  p)
E_0(1, 2  S) = 1 + (1  p)E(0, 2  S) + pE(2, 2  S) = 1 + 0 + p(1/(1  p) + E(1, 2  S))
So now, using the first line of this post, we can save that E(1, 2  S) <= E_0(1, 2  S) = 1 + p/(1  p) + pE(1, 2  S) which implies that E(1, 2  S) <= 1/(1  p) + p/(1  p)^2, with equality when E_0 < E_1, which we can show happens when t_save >= p/(1  p)^2.
From that, we can then say that:
S(1, 2) = "save" if t_save <= p/(1  p)^2
And hence that:
E(1, 2  S) = t_save + 1/(1  p) if t_save <= p/(1  p)^2, or 1/(1  p) + p/(1  p)^2 otherwise.
And we also have:
E(2, 2  S) = 1/(1  p) + E(1, 2  S)
Past this, it looks like it gets into some nasty induction, which I'm not sure how well it can be simplified/automated. I'll keep on with it, just out of interest sake.
pollywog wrote:I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
Re: Time to finish route heuristic problem
Actually, I assume saving with a fixed period (every L steps). This may not be quite optimal if L doesn't divide evenly into X (but if X is large it doesn't matter much).ConMan wrote:NINJA'd by Goplat  but he seems to be working solely from a "Save once and once only" standpoint, whereas I'm assuming an arbitrary number of saves. See below:
Re: Time to finish route heuristic problem
Goplat wrote:Actually, I assume saving with a fixed period (every L steps). This may not be quite optimal if L doesn't divide evenly into X (but if X is large it doesn't matter much).ConMan wrote:NINJA'd by Goplat  but he seems to be working solely from a "Save once and once only" standpoint, whereas I'm assuming an arbitrary number of saves. See below:
Ah, my mistake. Yes, you did make that assumption.
Anyway, to continue my crazy thoughts:
Under the optimal strategy, for every n there is an m which is the point at which you definitely save. As such, we can calculate a string of E_0's from E_0(n, n) up to the E_0(m, n) where it is greater than E_1(m, n), i.e. t_s + E_0(m, m). And I *think* that means you can, for each n, store a pair of values at a time  the m where the crossover occurs, and E_0(n, n). And, if you want, you can also store E_1(m, n) just to add them all together to get your final value. As such, E(m + 1, n  S) will equal E_0(m + 1, n  S) = 1 + (1  p)E(m, n  S) + pE(n, n  S) = 1 + (1  p)E_1(m, n) + pE_0(n, n) = 1 + (1  p)(t_save + E_0(m, m)) + p E_0(n, n) < so now we have our sequence of E_0(m', n) for m' between m and n, that relies only on alreadyknown p, t_save and E_0(m, m), and the asyetunknown E_0(n, n). Then we can cascade down, and try to solve for E_0(n, n) and m.
EDIT FOR MORE STUFF:
So, for some m, we can set E(m, n) = E_1(m, n) and then for m' > m, E(m, n) = E_0(m, n). Using a bit of induction (or breaking things down into geometric series), you can show that:
E_0(m + k, n) = [1  (1  p)^k]/p * [1 + p E_0(n, n)] + (1  p)^k * [t_save + E_0(m, m)]
And, from that, deduce that:
E_0(n, n) = 1/p * [(1  p)^(m  n)  1] + t_save + E_0(m, m)
The hard part is then working out what m is.
pollywog wrote:I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
 freakish777
 Posts: 354
 Joined: Wed Jul 13, 2011 2:14 pm UTC
Re: Time to finish route heuristic problem
@Goplat, that policy is nonoptimal. The closer you are to the destination, the less often you should make your current location the save point.
There should be some type of decaying frequency with which you save, like:
2, 4, 8, 16, 32, 64
Or whatever.
Say you have no save point, and are at position 99 (as per the initial post's numbers). Your chance of being sent back is 5%. You have:
Should yield an average time of 5.95 seconds to travel the last step. Compared to creating a save point (5 seconds) and moving (1 second), you're saving at least 0.05 seconds on average (not gonna bother with the percentage chance here).
So, with the initial posts numbers, my assumption is the because Y is so large, it would actually be optimal to create save points at almost all points, except perhaps the last handful.
Basically, you want to compute the average time it will take at each step, and compare with the average time of reaching the goal with creating the save point at the current position.
There should be some type of decaying frequency with which you save, like:
2, 4, 8, 16, 32, 64
Or whatever.
Say you have no save point, and are at position 99 (as per the initial post's numbers). Your chance of being sent back is 5%. You have:
 0.95 * 1 Second +
 0.05 *
 0.5 * 100 seconds + //go back only once
 0.5 *
 0.5 * 100 seconds + //go back twice
 0.5 *
 0.5 * 100 seconds + //go back 3 times
 0.5 *
 etc
Should yield an average time of 5.95 seconds to travel the last step. Compared to creating a save point (5 seconds) and moving (1 second), you're saving at least 0.05 seconds on average (not gonna bother with the percentage chance here).
So, with the initial posts numbers, my assumption is the because Y is so large, it would actually be optimal to create save points at almost all points, except perhaps the last handful.
Basically, you want to compute the average time it will take at each step, and compare with the average time of reaching the goal with creating the save point at the current position.
Re: Time to finish route heuristic problem
freakish777 wrote:@Goplat, that policy is nonoptimal. The closer you are to the destination, the less often you should make your current location the save point.
There's no difference between e.g. a 0to20 segment and an 80to100 segment. A segment of a particular length takes the same expected time to complete successfully no matter where it is, so there is no reason to prefer shorter segments near the beginning or longer segments near the end.
With the original numbers, the optimal segment length (in terms of time per distance covered) is 11. The best way to get to 100 is with eight 11length segments and one 12length; it will take 178.3 seconds on average.
If you get sent back, the probability that you won't go back any more isn't 0.5, it's 0.95^{100} ~ 0.006. Most likely you will go back many times.Say you have no save point, and are at position 99 (as per the initial post's numbers). Your chance of being sent back is 5%. You have:
 0.95 * 1 Second +
 0.05 *
 0.5 * 100 seconds + //go back only once
 freakish777
 Posts: 354
 Joined: Wed Jul 13, 2011 2:14 pm UTC
Re: Time to finish route heuristic problem
Goplat wrote:There's no difference between e.g. a 0to20 segment and an 80to100 segment.
Sure there there is. The 80100 segment is closer to the overall goal, making the expected value of creating a save point on any node in it less than the expected value of creating a save point on any node in the earlier segment.
If you get sent back, the probability that you won't go back any more isn't 0.5, it's 0.95^{100} ~ 0.006. Most likely you will go back many times.
My bad, I missed the percent sign in the opening post on the following:
.95^100~=.5%
That shouldn't change the fact that the expected value of a save point changes on each node and that there's optimal nodes to place them on (that don't follow a static frequency).
Re: Time to finish route heuristic problem
Talking about the expected value of creating a save point at a particular node is not a useful concept  it depends on both the previous save point you created and the next one you're going to create, so you can't consider nodes independently. If you've only decided you're going to save at 20, adding a save point at 10 is beneficial. If you've decided you're going to save at 9 and 11, adding a save point at 10 is a waste.freakish777 wrote:Goplat wrote:There's no difference between e.g. a 0to20 segment and an 80to100 segment.
Sure there there is. The 80100 segment is closer to the overall goal, making the expected value of creating a save point on any node in it less than the expected value of creating a save point on any node in the earlier segment.
If you don't believe me that save points should be spaced about uniformly, write a simulator and see for yourself. Or if you have Python, use mine. Try the different settings for savepts and see how they perform.
Code: Select all
import random
# Problem parameters
Y = 0.05
Z = 5
steps = 100
# Strategy
savepts = set((11, 22, 33, 44, 56, 67, 78, 89)) # Uniform spacing
#savepts = set((5, 10, 15, 20, 30, 40, 60, 80)) # More saves near beginning
#savepts = set((20, 40, 60, 70, 80, 85, 90, 95)) # More saves near end
trials = 1000
time = 0
for _ in xrange(trials):
pos = 0
save = 0
while pos < steps:
if pos > save and pos in savepts:
save = pos
time += Z
time += 1
pos += 1
if random.random() < Y:
pos = save
print "Average time:", time * 1.0 / trials
 freakish777
 Posts: 354
 Joined: Wed Jul 13, 2011 2:14 pm UTC
Re: Time to finish route heuristic problem
Then there shouldn't be any difference between the following?
savepts = set((12, 23, 34, 45, 56, 67, 78, 89)) # Uniform spacing, first point at 12, last point 11 away
savepts = set((11, 22, 33, 44, 55, 66, 77, 88)) # Uniform spacing, first point at 11, last point 12 away
When I increase the number of trials to 100,000 (really 100,000,000 would be nice for confidence in the results, but I don't have all day to let it run), I get 178.26135 for the second, and 178.3827 for the first.
savepts = set((10, 21, 32, 43, 54, 65, 76, 88)) # More points near beginning
Yielded 178.28684 (in between) and:
savepts = set((10, 20, 32, 45, 58, 72, 86)) # More saves near beginning, one less point
Yielded 179.8081 (about 1.5 seconds behind). All of this leads me to believe that 100 steps, 5% and 5 seconds are more restrictive compared to the general case.
Correct, it depends on the last time you saved, and how much farther you have to go. Like I said, start at your current position, calculate the average time it takes to get to the end from your current position (which is dependent on where you last saved), and compare it to the average time it takes to get to the goal if you create a save point at your current location.
The higher the number of steps there are until the finish, the higher the expected value of a save point.
The higher percentage chance of being sent back, the higher expected value of a save point.
The higher cost of creating the save point, the lower expected value of creating a save point.
These are all (obviously) true. However, one of these parameters changes while we're in the middle of the task (the steps left until the finish).
savepts = set((12, 23, 34, 45, 56, 67, 78, 89)) # Uniform spacing, first point at 12, last point 11 away
savepts = set((11, 22, 33, 44, 55, 66, 77, 88)) # Uniform spacing, first point at 11, last point 12 away
When I increase the number of trials to 100,000 (really 100,000,000 would be nice for confidence in the results, but I don't have all day to let it run), I get 178.26135 for the second, and 178.3827 for the first.
savepts = set((10, 21, 32, 43, 54, 65, 76, 88)) # More points near beginning
Yielded 178.28684 (in between) and:
savepts = set((10, 20, 32, 45, 58, 72, 86)) # More saves near beginning, one less point
Yielded 179.8081 (about 1.5 seconds behind). All of this leads me to believe that 100 steps, 5% and 5 seconds are more restrictive compared to the general case.
it depends on both the previous save point you created and the next one you're going to create, so you can't consider nodes independently. If you've only decided you're going to save at 20, adding a save point at 10 is beneficial. If you've decided you're going to save at 9 and 11, adding a save point at 10 is a waste.
Correct, it depends on the last time you saved, and how much farther you have to go. Like I said, start at your current position, calculate the average time it takes to get to the end from your current position (which is dependent on where you last saved), and compare it to the average time it takes to get to the goal if you create a save point at your current location.
The higher the number of steps there are until the finish, the higher the expected value of a save point.
The higher percentage chance of being sent back, the higher expected value of a save point.
The higher cost of creating the save point, the lower expected value of creating a save point.
These are all (obviously) true. However, one of these parameters changes while we're in the middle of the task (the steps left until the finish).
Re: Time to finish route heuristic problem
That's not a statistically significant difference. The standard deviation for individual trials is about 21, so for the average of 100000 trials it's about 21/sqrt(100000) = .066. The results deviate from my prediction (178.30626) by only 0.7 and 1.2 sigmas respectively.freakish777 wrote:Then there shouldn't be any difference between the following?
savepts = set((12, 23, 34, 45, 56, 67, 78, 89)) # Uniform spacing, first point at 12, last point 11 away
savepts = set((11, 22, 33, 44, 55, 66, 77, 88)) # Uniform spacing, first point at 11, last point 12 away
When I increase the number of trials to 100,000 (really 100,000,000 would be nice for confidence in the results, but I don't have all day to let it run), I get 178.26135 for the second, and 178.3827 for the first.
It depends on how much farther you have until the next save point, not your overall progress towards the goal.freakish777 wrote:it depends on both the previous save point you created and the next one you're going to create, so you can't consider nodes independently. If you've only decided you're going to save at 20, adding a save point at 10 is beneficial. If you've decided you're going to save at 9 and 11, adding a save point at 10 is a waste.
Correct, it depends on the last time you saved, and how much farther you have to go. Like I said, start at your current position, calculate the average time it takes to get to the end from your current position (which is dependent on where you last saved), and compare it to the average time it takes to get to the goal if you create a save point at your current location.
It seems you're thinking in terms of a "greedy algorithm" that neglects to take your own future actions into account. I move to 1, I save because saving at 1 is better than no saves at all. I move to 2, I save again because saving at 1 and 2 is better than saving at just 1. But this is already not optimal  my save at 2 subsumes almost all the benefit I got from saving at 1. If I was at 1 and already knew I was going to save at 2, I would have recognized that saving at 1 was wasteful and not bothered.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Time to finish route heuristic problem
Suppose our next save is going to be at location y, and we are at location x (a save point). We are only allowed one save point between x and y.
If we put a save at location z, we can work out the costbenefit of this save point relative to others.
Now, costs of a save at a given location are fixed. So other than deciding if we want that intermediate point, we can ignore costs to determine where the ideal point is between two given save points.
The argument from symmetry is pretty decent that it should be at the halfway point. The game of "get to the middle save point" and "get from the middle save point to the end point" are only determined by the length between the points. We'd need to throw in a convexity/concavity argument or something to prove that the average point is ideal. Suppose we have this lemma proven.
So we back up and look at a entire set of save points. Pretend we removed one, and wanted to replace it with a better one. In a nonuniform case, replacing one that isn't on the average location between its adjacent save points with one that is improves the time to win! So if nonuniform save points are ideal, it does have to be locally uniform.
Of course, we could short circuit this entire algorithm, and break our game down into a bunch of sub games. Each sub game is getting from one save point to the next. The time it takes to win, on average, is the sum of the average time in each save game! And with convexity of a certain sort, if any sub game is longer than another by 2, we can grow the short sub game and shrink the long sub game and end up with a shorter overall time. On top of this, the sum of sub games clearly doesn't care about the order the sub games where in on the original path. Between these two, we can construct a pretty robust proof that the ideal solution is with uniformly spaced saves, and a bias for longer/shorter saves at the start/end of the path does nothing, like my goggles...
(Note that the above just contains sketches of proofs, not the proofs themselves. I'm hoping it is convincing, nonetheless).
If we put a save at location z, we can work out the costbenefit of this save point relative to others.
Now, costs of a save at a given location are fixed. So other than deciding if we want that intermediate point, we can ignore costs to determine where the ideal point is between two given save points.
The argument from symmetry is pretty decent that it should be at the halfway point. The game of "get to the middle save point" and "get from the middle save point to the end point" are only determined by the length between the points. We'd need to throw in a convexity/concavity argument or something to prove that the average point is ideal. Suppose we have this lemma proven.
So we back up and look at a entire set of save points. Pretend we removed one, and wanted to replace it with a better one. In a nonuniform case, replacing one that isn't on the average location between its adjacent save points with one that is improves the time to win! So if nonuniform save points are ideal, it does have to be locally uniform.
Of course, we could short circuit this entire algorithm, and break our game down into a bunch of sub games. Each sub game is getting from one save point to the next. The time it takes to win, on average, is the sum of the average time in each save game! And with convexity of a certain sort, if any sub game is longer than another by 2, we can grow the short sub game and shrink the long sub game and end up with a shorter overall time. On top of this, the sum of sub games clearly doesn't care about the order the sub games where in on the original path. Between these two, we can construct a pretty robust proof that the ideal solution is with uniformly spaced saves, and a bias for longer/shorter saves at the start/end of the path does nothing, like my goggles...
(Note that the above just contains sketches of proofs, not the proofs themselves. I'm hoping it is convincing, nonetheless).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
 freakish777
 Posts: 354
 Joined: Wed Jul 13, 2011 2:14 pm UTC
Re: Time to finish route heuristic problem
Yakk wrote:Now, costs of a save at a given location are fixed.
I think your view of this as being a fixed cost only, may be skewing things. While the fixed cost is the same, there's an opportunity cost you end up paying later by not hedging your bets early.
Python 3.whatever code:
Code: Select all
import random
import itertools
# Problem parameters
Y = 0.05
Z = 5
steps = 100
i = 0
stepsActual = []
while i < steps:
i+=1
stepsActual.append(i)
j = 0
allCombinations5 = []
#At 12 save points, we have 160 seconds minimum, so the average can't possibly get better than the 178ish we're looking for
for L in range(0,12):
for savepts in itertools.combinations(stepsActual, L):
trials = 1000
time = 0
for _ in range(trials):
pos = 0
save = 0
while pos < steps:
if pos > save and pos in savepts:
save = pos
time += Z
time += 1
pos += 1
if random.random() < Y:
pos = save
if ((time * 1.0 / trials) < 179):
print(str(savepts) + '\t' + str(time * 1.0 / trials))
j += 1
if (j % 100000 == 0):
print(str(j) + ' combinations checked' + str(savepts))
I've modified the above, looking only in range 89 (since I had claimed I thought there was a good change at there being a series with 8 save points that outperformed the evenly spread one Goplat arrived at, and I also changed the number of trials from 1000 to 250 (both of these are to save time, so far my machine has completed 200,000 test combinations). The plan was to take the list of savepts it spits out and subject them to much larger trial sizes to get more accurate times.
Even at just the 100 choose 8, there's about 186,000,000,000 combinations to get through, so I don't think this will be completing any time soon.
It's entirely possible that biasing save points towards the beginning is too greedy in some way, and that evenly spread points are optimal, but I'm unconvinced thus far that evenly spread points are in fact optimal.
Anyone have access to a really fast machine??
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Time to finish route heuristic problem
I was doing a cost benefit analysis. The opportunity cost is factored in with the benefits.freakish777 wrote:I think your view of this as being a fixed cost only, may be skewing things. While the fixed cost is the same, there's an opportunity cost you end up paying later by not hedging your bets early.Yakk wrote:Now, costs of a save at a given location are fixed.
Opportunity cost is the "cost" of "benefits forgone by the choice". If I calculate the benefits for each possible decision, and the costs of each possible decision, then find the one with the highest (benefits)(costs), opportunity costs have been factored in already.
Do you have a valid objection to my reasoning? There are quite possibly flaws, but this doesn't look like one of them.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
 freakish777
 Posts: 354
 Joined: Wed Jul 13, 2011 2:14 pm UTC
Re: Time to finish route heuristic problem
Yakk wrote:I was doing a cost benefit analysis. The opportunity cost is factored in with the benefits.
Opportunity cost is the "cost" of "benefits forgone by the choice". If I calculate the benefits for each possible decision, and the costs of each possible decision, then find the one with the highest (benefits)(costs), opportunity costs have been factored in already.
Do you have a valid objection to my reasoning? There are quite possibly flaws, but this doesn't look like one of them.
Yes.
Yakk wrote:The time it takes to win, on average, is the sum of the average time in each save game!
Say you have uniform sub games (not uniform save points, but areas you've broken everything up into). I agree that you are looking to minimize the sum of these sub games to get the best possible time. However, if possible, we want to minimize the first sub game more than the other sub games. This is due to the fact that the first nodes will be the most visited. Obviously, we can't do this at such a high expense to the last nodes that they make us take longer.
The benefit forgone by the choice here is not repeating the first nodes over and over and over and over. Having a stable "each sub section of X nodes takes us the same amount of time" might actually be optimal, but it certainly doesn't seem optimal to me. If the first X nodes are capable of being minimized with 2 save points in them at the expense of the last 2X nodes taking longer, I think there exists the possibility of that being the optimal solution. Granted, it may not be, given the numbers we're using for this experiment (Y = 5%, Z = 5 seconds), and may only become evident when the time it takes to create a save point goes down, or the chance of being sent back goes up.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Time to finish route heuristic problem
No, you still aren't pointing out a flaw in my argument. I'll formalize it if it might help.
First, a simple lemma:
Lemma 1: Suppose you have two save points. When you add an additional save point, the optimal spot to place it (to minimize travel time between the two original save points) is the half way point.
I believe I sketched out why this is true in a previous post. Do you disagree with it?
This lemma builds on the previous one:
Lemma 2: If you have a length of with a save point at each end, and a save point somewhere in the middle, and no other save points, moving that save point to the middle of the interval will not increase the length of time it takes to go from one end of the interval to the other.
It is pretty easy to prove this using lemma 1. We simply remove the middle save point, and note that the most efficient spot to put it is in the middle, so it can't be worse than our original spot!
Lemma 3: The average time it takes to get from the start to the end of the track is the sum of the time it takes to get from the starting location, to save point 1, then save point 1 to save point 2, ..., then save point n to the end location.
Is this the one you are disagreeing with?
Lemma 4: A nonuniformly placed set of points is supoptimal (to the degree that you can make your points uniform). Or, a uniformly placed set of points is the optimal solution.
This follows pretty easily from 2 and 3. If we are nonuniformly placed, using #2 lets us find a better solution.
So, where do you disagree with my logic, explicitly? I'm aware that "it doesn't feel right" to you. That really isn't material.
First, a simple lemma:
Lemma 1: Suppose you have two save points. When you add an additional save point, the optimal spot to place it (to minimize travel time between the two original save points) is the half way point.
I believe I sketched out why this is true in a previous post. Do you disagree with it?
This lemma builds on the previous one:
Lemma 2: If you have a length of with a save point at each end, and a save point somewhere in the middle, and no other save points, moving that save point to the middle of the interval will not increase the length of time it takes to go from one end of the interval to the other.
It is pretty easy to prove this using lemma 1. We simply remove the middle save point, and note that the most efficient spot to put it is in the middle, so it can't be worse than our original spot!
Lemma 3: The average time it takes to get from the start to the end of the track is the sum of the time it takes to get from the starting location, to save point 1, then save point 1 to save point 2, ..., then save point n to the end location.
Is this the one you are disagreeing with?
Lemma 4: A nonuniformly placed set of points is supoptimal (to the degree that you can make your points uniform). Or, a uniformly placed set of points is the optimal solution.
This follows pretty easily from 2 and 3. If we are nonuniformly placed, using #2 lets us find a better solution.
So, where do you disagree with my logic, explicitly? I'm aware that "it doesn't feel right" to you. That really isn't material.
That possibility only exists if the proof sketched above isn't valid for some reason.I think there exists the possibility of that being the optimal solution.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Time to finish route heuristic problem
Goplat wrote:the average number of attempts made for the segment is (1Y)^{L}, and the average time taken for the segment is ((1Y)^{L}  1)/Y + Z.
First, I'm going to steal this. Average time to go S steps without saving (assuming you start on a save) is ((1Y)^{S}  1)/Y
For simplicity, let's let X be arbitrarily large.
Then assume that we went S steps from our closest save point.
Expected time to get to S+1 if you save at step S = Z + 1/(1Y)
Expected time to get to S+1 without saves = (1Y)*1 + Y*(((1Y)^{S1}  1)/Y) = (1Y)^{S1}  Y
For Y = .05 and Z = 5, expected time with saving = Z + 1/(1Y) = 5 + 1/.95 = 6.0526 seconds
For Y = .05 and Z = 5 and S = 34, expected time without saving = (1Y)^{S1}  Y = .95^{35}  .05 = 5.9711 seconds
For Y = .05 and Z = 5 and S = 35, expected time without saving = (1Y)^{S1}  Y = .95^{36}  .05 = 6.2880 seconds
So the optimal solution is to save every 35 steps if you're going forever. But the optimal steps when X = 100 seem to be close to 10/11. Can anyone spot an error in my math? Because I sure can't.
Dashboard Confessional wrote:I want to give you whatever you need. What is it you need? Is it within me?
Avatar by Matt
 freakish777
 Posts: 354
 Joined: Wed Jul 13, 2011 2:14 pm UTC
Re: Time to finish route heuristic problem
Yakk wrote:No, you still aren't pointing out a flaw in my argument. I'll formalize it if it might help.
First, a simple lemma:
Lemma 1: Suppose you have two save points. When you add an additional save point, the optimal spot to place it (to minimize travel time between the two original save points) is the half way point.
I believe I sketched out why this is true in a previous post. Do you disagree with it?
Why is this obviously true?
Essentially I'm not seeing how this is so obvious that we can assume it to be true and base the rest of an argument off of that.
 freakish777
 Posts: 354
 Joined: Wed Jul 13, 2011 2:14 pm UTC
Re: Time to finish route heuristic problem
Snark wrote:Goplat wrote:the average number of attempts made for the segment is (1Y)^{L}, and the average time taken for the segment is ((1Y)^{L}  1)/Y + Z.
First, I'm going to steal this. Average time to go S steps without saving (assuming you start on a save) is ((1Y)^{S}  1)/Y
For simplicity, let's let X be arbitrarily large.
Then assume that we went S steps from our closest save point.
Expected time to get to S+1 if you save at step S = Z + 1/(1Y)
Expected time to get to S+1 without saves = (1Y)*1 + Y*(((1Y)^{S1}  1)/Y) = (1Y)^{S1}  Y
For Y = .05 and Z = 5, expected time with saving = Z + 1/(1Y) = 5 + 1/.95 = 6.0526 seconds
For Y = .05 and Z = 5 and S = 34, expected time without saving = (1Y)^{S1}  Y = .95^{35}  .05 = 5.9711 seconds
For Y = .05 and Z = 5 and S = 35, expected time without saving = (1Y)^{S1}  Y = .95^{36}  .05 = 6.2880 seconds
So the optimal solution is to save every 35 steps if you're going forever. But the optimal steps when X = 100 seem to be close to 10/11. Can anyone spot an error in my math? Because I sure can't.
Assuming equal spacing is in fact optimal, it doesn't make sense that there should be a difference for how many nodes to travel between "going for set distance X" and "going forever." Going forever can logically be broken up into optimizing "going for set distance X" over and over again (if 11 is the optimal number, then X should be a multiple of 11, to avoid small inaccuracies of accidentally stretching (to 12)/compressing (to 10) a section in between 2 save points).
Re: Time to finish route heuristic problem
freakish777 wrote:Snark wrote:Goplat wrote:the average number of attempts made for the segment is (1Y)^{L}, and the average time taken for the segment is ((1Y)^{L}  1)/Y + Z.
First, I'm going to steal this. Average time to go S steps without saving (assuming you start on a save) is ((1Y)^{S}  1)/Y
For simplicity, let's let X be arbitrarily large.
Then assume that we went S steps from our closest save point.
Expected time to get to S+1 if you save at step S = Z + 1/(1Y)
Expected time to get to S+1 without saves = (1Y)*1 + Y*(((1Y)^{S1}  1)/Y) = (1Y)^{S1}  Y
For Y = .05 and Z = 5, expected time with saving = Z + 1/(1Y) = 5 + 1/.95 = 6.0526 seconds
For Y = .05 and Z = 5 and S = 34, expected time without saving = (1Y)^{S1}  Y = .95^{35}  .05 = 5.9711 seconds
For Y = .05 and Z = 5 and S = 35, expected time without saving = (1Y)^{S1}  Y = .95^{36}  .05 = 6.2880 seconds
So the optimal solution is to save every 35 steps if you're going forever. But the optimal steps when X = 100 seem to be close to 10/11. Can anyone spot an error in my math? Because I sure can't.
Assuming equal spacing is in fact optimal, it doesn't make sense that there should be a difference for how many nodes to travel between "going for set distance X" and "going forever." Going forever can logically be broken up into optimizing "going for set distance X" over and over again (if 11 is the optimal number, then X should be a multiple of 11, to avoid small inaccuracies of accidentally stretching (to 12)/compressing (to 10) a section in between 2 save points).
I agree they should be similar despite the size of X, but the maths seem to indicate that a length around 35 is optimal while trial and error show that this is not the case (that 10/11 is optimal).
Dashboard Confessional wrote:I want to give you whatever you need. What is it you need? Is it within me?
Avatar by Matt
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Time to finish route heuristic problem
freakish777 wrote:Why is this obviously true?Yakk wrote:No, you still aren't pointing out a flaw in my argument. I'll formalize it if it might help.
First, a simple lemma:
Lemma 1: Suppose you have two save points. When you add an additional save point, the optimal spot to place it (to minimize travel time between the two original save points) is the half way point.
I believe I sketched out why this is true in a previous post. Do you disagree with it?
Essentially I'm not seeing how this is so obvious that we can assume it to be true and base the rest of an argument off of that.
I believe I sketched out why it is true in a previous post. Namely:
I can make this sketch of a proof explicit if you'd like.Suppose our next save is going to be at location y, and we are at location x (a save point). We are only allowed one save point between x and y.
If we put a save at location z, we can work out the costbenefit of this save point relative to others.
Now, costs of a save at a given location are fixed. So other than deciding if we want that intermediate point, we can ignore costs to determine where the ideal point is between two given save points.
The argument from symmetry is pretty decent that it should be at the halfway point. The game of "get to the middle save point" and "get from the middle save point to the end point" are only determined by the length between the points. We'd need to throw in a convexity/concavity argument or something to prove that the average point is ideal.
We have n steps, and our goal is to minimize the time to reach step n.
Let T(z) be the time it takes, on average, to go from one save point to another one z steps away. Then if we have a gap of length n in which we put a single point z, the average time it takes to finish is T(z) + T(nz). Clearly this is symmetric around n/2.
Suppose T(z) is convex up. Then T(lambda z) >= lambda T(z) (the definition of convex up)
Examine T( z / (n/2) * n/2 ) + T ( (nz)/(n/2) * (n/2) ) >= (2z/n) + 2(nz)/n) * T(n/2) = 2 T(n/2)
This means that the minimal point of T(z) is at z = n/2.
Now, for odd n, this requires filling in the blanks between the points  but a linear interpolation between points is sufficient.
So all we have to show is that the time it takes to get to a save point z steps away is convex up.
Lemma 0: The time it takes to get to save point z steps away is convex up.
Do you see how Lemma 1 follows from 0?
That is what I meant by "you can prove this via symmetry and an argument from convexity", done a bit more formally.
The time it takes to go z steps to the next save has been covered by other posters in this thread.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Who is online
Users browsing this forum: No registered users and 5 guests