0

Good morning, I'm implementing Held-Karp in Matlab, and I'm a bit stuck on how to store the subsets of a given size that are generated by the method. I'm considering using a map through the containers.map class so that I do not need to generate sequential keys to identify each subset (which I would if I used an array). However, I need to generate a unique key for each subset which I can use to compute extended paths in the recursive step. I've considered methods revolving around multiplying all of the elements of the set together to generate a key, but this may not necessarily be unique: within subsets of size two, the sets ${ 6, 3 }$ and ${ 9, 2}$ would map to the same key, which would impact the dynamic programming aspect of the algorithm. Is there a simple way to hash the subsets and generate unique keys for each set? Thank you.

Matt
  • 217
  • 2
  • 12
  • Wouldn't a cell array be sufficient? – beaker Apr 13 '17 at 16:18
  • @beaker The thing is this might be prohibitive to search to see if a given subset is in the array. We'd have to loop over each element of both sets and compare elements, taking linear time. I believe this would push the complexity from n^2 2^n to n^3 2^2 if I'm not mistaken. I was hoping for something like a hash function or hash set – Matt Apr 13 '17 at 16:34
  • You *could* add a dimension for each of the recursive levels, but yes, that would mean a large search. Binary encoding won't work either, for graphs larger than 64 vertices. I'm not aware of any implemented hash functions other than Map, and as you say, a hash set would be more appropriate. – beaker Apr 13 '17 at 16:44
  • Ah, there's always the Java solution: http://stackoverflow.com/a/12625797/1377097 – beaker Apr 13 '17 at 16:48

0 Answers0