Traveling salesman problem

[wlxxiii_]

https://leetcode.com/problems/find-the-shortest-superstring/discuss/195077/Clean-python-DP-with-explanations

Was reading this solution until I saw

dp = [[''] * 12 for _ in range(1 << 12)]

Why 12? Anyone knows?

Sent from Xiaomi POCO F2 PRO using GAGT

 

[davidktw]

https://leetcode.com/problems/find-the-shortest-superstring/discuss/195077/Clean-python-DP-with-explanations

Was reading this solution until I saw

dp = [[''] * 12 for _ in range(1 << 12)]

Why 12? Anyone knows?

Sent from Xiaomi POCO F2 PRO using GAGT

Didn't read much into the algorithm.

 

[wlxxiii_]

ok no wonder...... i was thinking 5+4+3... 4+3+2+1.....5! etc all cannot sum to 12. thanks david.

 

[wlxxiii_]

ok i'm still having problems understanding even though i know about bit-wise operations and the idea of dp[path][end node] = dp[path][end -1 node] + cost[end node] and then subsequently performing recursion.

any suggestions for video/article on how to understand dynamic prog using bitmasking? thanks in advance

 

[davidktw]

ok i'm still having problems understanding even though i know about bit-wise operations and the idea of dp[path][end node] = dp[path][end -1 node] + cost[end node] and then subsequently performing recursion.

any suggestions for video/article on how to understand dynamic prog using bitmasking? thanks in advance

Lets start off dynamic programming technique using this
https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

Bitmask is not part of DP, it is just a technique this algorithm used to perform marking. Marking can be done with sequence of booleans, whether they are a string, or single/multidimensional array or so forth. It doesn't have to be bits, but obviously bits are more compact at the expense of using more bitwise operations.

Do you get the concept of DP first ? That's more important than bitwise operations.

Then you need to understand why this shortest superstring that can contain all the substrings in A is a TSP. How is that problem modelled into a TSP ? You ought to read up on what is TSP, and the dynamic programming approach to solve the problem. Looking at the algorithm is not going to make sense to you unless you understand the context of how it is written.

 

[wlxxiii_]

yup i've done a few problems on DP
How is that problem modelled into a TSP ? <--- because each char in the different substrings can be thought of as different cities. shortest superstring is then similar to shortest path taken. the idea is to find out how many char u can "save" by placing one substring behind another and noting the num of overlapping chars, and maximizing the "savings".

just feel that i'm quite close to understanding the solution.....just need more comments in the code to explain why the various steps are executed....