Mock CCC (WCC)

[bbi5291]

Say there are V vertices and E edges. No two connected vertices can be separated by a distance of more than V-1, so we may initially set all entries of a distance array to V, and then run our DFS. At each point we have the distance to the current vertex; we continue recursing only if this is less than the distance currently stored. Hence each vertex is visited at most V times, and an edge is traversed only when it would lead to a decrease in distance for a vertex, so no more than EV edge traversals can occur. I therefore claim that the runtime of DFS shortest-path is bounded by O(V(E+V)). Compare this however to BFS which runs in guaranteed O(E+V) time, and you can see which one is the obvious choice. However you can see that the running time is still strongly polynomial (and not exponential).

[A.J]

I agree with Brian. It is not exponential, however the runtime isn't formidable.

[chili5]

I get how the DFS applies to a graph. You check one path completely before checking another path. Is the concept the same with mazes?

Can someone point me at a good resource for DFS and BFS? Other than the turing tutorial here which I don't understand very well?

[A.J]

well, the tutorial here is actually quite good....however, if you would like, I would not mind explaining DFS/BFS to you

[saltpro15]

umm guys you lost me with this maze/graph talk...
My understanding is that BFS/DFS is used for questions like these
http://dwite.org/questions/shortest_path_around_v2.html
please correct me, I wish to learn
what is an example of a graph problem? like S3 of this year's CCC ?

[A.J]

@saltpro15 - You shouldn't only use DFS/BFS for questions like those. They have sooo many applications. For example, one example for using BFS is when you want to solve the slide puzzle (or the 8 puzzle, 15 puzzle, etc... it really depends on the size of the board). Your starting point is the current configuration of the board, and your goal is the required endstate. You can BFS outwards, by performing a move on the board (i.e. sliding the squares on the board) to get new configurations of the board, which you will then add to your FIFO queue (i.e. 'first in first out' queue).

As for DFS, there is a small variation of DFS, called DFSID (Depth First Search with Iterative Deepening). In essence it covers the same route BFS covers, but it has its benefits. It is basically DFS'ing to a certain 'depth'. DFSID is very useful when creating AI for games like Chess, where you have to deal with a bunch of moves.

Also, a bit more obvious application, is in graphs. The question you provided in the link, saltpro15, is a shortest path question; but what if the input isn't given to you as a grid, but as a graph (with nodes, edges, starting and ending points). You must first realize that for DFS/BFS to work for such a graph, the distance between any 2 nodes must be the same (otherwise DFS/BFS won't work). If the distances aren't the same, then maybe algorithms like Floyd-Warshall's or Dijkstra's will definitely come in handy (depending on the size of the input).

So, here are some of the other applications of DFS/BFS, saltpro15.

[saltpro15]

ok, thanks A.J. , you're basically my CS teacher now haha, I learned DP pretty much just from your DWITE work, good job

[A.J]

saltpro15 wrote:

ok, thanks A.J. , you're basically my CS teacher now haha, I learned DP pretty much just from your DWITE work, good job

That's flattering, thanks

[saltpro15]

no problem, you don't graduate this year do you? I still need to learn Dijkstra's lol

[saltpro15]

woo 500 bits!

ok that's the last of my off-topic-ness, did anyone ever get J4? I thought I almost had it until I realized I did it wrong, then gave up

[Analysis Mode]

There are four shortest path algorithms I use:

1) BFS (only in unweighted graphs) O(V+E)
2) Dijkstra's (in any graphs with no negative edge weights) O((E+V) log V) using a heap
3) Floyd-Warshall's (in any graph less then 100 vertices (because of it's time complexity O(V^3))
4) Bellman-Ford (in any graph with negative edge weights but no negative cycles ) O(VE)

It's essential to know the first three, but as for the last one, it isn't that prevalent. I've only had to code it because a problem required it (and it was worth points in my CS class).

And yes, the problem J5/S3 this year was indeed a graph theory problem. Floyd-Warshall's came in handy in the shortest path of it because:

1) It's faster and easier to code than BFS.
2) There were less than 100 people, so time wasn't a problem.

The other parts were basic operations on a graph (stored in an adjacency matrix due to small size). If the graph was bigger, I would've used an adjacency list, in which case I wouldn't have used Floyd's; most likely, my next choice would've been BFS.

Given this graph:

1
/ \
2 3
/ \ / \
4 5 6 7

DFS would visit the nodes in this order:

1, 2, 4, 2, 5, 2, 1, 3, 6, 3, 7, 3, 1 (note I'm including all backtracking)

BFS:

1, 2, 3, 4, 5, 6, 7

[A.J]

yes, thats true

Floyd Warshall was a good way to go for this years S3/J5

[chili5]

A.J @ Sat Mar 21, 2009 6:01 pm wrote:

well, the tutorial here is actually quite good....however, if you would like, I would not mind explaining DFS/BFS to you

That would be great! Maybe the tutorial is good, just I don't seem to understand.

[bbi5291]

A.J @ Sat Mar 21, 2009 7:05 pm wrote:

You shouldn't only use DFS/BFS for questions like those. They have sooo many applications. For example, one example for using BFS is when you want to solve the slide puzzle (or the 8 puzzle, 15 puzzle, etc... it really depends on the size of the board)

Yeah, for the 8 puzzle it's fine, because there are only (I think) 9!/2 = 181440 vertices and about four times as many edges. But for the 15 puzzle the state space is too large, and you're better off using A*, which is like Dijkstra's but uses a heuristic to guess which way to go next, in order to speed up the search. Consider that there are 16!/2 = 10461394944000 configurations and you'll see what I mean.

[A.J]

bbi5291 wrote:

A.J @ Sat Mar 21, 2009 7:05 pm wrote:

You shouldn't only use DFS/BFS for questions like those. They have sooo many applications. For example, one example for using BFS is when you want to solve the slide puzzle (or the 8 puzzle, 15 puzzle, etc... it really depends on the size of the board)

Yeah, for the 8 puzzle it's fine, because there are only (I think) 9!/2 = 181440 vertices and about four times as many edges. But for the 15 puzzle the state space is too large, and you're better off using A*, which is like Dijkstra's but uses a heuristic to guess which way to go next, in order to speed up the search. Consider that there are 16!/2 = 10461394944000 configurations and you'll see what I mean.

You are right, A* is optimal. However, BFS would also work, eventhough it is too slow. I just meant to give a couple of applications of BFS.