"everything from travel to mass transit to shipping", so the triangular relationship holds for my statement.
not necessarily. Is it always true that a flight from new york to boston to chicago is more expensive than a direct flight from new york to chicago?
I would be very surprized if airline flight prices satisfied it the triangle ineq.
"There is already a P partial solution to the travelling salesman. It does not find the best path, but it is proven that it finds at worst a path that's twice as long.
With a few heuristics, the worst case becomes very rare, and it usually finds something closer to the best solution"
Only in the METRIC case!
i.e. only if we can assume the distances satisfy the triangle inequality.
the distance from c to b is at most the distance from c to x to b
which i suppose might be reasonable--given reality.
uh hmmmmm
let me attempt to clear this up:
DFS--i.e. Depth First search (of graph) is something like O(n+m)
where n is the number of vertices(nodes) and m is the number of edges.
m is at most n(n+1)/2. so we can also say DFS is O(n^{3}).
But anyhow this just saying that DFS is polynomial in the size of the input!!
In other words if you have a graph G with n vertices we can then perform a depth first search on it in time O(n^{3}).
However This does not imply that you can solve sodoku in polynomial time.
The DFS algorithm for this would involve representing possible solutions for Sodoku as a graph, which would obviously have an exponential number of vertices--call this number h.
so when we run DFS on this graph , yes it runs in polytime with respect to h, i.e. Oh^{3}, but h itself is exponential with regard to the input of the original Sodoku problem
So in fact this DFS based algorithm is not polynomial!
However it is important that DFS is polynomial in the size of its input.
Slashdot Mirror
"everything from travel to mass transit to shipping", so the triangular relationship holds for my statement. not necessarily. Is it always true that a flight from new york to boston to chicago is more expensive than a direct flight from new york to chicago? I would be very surprized if airline flight prices satisfied it the triangle ineq.
"There is already a P partial solution to the travelling salesman. It does not find the best path, but it is proven that it finds at worst a path that's twice as long. With a few heuristics, the worst case becomes very rare, and it usually finds something closer to the best solution" Only in the METRIC case! i.e. only if we can assume the distances satisfy the triangle inequality. the distance from c to b is at most the distance from c to x to b which i suppose might be reasonable--given reality.
uh hmmmmm let me attempt to clear this up: DFS--i.e. Depth First search (of graph) is something like O(n+m) where n is the number of vertices(nodes) and m is the number of edges. m is at most n(n+1)/2. so we can also say DFS is O(n^{3}). But anyhow this just saying that DFS is polynomial in the size of the input!! In other words if you have a graph G with n vertices we can then perform a depth first search on it in time O(n^{3}). However This does not imply that you can solve sodoku in polynomial time. The DFS algorithm for this would involve representing possible solutions for Sodoku as a graph, which would obviously have an exponential number of vertices--call this number h. so when we run DFS on this graph , yes it runs in polytime with respect to h, i.e. Oh^{3}, but h itself is exponential with regard to the input of the original Sodoku problem So in fact this DFS based algorithm is not polynomial! However it is important that DFS is polynomial in the size of its input.
the thing is, they didnt call astronomy `telescope science'.