|
LeftistMuslimObama posted:It's a weighted graph, but I need the distance only between a specific pair of nodes, rather than for all nodes. You mean all pairs of nodes. Yeah, still not O(E+V).
|
#
?
Jun 24, 2015 15:28
|
|
|
|
| # ? May 31, 2024 16:09 |
|
|
drat. Back to the drawing board then. If I used a simple BFS to just build a tree of all routes A to B, then traverse each branch of the tree summing edge weights, would that work? You're hitting everything twice there, but that's just a constant and you can drop it from the big o notation.
|
|
#
?
Jun 24, 2015 15:33
|
|
|
Dijkstra's algorithm is the best option there is (this problem's literally what it solved) and it's not O(E+V).
|
|
#
?
Jun 24, 2015 15:40
|
|
|
The homework is literally: You have a topographic map of elevations on roads between cities, given in adjacency list format. Given cities A and B, find the path between them with the lowest total elevation. The algorithm must run in linear time. I guess they're expecting us to make new discoveries in undergrad algorithms if Dijkstra is too slow here.
|
|
#
?
Jun 24, 2015 15:48
|
|
|
the best upper bound you can get out of Dijkstra's, if I remember right, is linearithmic time. To do this you need to use a particular implementation of a min-priority queue.
|
|
#
?
Jun 24, 2015 15:56
|
|
|
There's no such concept as "total elevation" of a journey. There's total elevation change, and there's maximum elevation, not to mention the trivially calculable net elevation change, but there isn't "total elevation."
|
|
#
?
Jun 24, 2015 16:26
|
|
|
sarehu posted:There's no such concept as "total elevation" of a journey. There's total elevation change, and there's maximum elevation, not to mention the trivially calculable net elevation change, but there isn't "total elevation." I think I misread it, and there might not even be a shortest-path component. This is the whole question: quote:You are given a topographical map that provides the maximum altitude along the He also just mentioned in an email that we should be using a divide and conquer approach. I think I was assuming I needed to do something with the sum of the edge weights because all the graph algorithms I know about deal with that in some way. In this case, I think I just need to pick the route where the highest edge weight is the lowest of the maximum edge weights amongst paths to the target. That leaves me with some pondering to do as to exactly how to split up the work into smaller problems, but at least I know what I actually need to do now.
|
|
#
?
Jun 24, 2015 16:44
|
|
|
nielsm posted:There is no "Express Community Edition", either you're on Express or you're on Community. Oh whoops. It's on the Express page and Express used to be free so I thought community was a version of that... Here's the link to emacs keybindings plugin for vs2013: http://stackoverflow.com/questions/13884953/emacs-keybindings-in-visual-studio-2012-or-2013 I've been changing the edition in the manifest file to "Express_All" this entire time.
|
|
#
?
Jun 24, 2015 18:28
|
|
|
OK, how does this solution sound: Depth first search. Base case of recursion is that we reach the target or there are no unvisited nodes to visit. Keep an auxiliary array that records the path with the current minimum elevation. Each time a new path is found, check its elevation against the recorded path and swap if it's lower. The worst case scenario visits some nodes and edges multiple times, but it's some constant multiplier of the number of nodes + edges, as each recursive call does constant-time work(add itself to the current path, do a comparison against the present max elevation on the path). I feel like I'm missing something still, but I think this is on the right track.
|
|
#
?
Jun 24, 2015 18:29
|
|
|
I would think elevation would be a property of the nodes, not the edges, and so the total elevation of a path is Elev(A) + Elev(B) + SUM(Elev(intermediate nodes)), which feels like at least a slightly different problem.
|
|
#
?
Jun 24, 2015 18:38
|
|
|
fritz posted:I would think elevation would be a property of the nodes, not the edges, and so the total elevation of a path is Elev(A) + Elev(B) + SUM(Elev(intermediate nodes)), which feels like at least a slightly different problem. No, as the problem specification says the elevation is the maximum elevation of the roads between cities (so the edges). I asked for clarification from the teacher and he said that we needed to return the path that has the lowest maximum elevation amongst its edges. No summing, averaging, or anything else of the edges required. Everywhere I'm looking shows DFS being O(E), and the additional processing I'm adding to each recursive call for path-recording and elevation-tracking is all constant-time work, so I think this solution works, unless someone swoops in here shouting "NO YOU FOOL". I'm finding a lot of my confusion in this class comes down to the teacher being a german grad student. His instructions aren't always super clear and he is overly fond of throwing around all the various math symbology that I know nothing about since I haven't taken a math class in over 8 years at this point.
|
|
#
?
Jun 24, 2015 19:04
|
|
|
LeftistMuslimObama posted:OK, how does this solution sound: I don't think this is quite right, or at least isn't clear to me. What do you do if the correct path requires edges that were in previously checked paths?
|
|
#
?
Jun 24, 2015 19:19
|
|
|
LeftistMuslimObama posted:OK, how does this solution sound: So here's what happens: you do a DFS. You end up recording some lowest-elevation path, i.e. one of the one-segment paths attached to your start node. Then you keep doing a DFS until you find the target node. Then you declare victory and announce that your one-segment path is the lowest... but that's not a path to the target node. Or if you returned your path to the target node, it's just some arbitrary path found by DFS, still no good.
|
|
#
?
Jun 24, 2015 20:32
|
|
|
^^^I'm thinking of the modified version of DFS where right before a recursive call returns, you throw away its list of visited nodes, so the parent recursive call can still visit nodes that were visited in the recursive call. It doesn't matter that this means that we could end up back at the neighbor we visited directly before, because for this problem the indirect route to the neighbor could be "better" than the direct one based on edge weights.Dr. Stab posted:I don't think this is quite right, or at least isn't clear to me. What do you do if the correct path requires edges that were in previously checked paths? Do you mean because I could have a partway complete path stored at each point? Each recursive call could store its index in the array that contains the current path so that I can just start over from there when I return to it and start exploring the next neighbor. The current "best" path would be copied into a separate array so it's pristine until a better one is found. So at recursive call n-1 the "cur" array could be {A,B,C,D} and the "curIndex" variable would store the integer 3. and then recursive call N explores vertex E so "cur" array is {A,B,C,D,E} and curIndex at this local level is 4. N returns (because E is the target) and cur is still {A,B,C,D,E}, but the local curIndex pointer points at D, so we make a new recursive call and pass in the index to start the path from, and D's next neighbor, K. K adds itself at curIndex+1 (and sets its own curIndex variable to that) so cur is now: {A,B,C,D,K} If K also has an edge to E, the recursive procedure is made again. If the edges from D-K and K-E are both lower max altitude than the one direct from D-E, and that was the highest edge before, we have a new best path and we copy the current state of the array into the best array. Does this make sense? All the work done in the recursive call is always going to be just copying stuff into and out of those two arrays, and since the arrays store vertices the work should be some constant * the number of vertices, so this shouldn't harm the linear running time of the DFS. The MUMPSorceress fucked around with this message at 20:44 on Jun 24, 2015 |
|
#
?
Jun 24, 2015 20:42
|
|
|
It's pretty weird that you'd be asked this because a linear time solution wasn't found until 1991.
|
|
#
?
Jun 24, 2015 20:45
|
|
|
LeftistMuslimObama posted:^^^I'm thinking of the modified version of DFS where right before a recursive call returns, you throw away its list of visited nodes, so the parent recursive call can still visit nodes that were visited in the recursive call. It doesn't matter that this means that we could end up back at the neighbor we visited directly before, because for this problem the indirect route to the neighbor could be "better" than the direct one based on edge weights. Then it's not linear time.
|
|
#
?
Jun 24, 2015 20:46
|
|
|
sarehu posted:It's pretty weird that you'd be asked this because a linear time solution wasn't found until 1991. Yeah, they seem to be offering a lot of assignments that require us to solve problems that either require absurdly high-level math knowledge or to recreate algorithms that were only recently discovered. It's hard enough that, with the curve he applied to everyone's awful grades, a 12/20 on the first homework was an A. If my DFS idea is bunk, then I'm at a loss as to how to proceed. I'm thinking there's something clever I could do by detecting if a node is about to visit a node that's already been visited and stealing the remainder of the paths from that node. That would suck for space because I'd need to store a structure with all of the paths out of each node and the worst elevation on that subpath, but that's basically memoization (isn't it?) and dynamic programming isn't on the syllabus until much later so I don't think they want us to self-invent memoization for this problem. He said a divide and conquer approach was optimal, but I'm at a total loss as to how in the heck you divide a graph in a way that can be meaningfully recombined.
|
|
#
?
Jun 24, 2015 20:55
|
|
|
Well, maybe 1991 is reasonable if it's not an intro class, which it sounds like it's not. The "divide and conquer" approach was good enough a hint for me. So... I recommend that you divide and conquer. I'm not telling you what to divide and conquer, but there's an obvious n log n solution if you do it right, and I'm guessing that some tools recently covered in class are the way to convert that to linear time.
|
|
#
?
Jun 24, 2015 21:24
|
|
|
sarehu posted:Well, maybe 1991 is reasonable if it's not an intro class, which it sounds like it's not. The "divide and conquer" approach was good enough a hint for me. So... I recommend that you divide and conquer. I'm not telling you what to divide and conquer, but there's an obvious n log n solution if you do it right, and I'm guessing there's a way to convert that to linear time that probably depends on tools that were covered recently in class. It actually is an intro class. It's undergrad algorithms. And the only tools that were discussed in class so far were DFS and BFS. I'll keep plugging away at it 
|
|
#
?
Jun 24, 2015 21:26
|
|
|
So my thoughts are that it's not necessarily a pathfinding problem. Given a minimal elevation path P between A and B, there exists some edge E such that all other edges in the path have an elevation less than or equal to E. This can also be extended to subgraphs so any connected subgraph containing A and B must contain an edge with elevation greater than or equal to E's elevation. If E is the highest elevation edge in the subgraph, then all paths between A and B are minimal elevation and you can pick an arbitrary one in linear time. Now the problem is just constructing such a subgraph. Constructing the subgraph should be pretty similar to Prim's algorithm except we always grow the subgraph by picking the lowest elevation edge pointing to a node not in the subgraph and never re-examine nodes once they're added to the subgraph. I'm not sure of the exact algorithm but something tracking the minimal elevation edge from any node in the graph to any particular node in the overall graph as a hashtable should keep it linear time.
|
|
#
?
Jun 25, 2015 01:32
|
|
|
Actually just got back from office hours with the ta and came up with something hilariously simple. Like, how the hell didn't I think of it. I'll describe it later when not phone posting.
|
|
#
?
Jun 25, 2015 02:47
|
|
|
1337JiveTurkey posted:So my thoughts are that it's not necessarily a pathfinding problem. Your solution won't work because (a) figuring out which node to connect to the graph (keeping track of which node has the smallest edge connecting it) will have logarithmic cost, (b) technically you want two subgraphs, one from A and one from B, and you finish once they're overlapping. (I.e. have one subgraph and stop when it's connected, but then you've got to worry about edges between your existing nodes, which is slightly different.) sarehu fucked around with this message at 03:17 on Jun 25, 2015 |
|
#
?
Jun 25, 2015 03:06
|
|
|
Also, if there was some way to grow your subgraph in linear time then you'd be able to adapt that algorithm to make yourself a linear time comparison-based sorting algorithm, by having a graph with one hub and many spokes of different edge weights.
|
|
#
?
Jun 25, 2015 03:16
|
|
|
Is there a library or corpus or something that people use for help disambiguating names? Obviously there's no closed-form solution but basically I want to be able to say that "James L. Smith", "J. L. Smith", "JL Smith", and "James Smith" are likely the same person, "J Smith" probably is too but not if there's also a "John Smith" in the list. (I'm trying to standardize author names in my personal academic literature database, a small enough sample that I can make those assumptions). I don't think it will be hard to do from scratch but this must be a common type of problem, maybe something's out there.
|
|
#
?
Jun 25, 2015 03:25
|
|
|
Note that in practice a modified Dijkstra's is going to wipe the floor with the linear algorithm despite being worst-case O(E + V lg V).
|
|
#
?
Jun 25, 2015 03:27
|
|
|
rjmccall posted:Note that in practice a modified Dijkstra's is going to wipe the floor with the linear algorithm despite being worst-case O(E + V lg V). Yep, obviously the problem is somewhat artificially constrained for learning purposes.
|
|
#
?
Jun 25, 2015 03:36
|
|
|
OK, here's my algorithm, after working with the TA. Note that he said we can just treat the vertex as a "magic box" in terms of stowing data: Start a DFS down to the target. In the base case, the procedure returns 0 if it's the target, -1 if it's not the target. For vertices that have no neighbors that reach the target just propagate the -1 up the tree. Otherwise the vertex has a a variable where it stores the current best value returned to it by a recursive call, and the vertex that returned that value. If another recursive call from that vertex returns a better max edge weight, the values are overwritten with the new one. When all neighbors are visited, the vertex returns the greater of the best (lowest) return value it's received or its own edge weight with the neighbor that returned the best edge weight. This is because we want the path with the lowest maximum edge weight, so the next vertex up needs to make its choice based on the worse of these two numbers. The current vertex has already determined the best path on from itself before returning. When all recursion is complete, just start walking the vertices based on their "best neighbor" variable and build your return list that way. This procedure multiple steps that are linear with E+V (actual DFS, number of potential comparisons at each level, final traversal to build a return), but these constitute a constant worst-case coefficient on the running time, so it's still overall O(E+V). I was 95% of the way here after Sarehu said "there's something obvious that I can't tell you". I was, however, passing a full list of the current best path all the way up the stack, and the TA pointed out that in terms of performance that's about the same as just doing a final traversal and the final traversal wastes less space/is slightly less complicated. I gotta say, this is the first problem in this class that was truly fun to consider. Probably because I wasn't staring at a big soup of Sigmas and geometry.
|
|
#
?
Jun 25, 2015 05:42
|
|
|
LeftistMuslimObama posted:It actually is an intro class. It's undergrad algorithms. And the only tools that were discussed in class so far were DFS and BFS. Is the lecturer a cyclist, he is trying to get from A to B with the least hills
|
|
#
?
Jun 25, 2015 05:50
|
|
|
TheresaJayne posted:Is the lecturer a cyclist, he is trying to get from A to B with the least hills But a cycle can't possibly be the best path in the graph! 
|
|
#
?
Jun 25, 2015 05:51
|
|
|
LeftistMuslimObama posted:OK, here's my algorithm, after working with the TA. Note that he said we can just treat the vertex as a "magic box" in terms of stowing data: Suppose you have a graph with four nodes, named A, B, C, and D. The starting node is A, and the destination node is D. The following edges exist, with their maximum altitudes: AB 2 AC 1 BC 1 BD 1 Your algorithm, where the depth first search visits neighbors in ascending alphabetical order, will compute the path ABD instead of ACBD.
|
|
#
?
Jun 25, 2015 06:46
|
|
|
sarehu posted:Suppose you have a graph with four nodes, named A, B, C, and D. The starting node is A, and the destination node is D. The following edges exist, with their maximum altitudes: I think the other tweak needed was to let vertices ask visited neighbors about their best path data and use it when deciding what to return.
|
|
#
?
Jun 25, 2015 07:04
|
|
|
LeftistMuslimObama posted:I think the other tweak needed was to let vertices ask visited neighbors about their best path data and use it when deciding what to return. So first C asks A for its best path data -- there is none because we haven't recursed back to A. Then, later, A asks C for its best path data, and there is none because when you were visiting C, no paths to D had been made yet.
|
|
#
?
Jun 25, 2015 07:25
|
|
|
sarehu posted:So first C asks A for its best path data -- there is none because we haven't recursed back to A. Then, later, A asks C for its best path data, and there is none because when you were visiting C, no paths to D had been made yet. I just drew myself a picture and I see exactly what you mean. I wonder why the TA liked the algorithm then  I'm trying to think of something clever, and drawing a blank. I do have the somewhat dumb idea of preferentially visiting the lowest-weighted edges first at each vertex, which fixes the specific case you describe. I can't think of any cases where that tweak would break. I just tried this solution out on my white board with a graph containing two cycles and it worked. I also tried it on this graph and it worked: Vertices A,B,C,D,E Edges: AB 5 AC 1 CD 2 BD 9 BE 1 Basically a square where A and B are adjacent but have a higher edge weight than A and C, but the only connection to E is from B. With a source of A and a target of B, this flavor starts by visiting C and recursively gets all the way to E, but then returns all the way back to A which then visits B (who already has its path to E info) and A is able to correctly switch over to AB as the best edge to take. Here's the algorithm from my original post: quote:Start a DFS down to the target. In the base case, the procedure returns 0 if it's the target, -1 if it's not the target. I would make the following changes: Visiting neighbors goes in order of smallest edge to greatest edge. If a vertex has already been marked as visited (but the current call didn't visit it), recursive call just asks the vertex to return its existing best-path data. I tried a couple more complicated scenarios too, where very long paths that lead into cycles are visited first (because the first edge weight in looked best), and I can't come up with anything that breaks using this logic. If I require that the adjacency list is ordered by edge weight instead of node label this should work. edit: drat, someone just showed me a case where it doesn't work: Nodes A B C D W Y Z Edges: AY 4 AC 3 CD 2 CW 2 WB 9 BY 1 BZ 1 DZ 7 In this graph, a goes to C first, which goes to D and then Z. C then goes to W which goes to B. Both of b's edges are 1, so it uses node label as a tiebreaker and goes to y (which is backward toward the source). Z is already visited, so it asks for best path data from Z, who says I'm the target. Now it unrolls all the way to A, which sees Y has been visited and asks it for best path data. Y doesn't have any because it was visited from B. The only solution I can think of is to let the "do you have data now?" query call all the way down the chain, but that could end up requerying the whole graph, which isn't linear to do. fake edit: OOOH, what about this? If a vertex finds a path to the target, it removes visited marks it made (and only it made) from any neighbors that didn't give it a path to the target? This should only unvisit vertices that can come back to B via completely unexplored parts of the graph, and since B doesn't need to make any further recursive calls, it shouldn't break the linearity. The same number of edges are still being queried overall. The MUMPSorceress fucked around with this message at 17:10 on Jun 25, 2015 |
|
#
?
Jun 25, 2015 16:43
|
|
|
Your algorithm has a complex interworking of two notions of visitation marking (the normal DFS marking and the vertex score), one of which you're now clearing under complex conditions. It's really difficult to reason about , and I'm not seeing any real effort to grapple with the basic flaw of a purely-locally-directed search here, which is that at given point in time you don't know anything about whether you've already found the best path to the current vertex or whether the best path from the current vertex to the target involves nodes you've already visited. In other words, I'm not seeing any properties of this search that would actually support a correctness argument. I can tell you straight off that no tweak to search edges in increasing order of cost is going to improve the correctness of a DFS-based traversal. Given a counter-example that the tweak helps with, I can always defeat the tweak by splitting the edge: instead of seeing edges [A->B, 5], [A->C, 4], and [A->D, 3], I see [A->B', 0], [A->C', 1], and [A->D', 2], and then there are edges [B'->B, 5], [C'->C, 4], and [D'->D, 3] that I don't see until I commit to a path. (Also, your problem statement does not let you cheaply search edges in order of increasing cost; you'd need to sort them first, and so a vertex with a θ(V) out-degree would affect your asymptotic complexity.) One condition that would actually establish correctness would be if you always knew the best path to a vertex by the time you visited it. To do this, you'd need to visit nodes in order of the cost of the best path to them from the origin; that's feasible, but it requires a priority queue that could get arbitrarily large, and so it's worst-case O(V lg V). Also it's basically Dijkstra's algorithm.
|
|
#
?
Jun 25, 2015 19:31
|
|
|
Why do most command-line utilities use either a dash or slash to precede switch arguments? Is that just to differentiate switches from other kinds of arguments?
|
|
#
?
Jun 25, 2015 22:13
|
|
|
sarehu posted:Your solution won't work because (a) A solution shouldn't need to sort, simply partition although that probably isn't compatible with growing the graph by following connections. (b) Meeting in the middle is possible but it should still work if you let one of the subgraphs simply consist of A or B. I did find a linear time algorithm for a spanning tree but that actually ends up with an arbitrary number of subgraphs. sarehu posted:Also, if there was some way to grow your subgraph in linear time then you'd be able to adapt that algorithm to make yourself a linear time comparison-based sorting algorithm, by having a graph with one hub and many spokes of different edge weights. Are you sure about that?  If you can find a minimal elevation path in linear time then you can trivially construct said subgraph in linear time by simply adding every edge whose elevation is less than or equal to that of the highest elevation edge in that path.
|
|
#
?
Jun 25, 2015 22:19
|
|
|
hooah posted:Why do most command-line utilities use either a dash or slash to precede switch arguments? Is that just to differentiate switches from other kinds of arguments? Yeah, it's to help distinguish between the arguments and their values. The specific character chosen is mostly convention, I think.
|
|
#
?
Jun 25, 2015 22:30
|
|
|
1337JiveTurkey posted:(a) A solution shouldn't need to sort, simply partition although that probably isn't compatible with growing the graph by following connections. You said we're picking the lowest elevation edge pointing to a node not in a subgraph, so you need to maintain that information. If you want it to be a partition, that would be different than what you said, and I guess you mean you just need to pick an edge less than some threshold. That's an interesting thing to do, but not a solution to the problem. 1337JiveTurkey posted:Are you sure about that? The fact that you could trivially construct the subgraph in linear time by some other mechanism doesn't mean that your mechanism constructs it in linear time.
|
|
#
?
Jun 25, 2015 22:45
|
|
|
rjmccall posted:Your algorithm has a complex interworking of two notions of visitation marking (the normal DFS marking and the vertex score), one of which you're now clearing under complex conditions. It's really difficult to reason about , and I'm not seeing any real effort to grapple with the basic flaw of a purely-locally-directed search here, which is that at given point in time you don't know anything about whether you've already found the best path to the current vertex or whether the best path from the current vertex to the target involves nodes you've already visited. In other words, I'm not seeing any properties of this search that would actually support a correctness argument. Yeah, I'm getting pretty frustrated with this assignment. Everything I can think of is just Dijkstra's algorithm, and the instructor insists there's a linear solution. The only other thing I can think of is a terrible hack, where I keep the dfs and maintain a bunch arrays holding the currently found best path from each vertex to the target. The TA hated that, so I don't think that'd the answer. Every time I think about how to divide and conquer this, it just keeps turning back into a dfs on me.
|
|
#
?
Jun 25, 2015 23:24
|
|
|
|
| # ? May 31, 2024 16:09 |
|
|
Not really a programming question, but I'm currently reading through Comer's Internetworking with TCP/IP for my networking II class, and I've run up against a problem I can't readily see a solution for; chapter 9, problem 9.5 reads:quote:9.5 Consider an Ethernet that has one conventional host, H, and 12 routers connected to it. I'm assuming the routers/host make up one sub-network; I had thought that perhaps one could broadcast a packet to prompt a bunch of ICMP redirect messages, using source routing, but ICMP redirect won't work if source routing is used, and that won't prompt a second message from each of the 12 routers in any case. Other errors won't work as (as far as I know) the source packet would be dropped once any other ICMP message other than a redirect is sent by a given router, so just broadcasting a frame with enough errors to cause an ICMP message won't work either. Echo request is similarly dropped once received and will only spawn one response per router if broadcast; I had though maybe I could use the Router Alert option, but I don't have a very clear idea of exactly how it processes the packet, so I'm not sure whether that would help at all here. Am I just missing something simple?
|
|
#
?
Jun 25, 2015 23:29
|
|