ER was chock full of those kinds of takes moving from one actor to another walking through the ER to following a gurney into and around a trauma room or even bouncing between multiple traumas.
The more I think about this the more I think it's not the traveling salesman problem at all. Instead, it is more an optimization problem as the OP suggested. While it appears to be TSP, there are artificial restrictions imposed such that the weights on the edges are dependent on each other. More specifically, they are constrained by the triangle inequality theorem.
Assuming the graph consists of flowers for nodes and a straight (as the bee flies) line between them are the edges, the weights of the edges being the distance from one node to its neighbor, for any nodes a, b and c, the distance between a and c <= distance between a and b + the distance between b and c. This also assumes the optimal route (to a bee) between neighboring nodes is in fact a straight line.:-)
In your example, nodes a, b and c fit this theorem, however, the edge between b and d cannot be 1 and still fit. Since a-b is 2 and a-d is 5, b-d can be no less than 3. (a-d <= a-b + b-d) and also no more than 7...
Given the triangle inequality constraint, I'm thinking the greedy algorithm will still suffice to find the shortest path from a specific starting node to every other node in O(n^2) time. O(n^3) to find the shortest path from an arbitrary starting node. I think this constraint is what differentiates this problem from the typical TSP which has no such restriction. What are your thoughts?
The TSP deals with connected graphs in which there is at least one path from any one node to any other node.
A fully connected graph is a connected graph where there is a single edge connecting every node to every other node. The fully connected graph makes the the shortest path much easier to find simply using a greedy algorithm.
The difference in this case is that the starting point presumably is not arbitrary but predetermined. (closest to where the bee is released) The shortest path then does not necessarily have to be the actual shortest path through the graph but the shortest path from the given start point. The greedy algorithm will work for a complete graph but not the connected but not complete graph.
I believe the bee's have an advantage over the typical traveling salesman problem in that the bee's are finding the shortest path on a fully connected or complete graph. The traveling salesman problem is hard because the graph is not necessarily fully connected so all paths have to be examined individually. The bee presumably also has a predetermined starting node, the one closes to where it is released.
I believe the shortest path on a fully connected graph is found by always choosing the closest non-visited neighbor from the current node. The difference in calculation is O(n!) vs. O(n^2).
Actually, illegal file sharing had a huge part in the movie not making any money. People could see just how bad it sucked for free before shelling out the cash to see it suck in a theater.
The article doesn't expressly mention jailbroken phones. The patent does. It lists methods for distinguishing authorized users from unauthorized users.
The patent does not equate jailbreaking with "unauthorized user".
It is listed as one of several methods for "comparing the determined identity to the identity of one or more authorized users of the electronic device". Also listed among the "suspicious" activities is "removing a SIM card from the electronic device" which an authorized user is also allowed to do.
This is why we should be able to rate stories -1 Troll.
I agree. I come here for useful and interesting news stories reporting on actual news. Instead, lately we have to sift through all this kind of crap, dig through hundreds of "OHNOES!!" comments to find the one objective comment that explains the whole thing is FUD. Meanwhile, this front page story is indexed by Google helping spread misinformation.
This has nothing to do with Jailbroken phones. Where did the "anonymous reader" come up with that crap? From the first sentence in the abstract "This is generally directed to identifying unauthorized users of an electronic device." And nowhere in TFA does it say anything about Jailbroken phones. This is simply a twist on lojack.
The image of the "woman paying a bill online in her kitchen" was not likely owned by the Copyright Enforcement Group either but was licensed stock photography from somewhere else. Not only did they rip off CEG but also the owner of the stock image...
Slashdot Mirror
You can ship packages UPS Ground to Hawaii so why not?
ER was chock full of those kinds of takes moving from one actor to another walking through the ER to following a gurney into and around a trauma room or even bouncing between multiple traumas.
The only thing that is really needed to get by windows driver signing is an exploitable flaw in an existing signed driver.
That opinion WAS in TFA... if you had read it...
Ok, so the nearest neighbor is still an approximation and not necessarily the optimal solution.
I'll shut up now and learn from the masters. :-)
I don't know... I think the statement "will not allow the programmer to write insecure code" implies secure programming to me.
Damn, I love these kinds of brain teasers!
Of course... you are right.
The more I think about this the more I think it's not the traveling salesman problem at all. Instead, it is more an optimization problem as the OP suggested. While it appears to be TSP, there are artificial restrictions imposed such that the weights on the edges are dependent on each other. More specifically, they are constrained by the triangle inequality theorem.
Assuming the graph consists of flowers for nodes and a straight (as the bee flies) line between them are the edges, the weights of the edges being the distance from one node to its neighbor, for any nodes a, b and c, the distance between a and c <= distance between a and b + the distance between b and c. This also assumes the optimal route (to a bee) between neighboring nodes is in fact a straight line. :-)
In your example, nodes a, b and c fit this theorem, however, the edge between b and d cannot be 1 and still fit. Since a-b is 2 and a-d is 5, b-d can be no less than 3. (a-d <= a-b + b-d) and also no more than 7...
Given the triangle inequality constraint, I'm thinking the greedy algorithm will still suffice to find the shortest path from a specific starting node to every other node in O(n^2) time. O(n^3) to find the shortest path from an arbitrary starting node. I think this constraint is what differentiates this problem from the typical TSP which has no such restriction. What are your thoughts?
I didn't say anything about disconnected graphs.
The TSP deals with connected graphs in which there is at least one path from any one node to any other node.
A fully connected graph is a connected graph where there is a single edge connecting every node to every other node. The fully connected graph makes the the shortest path much easier to find simply using a greedy algorithm.
The difference in this case is that the starting point presumably is not arbitrary but predetermined. (closest to where the bee is released) The shortest path then does not necessarily have to be the actual shortest path through the graph but the shortest path from the given start point. The greedy algorithm will work for a complete graph but not the connected but not complete graph.
I believe the bee's have an advantage over the typical traveling salesman problem in that the bee's are finding the shortest path on a fully connected or complete graph. The traveling salesman problem is hard because the graph is not necessarily fully connected so all paths have to be examined individually. The bee presumably also has a predetermined starting node, the one closes to where it is released.
I believe the shortest path on a fully connected graph is found by always choosing the closest non-visited neighbor from the current node. The difference in calculation is O(n!) vs. O(n^2).
What will really blow your mind is that the same proof can be used to show that 0.333... is also equal to 1 and 0.6666... is also equal to 1.
This of course then makes 0.333... + 0.666... actually equal to 2.
Provided those bystanders are also construction workers.
It's called multi-level security.
No, that's defense-in-depth.
Yes, you are correct.
Though I've seen both those terms, along with multi-layer security, used interchangeably.
Exactly. It's called multi-level security. Desktop firewalls are not meant to replace server-based solutions but complement them.
which is like regular Hyper except on ADHD...
No, that would be plaid...
See, now that's insightful... but I've already posted and cannot mod as such...
Actually, illegal file sharing had a huge part in the movie not making any money. People could see just how bad it sucked for free before shelling out the cash to see it suck in a theater.
I seem to remember hearing of this one guy who bought up a bunch of swamp land in Florida and made a butt load of money... Count me in!!
Leave now and never come back!
The article doesn't expressly mention jailbroken phones. The patent does. It lists methods for distinguishing authorized users from unauthorized users.
The patent does not equate jailbreaking with "unauthorized user".
It is listed as one of several methods for "comparing the determined identity to the identity of one or more authorized users of the electronic device". Also listed among the "suspicious" activities is "removing a SIM card from the electronic device" which an authorized user is also allowed to do.
I agree. I come here for useful and interesting news stories reporting on actual news. Instead, lately we have to sift through all this kind of crap, dig through hundreds of "OHNOES!!" comments to find the one objective comment that explains the whole thing is FUD. Meanwhile, this front page story is indexed by Google helping spread misinformation.
This has nothing to do with Jailbroken phones. Where did the "anonymous reader" come up with that crap? From the first sentence in the abstract "This is generally directed to identifying unauthorized users of an electronic device." And nowhere in TFA does it say anything about Jailbroken phones. This is simply a twist on lojack.
Feel free to mod me into oblivion.
Nah... your post has more substance...
MAC addresses don't have anything to do with it since they are not really useful beyond your switch or router.
How typical... He with the most money wins! God our justice system needs an overhaul!
Oh wait... we won... nevermind!
The image of the "woman paying a bill online in her kitchen" was not likely owned by the Copyright Enforcement Group either but was licensed stock photography from somewhere else. Not only did they rip off CEG but also the owner of the stock image...