← 13ps-06 A Better Tree Solution

• 1 Follower
• 44 Lines

Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=dgrMaH-U_JU" data-team="udacity"></div> ``` 1 Language

Showing Revision 1 created 10/24/2012 by Amara Bot.

1. All right, so let's take a look at how I decide to do this.
2. Like I said, you set up a second vertex called u and set it to equal to -1.
3. In other words, it's not set to any actual vertex in the graph at first.
4. So for every single element in the upper triangular portion of the adjacency matrix
5. since we're presenting this as an adjacency matrix,
6. we check if there is an edge between those two vertices between vertices I and J.
7. And if there is, then we check if the assignment for I and J is zero
8. that is they're not none anymore, we have specifically set them to not be in the assignment.
9. Well, if both of them are explicitly out of the assignment and there's an edge between them
10. well then that's not going to be a valid vertex cover, so we return float infinity.
11. Now, otherwise, if we find that the assignment for both I and J is equal to none,
12. then that means we haven't actually look at this yet, so it's a good candidate for setting v and u--
13. so that we set u equal i and v equal to j and we continue on.
14. Now, once we go through the entire double for loop, we check if v is still on set.
15. If v is still on set, that means first of all we didn't fall out of this by not having a valid vertex cover
16. and second of all, it means that all the vertices have been assigned to something rather
17. because that's the only way that v could still be set to -1
18. and if v is set to -1, then note that u also is.
19. Now, if that's the case, then we set a variable size equal to zero
20. and we start simply counting up all of the different vertices in the assignment.
21. If the vertex is set in the assignment, then we increment size.
22. It it's still unset, well then we have to do a little bit of manipulation here.
23. We'll just set the vertex i to 1 if a neighbor is zero
24. because we want to make sure that this is still a valid vertex cover.
25. So, for every j in range i--well, I just realized I put an i in here.
26. Well, then there are unnecessary just a slight inefficiency,
27. you can boost this to i+1 since we don't allow any loops in the graph.
28. If we did, then we would have to simply use i but this doesn't really particularly matter for this.
29. Moving on, so for every other vertex in the graph, we check if there is an edge between i and j again
30. and if there is and if the assignment of j is zero, well then, we have to set i
31. and we say that the size is an additional element because we now have to set i,
32. and once we go through all this, we return the size and that's done.
33. Now, for each of these for the recursive part that you don't have to worry about,
34. we try all the different possible combinations that aren't zero-zeros
35. since that would not be a valid vertex cover.
36. We try 1, 0; 0, 1; and 1, 1.
37. We compute the size for each of these and then we return the minimum of those
38. and compute this whole thing recursively.
39. So that was a little tricky. If you had trouble with that, totally understandable.
40. This does give you a little bit of improvement in the total size
41. of the search tree we end up searching through.
42. Before, it was 2 to the end--Now, we got about 1.733 to the end.
43. It might not seem like much but in practice, it can be helpful.
44. So, okay. Let's go ahead and look a different problem now.