| Topic: |
Science > Physics |
| User: |
"The Lord of Chaos \Suresh Devanathan" |
| Date: |
22 Feb 2004 04:41:49 PM |
| Object: |
Re: P vs NP and the analog machine |
here's the most accurate way of saying it, but still not exactly correct.
The distribution of 'total costs' is gaussian. That would mean that i can
randomly generate k tour vectors, and there is a good chance that i would
get a tour vector that would be better than N!( 1- 1/k)
Assume that a_ij = a_ji , for the moment.
Now, one can build a distribution for a_ij. In other words, given a value
x, it has the probability p(x) dx of occuring in the matrix.
Now, there are N^2 elements in the matrix. Each row could be seen as
'sample' of the matrix. So, each row also obeys the distribution p(x) dx,
approximately.
Now, suppose a pick a minimum element along a row. Since the row is a
'sample' of the actual city matrix, it would be 'statistically equivalent'
to picking a minimum element on the entire matrix.
Now, N! is the total number of paths. However, our sample is restricted to
sqrt(N!) since number of elements on a given row is sqrt(N) where N is the
number of elements on the given matrix.
Another way of saying it is that the algorithm samples about sqrt(N!)
paths. However, since the sample,is a guassian with about the same variance
and average, the algorithm compares about N!( 1 - 1/sqrt(N!)) paths!.
The above 2 statements are what are to proved, to show why the algorithm
works.
-suresh
"The Lord of Chaos (Suresh Devanathan)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in message
news:c1alr0$1fetj4$1@ID-182852.news.uni-berlin.de...
Here's an interesting reason, why (how) the algorithm works
The distribution is gaussian. That would mean that i can randomly generate
k
vectors, and there is a good chance that i would get a vector that would
be
better than N!( 1- 1/k)
The algorithm, which is presented, could be seen in the following way.
Suppose, I generate a sample, with such that 'sum of the min edges' are
minimum in the sample, by virtue of that the distribution being gaussian,
i
am able to obtain a very good answer, very quickly.
I cannot exactly articulate myself correctly. But something along those
lines would be the right answer.
-suresh
"The Lord of Chaos (Suresh Devanathan)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in
message
news:c1al0v$1g978a$1@ID-182852.news.uni-berlin.de...
Right now, I cannot completely. Before I address that question. There is
a
lot more interesting and related question.
Since each path is equiprobable, suppose I randomly generate 100 paths,
since the distribution is gaussain, i, without trying too hard,
automatically, would have found a path that is almost always better than
N!(1-1/100)
Suppose, i randomly genrate 1000 paths, i would have found a path that
is
almost always better than N!(1-1/1000)
The algorithm, i have generated, is just a smarter version of, above
unguided random sampling algorithm. I havent found a way to communicate
this
idea, correctly, yet, but i am getting there.
-suresh
"Jim Nastos" <nastos@cs.ualberta.ca> wrote in message
news:Pine.LNX.4.44.0402220238190.18836-100000@eva117.cs.ualberta.ca...
On Sat, 21 Feb 2004, The Lord of Chaos (Suresh Devanathan) wrote:
From j to x, it finds an x, where a_jx is minimum. And from x, finds
b_xy
where y is minimum and so on and so forth.
There are other assumptions: one of them is that a_mn is unique and
that
a_mn= a_nm.
So you are essentially using a greedy heuristic and taking the
shortest
edge possible, which is a reasonable and a very common initial
strategy
to
TSP. There are much more sohpisticated ones used.
But you go further and claim that on a particular distribution of
edge
weights, this heuristic will yield an average result asymptotic to the
optimal path as N grows large. This would require some more proof.
Note that for any heuristic, one could always define a distribution
of
inputs on which that method performs well. Some would be quite
trivial,
of
course... your claim is on a significant and general Gaussian
distribution.
Can you formally write out a proof of this?
J
.
|
|
| User: "Jim Nastos" |
|
| Title: Re: P vs NP and the analog machine |
22 Feb 2004 07:46:43 PM |
|
|
On Sun, 22 Feb 2004, The Lord of Chaos (Suresh Devanathan) wrote:
Another way of saying it is that the algorithm samples about sqrt(N!)
paths. However, since the sample,is a guassian with about the same variance
and average, the algorithm compares about N!( 1 - 1/sqrt(N!)) paths!.
Wouldn't it be sufficient to say that the edge weights are uniformly
distributed over some interval of values, and then for large N, a
selection of N edges (to make a tour) would make such randomly chosen
tours have weights approximating a normal distributio?
J
.
|
|
|
| User: "The Lord of Chaos \Suresh Devanathan" |
|
| Title: Re: P vs NP and the analog machine |
23 Feb 2004 12:21:01 AM |
|
|
yes, but i want to say a couple of things. First of all, the algorithm isnt
limited to a_ij distributed uniformly. This is because, we are depending on
the properties of the central limit theorem.
Secondly,
Wouldn't it be sufficient to say that the edge weights are uniformly
distributed over some interval of values, and then for large N, a
selection of N edges (to make a tour) would make such randomly chosen
tours have weights approximating a normal distributio?
This is true. But i am not exactly talking about that. I will find better
words to explain later.
Anyways, do u get the idea?
"Jim Nastos" <nastos@cs.ualberta.ca> wrote in message
news:Pine.LNX.4.44.0402221839520.3775-100000@eva117.cs.ualberta.ca...
On Sun, 22 Feb 2004, The Lord of Chaos (Suresh Devanathan) wrote:
Another way of saying it is that the algorithm samples about sqrt(N!)
paths. However, since the sample,is a guassian with about the same
variance
and average, the algorithm compares about N!( 1 - 1/sqrt(N!)) paths!.
J
.
|
|
|
| User: "Jim Nastos" |
|
| Title: Re: P vs NP and the analog machine |
22 Feb 2004 09:37:12 PM |
|
|
On Sun, 22 Feb 2004, The Lord of Chaos (Suresh Devanathan) wrote:
Secondly,
Wouldn't it be sufficient to say that the edge weights are uniformly
distributed over some interval of values, and then for large N, a
selection of N edges (to make a tour) would make such randomly chosen
tours have weights approximating a normal distributio?
This is true. But i am not exactly talking about that. I will find better
words to explain later.
Anyways, do u get the idea?
Yeah, I think I get the idea, but my point was that (I think) you were
assuming the edge weights to be drawn from a gaussian distribution, and my
comment was suggesting that you could have the edge weights generated from
many other kinds of distributions as well.
J
.
|
|
|
| User: "The Lord of Chaos \Suresh Devanathan" |
|
| Title: Re: P vs NP and the analog machine |
23 Feb 2004 01:04:54 AM |
|
|
Btw, looking at the central limit theorem
the average approaches n \mu and the standard deviation approaches
\sqrt{n} \sigma
Taking the pecentage deviation of the tour costs \frac{\sqrt{n} \sigma}{n
\mu} = \frac{1}{\sqrt{n}} \frac{\sigma}{\mu}
In a way, it even gets pointless to look for a solution to the salesman
problem as n->infty, since all paths are approximately going to be equal.
Going along one path would equal all paths travelled!!!
-suresh
"Jim Nastos" <nastos@cs.ualberta.ca> wrote in message
news:Pine.LNX.4.44.0402222035280.4202-100000@eva117.cs.ualberta.ca...
On Sun, 22 Feb 2004, The Lord of Chaos (Suresh Devanathan) wrote:
Secondly,
Wouldn't it be sufficient to say that the edge weights are uniformly
distributed over some interval of values, and then for large N, a
selection of N edges (to make a tour) would make such randomly chosen
tours have weights approximating a normal distributio?
This is true. But i am not exactly talking about that. I will find
better
words to explain later.
Anyways, do u get the idea?
Yeah, I think I get the idea, but my point was that (I think) you were
assuming the edge weights to be drawn from a gaussian distribution, and my
comment was suggesting that you could have the edge weights generated from
many other kinds of distributions as well.
J
.
|
|
|
| User: "The Lord of Chaos \Suresh Devanathan" |
|
| Title: Re: P vs NP and the analog machine |
23 Feb 2004 01:07:12 AM |
|
|
What i m trying to say is that they will have about the same cost!!! Going
along one random path would have the same effect as going thru all the other
paths.
-suresh
"The Lord of Chaos (Suresh Devanathan)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in message
news:c1btk8$1gmnjr$1@ID-182852.news.uni-berlin.de...
Btw, looking at the central limit theorem
the average approaches n \mu and the standard deviation approaches
\sqrt{n} \sigma
Taking the pecentage deviation of the tour costs \frac{\sqrt{n}
\sigma}{n
\mu} = \frac{1}{\sqrt{n}} \frac{\sigma}{\mu}
In a way, it even gets pointless to look for a solution to the salesman
problem as n->infty, since all paths are approximately going to be equal.
Going along one path would equal all paths travelled!!!
-suresh
"Jim Nastos" <nastos@cs.ualberta.ca> wrote in message
news:Pine.LNX.4.44.0402222035280.4202-100000@eva117.cs.ualberta.ca...
On Sun, 22 Feb 2004, The Lord of Chaos (Suresh Devanathan) wrote:
Secondly,
Wouldn't it be sufficient to say that the edge weights are
uniformly
distributed over some interval of values, and then for large N, a
selection of N edges (to make a tour) would make such randomly
chosen
tours have weights approximating a normal distributio?
This is true. But i am not exactly talking about that. I will find
better
words to explain later.
Anyways, do u get the idea?
Yeah, I think I get the idea, but my point was that (I think) you were
assuming the edge weights to be drawn from a gaussian distribution, and
my
comment was suggesting that you could have the edge weights generated
from
many other kinds of distributions as well.
J
.
|
|
|
| User: "The Lord of Chaos \Suresh Devanathan" |
|
| Title: Re: P vs NP and the analog machine |
23 Feb 2004 01:21:42 AM |
|
|
This is one thing i can prove.
Take an element a_ij. Let x = a_ij Assume that x has the pdf p(x)
Now, the total cost along certain tour can written as
cost = \sum a_mn
Now, each a_mn also has the distribution p(x), by definition of p(x) .
From the distribution, we can calculate the \mu and \sigma
For a tour of length n,
The distribution of costs would have the mean (n) \mu and the standard
deviation \sqrt(n) \sigma
% deviation from the mean is \frac{\sqrt(n) \sigma}{ n \mu} =
\frac{1}{\sqrt{n}} \frac{\sigma}{\mu}
As n->infy, % deviation goes to 0. In a way, all paths "relatively" have
about the same n \mu
Of course, the proof makes implicit assumption that p(x) is not changing
with n.
Either, i have gone completely crazy, or have discovered something
completely interesting. It looks so deviously simple.
-suresh
.
|
|
|
| User: "The Lord of Chaos \Suresh Devanathan" |
|
| Title: Re: P vs NP and the analog machine |
23 Feb 2004 01:53:23 AM |
|
|
One more thing
although the % deviation = (standard deviation)/(average) goes to 0, the
deviation between the path with the least cost and the average cost doesnt.
It can be seen from the following analysis. The notation is sloppy
Let P(a) be probability of getting a value anything under a, given that a is
normally distributed.
P(a) = 1/N!
P ( (x - n \mu)/( \sqrt {2 n} \sigma) ) = 1/N!
For asymptocially small values P(a) would be about exp(-a^2)/ a
exp(-a^2)/ a = 1/N!
-a^2 = -log(N!)
a^2 = N (log N - 1)
a = sqrt(N) sqrt( log N - 1)
x - n\mu = \sqrt(2n) sqrt(N) sqrt( log N -1)
x = n \mu + n sqrt(2) sqrt( log N -1)
x/(n \mu) -> 1 + \frac{sqrt(2) sqrt( log N - 1)}{\mu}
It does us no good to find just the average one.
"The Lord of Chaos (Suresh Devanathan)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in message
news:c1bujo$1gmtka$1@ID-182852.news.uni-berlin.de...
This is one thing i can prove.
Take an element a_ij. Let x = a_ij Assume that x has the pdf p(x)
Now, the total cost along certain tour can written as
cost = \sum a_mn
Now, each a_mn also has the distribution p(x), by definition of p(x) .
From the distribution, we can calculate the \mu and \sigma
For a tour of length n,
The distribution of costs would have the mean (n) \mu and the standard
deviation \sqrt(n) \sigma
% deviation from the mean is \frac{\sqrt(n) \sigma}{ n \mu} =
\frac{1}{\sqrt{n}} \frac{\sigma}{\mu}
As n->infy, % deviation goes to 0. In a way, all paths "relatively" have
about the same n \mu
Of course, the proof makes implicit assumption that p(x) is not changing
with n.
Either, i have gone completely crazy, or have discovered something
completely interesting. It looks so deviously simple.
-suresh
.
|
|
|
| User: "The Lord of Chaos \Suresh Devanathan" |
|
| Title: Re: P vs NP and the analog machine |
23 Feb 2004 01:00:09 PM |
|
|
err
x - n\mu = +/- \sqrt(2n) \sigma sqrt(N) sqrt( log N -1)
x = n \mu +/- n sqrt(2) \sigma sqrt( log N -1)
x/(n \mu) -> 1 +/- \frac{sqrt(2) \sigma sqrt( log N - 1)}{\mu}
I will leave the math here.
"The Lord of Chaos (Suresh Devanathan)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in message
news:c1c0f5$1g7eb2$1@ID-182852.news.uni-berlin.de...
One more thing
although the % deviation = (standard deviation)/(average) goes to 0, the
deviation between the path with the least cost and the average cost
doesnt.
It can be seen from the following analysis. The notation is sloppy
Let P(a) be probability of getting a value anything under a, given that a
is
normally distributed.
P(a) = 1/N!
P ( (x - n \mu)/( \sqrt {2 n} \sigma) ) = 1/N!
For asymptocially small values P(a) would be about exp(-a^2)/ a
exp(-a^2)/ a = 1/N!
-a^2 = -log(N!)
a^2 = N (log N - 1)
a = sqrt(N) sqrt( log N - 1)
x - n\mu = \sqrt(2n) sqrt(N) sqrt( log N -1)
x = n \mu + n sqrt(2) sqrt( log N -1)
x/(n \mu) -> 1 + \frac{sqrt(2) sqrt( log N - 1)}{\mu}
It does us no good to find just the average one.
"The Lord of Chaos (Suresh Devanathan)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in
message
news:c1bujo$1gmtka$1@ID-182852.news.uni-berlin.de...
This is one thing i can prove.
Take an element a_ij. Let x = a_ij Assume that x has the pdf p(x)
Now, the total cost along certain tour can written as
cost = \sum a_mn
Now, each a_mn also has the distribution p(x), by definition of p(x) .
From the distribution, we can calculate the \mu and \sigma
For a tour of length n,
The distribution of costs would have the mean (n) \mu and the standard
deviation \sqrt(n) \sigma
% deviation from the mean is \frac{\sqrt(n) \sigma}{ n \mu} =
\frac{1}{\sqrt{n}} \frac{\sigma}{\mu}
As n->infy, % deviation goes to 0. In a way, all paths "relatively"
have
about the same n \mu
Of course, the proof makes implicit assumption that p(x) is not changing
with n.
Either, i have gone completely crazy, or have discovered something
completely interesting. It looks so deviously simple.
-suresh
.
|
|
|
| User: "Paul J." |
|
| Title: Re: P vs NP and the analog machine |
23 Feb 2004 07:05:26 PM |
|
|
"The Lord of Chaos \(Suresh Devanathan\)" <surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in message news:<c1d7hb$1hab3s$1@ID-182852.news.uni-berlin.de>...
err
x - n\mu = +/- \sqrt(2n) \sigma sqrt(N) sqrt( log N -1)
x = n \mu +/- n sqrt(2) \sigma sqrt( log N -1)
x/(n \mu) -> 1 +/- \frac{sqrt(2) \sigma sqrt( log N - 1)}{\mu}
I will leave the math here.
"The Lord of Chaos (Suresh Devanathan)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in message
news:c1c0f5$1g7eb2$1@ID-182852.news.uni-berlin.de...
One more thing
although the % deviation = (standard deviation)/(average) goes to 0, the
deviation between the path with the least cost and the average cost
doesnt.
It can be seen from the following analysis. The notation is sloppy
Let P(a) be probability of getting a value anything under a, given that a
is
normally distributed.
P(a) = 1/N!
P ( (x - n \mu)/( \sqrt {2 n} \sigma) ) = 1/N!
For asymptocially small values P(a) would be about exp(-a^2)/ a
exp(-a^2)/ a = 1/N!
-a^2 = -log(N!)
a^2 = N (log N - 1)
a = sqrt(N) sqrt( log N - 1)
x - n\mu = \sqrt(2n) sqrt(N) sqrt( log N -1)
x = n \mu + n sqrt(2) sqrt( log N -1)
x/(n \mu) -> 1 + \frac{sqrt(2) sqrt( log N - 1)}{\mu}
It does us no good to find just the average one.
"The Lord of Chaos (Suresh Devanathan)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in
message
news:c1bujo$1gmtka$1@ID-182852.news.uni-berlin.de...
This is one thing i can prove.
Take an element a_ij. Let x = a_ij Assume that x has the pdf p(x)
Now, the total cost along certain tour can written as
cost = \sum a_mn
Now, each a_mn also has the distribution p(x), by definition of p(x) .
From the distribution, we can calculate the \mu and \sigma
For a tour of length n,
The distribution of costs would have the mean (n) \mu and the standard
deviation \sqrt(n) \sigma
% deviation from the mean is \frac{\sqrt(n) \sigma}{ n \mu} =
\frac{1}{\sqrt{n}} \frac{\sigma}{\mu}
As n->infy, % deviation goes to 0. In a way, all paths "relatively"
have
about the same n \mu
Of course, the proof makes implicit assumption that p(x) is not changing
with n.
Either, i have gone completely crazy, or have discovered something
completely interesting. It looks so deviously simple.
-suresh
As n->infy, % deviation goes to 0. In a way, all paths "relatively"
have
about the same n \mu
This works for large N. However, let me back up a few steps. You are
assuming N! for all possible routes between some i and j (or k). This
assumption may be
wrong. To compute the possible paths of any length binomially we
should use
N!/((N-2)!) since we require just 2 vertices for each path. Going
further still, and assuming random distribution of path choice
probabilities, we could multiply our binomial by p^n * (p-1)^n-2 where
p should be 1/N.
I think your math, above, for 'normalization' was accurate, but let me
rephrase it for clarity (if not redundancy).
normalized = (random variable - finite mean) / standard deviation
where standard deviation can be calculated by:
sd = sqrt[ (1/n)*((n0^2)+(n1^2)+(n2^2...) - (average
expectation)^2 ]
In general, we could apply transitive closure (~composition) to find
the longest path lengths by assuming a fully converged (or total mesh)
and removing increasing path lengths by squaring over all the
relations (R^n). Where n=sqrt(nodes) should be a weak upper bound on
the total of squarings needed. In this way, the step which loses the
most paths is found to be contain the average path length.
.
|
|
|
| User: "The Lord of Chaos \Suresh Devanathan" |
|
| Title: Re: P vs NP and the analog machine |
24 Feb 2004 03:52:56 PM |
|
|
to it, i say blah.
I am not trying to insult you or anything. I am not a master in
combinatorics. The terms you are using, i have bare conception of.
References to definitions would help
-suresh
"Paul J." <it_paul_jay@hotmail.com> wrote in message
news:f0d73396.0402231705.2527106c@posting.google.com...
"The Lord of Chaos \(Suresh Devanathan\)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in message
news:<c1d7hb$1hab3s$1@ID-182852.news.uni-berlin.de>...
err
x - n\mu = +/- \sqrt(2n) \sigma sqrt(N) sqrt( log N -1)
x = n \mu +/- n sqrt(2) \sigma sqrt( log N -1)
x/(n \mu) -> 1 +/- \frac{sqrt(2) \sigma sqrt( log N - 1)}{\mu}
I will leave the math here.
"The Lord of Chaos (Suresh Devanathan)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in
message
news:c1c0f5$1g7eb2$1@ID-182852.news.uni-berlin.de...
One more thing
although the % deviation = (standard deviation)/(average) goes to 0,
the
deviation between the path with the least cost and the average cost
doesnt.
It can be seen from the following analysis. The notation is sloppy
Let P(a) be probability of getting a value anything under a, given
that a
is
normally distributed.
P(a) = 1/N!
P ( (x - n \mu)/( \sqrt {2 n} \sigma) ) = 1/N!
For asymptocially small values P(a) would be about exp(-a^2)/ a
exp(-a^2)/ a = 1/N!
-a^2 = -log(N!)
a^2 = N (log N - 1)
a = sqrt(N) sqrt( log N - 1)
x - n\mu = \sqrt(2n) sqrt(N) sqrt( log N -1)
x = n \mu + n sqrt(2) sqrt( log N -1)
x/(n \mu) -> 1 + \frac{sqrt(2) sqrt( log N - 1)}{\mu}
It does us no good to find just the average one.
"The Lord of Chaos (Suresh Devanathan)"
<surkum_removetheunderscore_here_dev_and_here_1@yahoo.com> wrote in
message
news:c1bujo$1gmtka$1@ID-182852.news.uni-berlin.de...
This is one thing i can prove.
Take an element a_ij. Let x = a_ij Assume that x has the pdf p(x)
Now, the total cost along certain tour can written as
cost = \sum a_mn
Now, each a_mn also has the distribution p(x), by definition of
p(x) .
From the distribution, we can calculate the \mu and \sigma
For a tour of length n,
The distribution of costs would have the mean (n) \mu and the
standard
deviation \sqrt(n) \sigma
% deviation from the mean is \frac{\sqrt(n) \sigma}{ n \mu} =
\frac{1}{\sqrt{n}} \frac{\sigma}{\mu}
As n->infy, % deviation goes to 0. In a way, all paths "relatively"
have
about the same n \mu
Of course, the proof makes implicit assumption that p(x) is not
changing
with n.
Either, i have gone completely crazy, or have discovered something
completely interesting. It looks so deviously simple.
-suresh
As n->infy, % deviation goes to 0. In a way, all paths "relatively"
have
about the same n \mu
This works for large N. However, let me back up a few steps. You are
assuming N! for all possible routes between some i and j (or k). This
assumption may be
wrong. To compute the possible paths of any length binomially we
should use
N!/((N-2)!) since we require just 2 vertices for each path. Going
further still, and assuming random distribution of path choice
probabilities, we could multiply our binomial by p^n * (p-1)^n-2 where
p should be 1/N.
I think your math, above, for 'normalization' was accurate, but let me
rephrase it for clarity (if not redundancy).
normalized = (random variable - finite mean) / standard deviation
where standard deviation can be calculated by:
sd = sqrt[ (1/n)*((n0^2)+(n1^2)+(n2^2...) - (average
expectation)^2 ]
In general, we could apply transitive closure (~composition) to find
the longest path lengths by assuming a fully converged (or total mesh)
and removing increasing path lengths by squaring over all the
relations (R^n). Where n=sqrt(nodes) should be a weak upper bound on
the total of squarings needed. In this way, the step which loses the
most paths is found to be contain the average path length.
.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Related Articles |
|
|
