Can anyone write a tutorial on this technique?
1 Like
I think this will help you
Meet in the middle (sometimes called split and merge) is a clever idea that uses caching to get efficient solutions. Much like divide et impera it splits the problem in two and then tries to merge the results. The benefit is that by using quite a bit of extra memory you can tackle problems of twice the size you could before. Follow the link to read full tutorial - here
1 Like
@amitt001 @drj_reddy thanks for the link, I am having really difficult time understanding the minimal set cover solution, I googled it but was unable to find solution for it based on meet in the middle technique.Can you guys help me in understanding the solution?
In the technique we are dividing the total vertices in two equal sized sets, and then we divide each set in states vertex, so total number of ways to divide vertices in 3 states will be 3^(n/2).
Now after dividing the vertices we will check wether the A and B state set cover all the edges in that set(which I assumes that all those edges between the vertices belonging to that set)if yes than we assign the same value to the A and C state vertices and hash the value along with the vertices belonging to A and B set.we will do same with the second set vertices and search for the complementary hash in first set hashlist,
The value to the vertices in the first set be 0 or 1 if all the edges between that vertices and vertices in the second set belongs to B(now what does that mean, since B state was for vertices
not for edges and what is the use of 3 states ) Please explain that with example?