English subtitles

← 13ps-06 A Better Tree Solution

Get Embed Code
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.