So, would it be possible to obtain the exact result each time if we: a) whenever we have a tie - parallelize the algorithm to explore different choices/branches b) at the end choose the shortest one among those?
I didn't get why you have issue to find the shortest string? 3:38 ABB has 2 equal options merge with BBB (2) or BBA (2). But you can create multiple branching, OR just skip node and move to another, like combine BBB with BBA, because it has (2), and AAAB with ABB, so you left with AAABB and BBBA, that's equal 7.
Does Spectral Graph analysis have any particular cool property in this specific np problem? I wondering if in the class of np-complete problem set we can highlight some pattern, which doesn't make the problem to loose it's complexity characteristic, but give us some insight. To conclude, can we make this np-complete slim getting rid of some fat?
No, that wouldn't make the algorithm optimal. Consider the example Jacob presents about 6 minutes into this practical video: th-cam.com/video/uS6ca7yeVb0/w-d-xo.html
So, would it be possible to obtain the exact result each time if we:
a) whenever we have a tie - parallelize the algorithm to explore different choices/branches
b) at the end choose the shortest one among those?
I didn't get why you have issue to find the shortest string? 3:38
ABB has 2 equal options merge with BBB (2) or BBA (2).
But you can create multiple branching, OR just skip node and move to another, like combine BBB with BBA, because it has (2), and AAAB with ABB, so you left with AAABB and BBBA, that's equal 7.
Simple and clear explanation loved it !
Does Spectral Graph analysis have any particular cool property in this specific np problem? I wondering if in the class of np-complete problem set we can highlight some pattern, which doesn't make the problem to loose it's complexity characteristic, but give us some insight. To conclude, can we make this np-complete slim getting rid of some fat?
No, that wouldn't make the algorithm optimal. Consider the example Jacob presents about 6 minutes into this practical video: th-cam.com/video/uS6ca7yeVb0/w-d-xo.html