Given a directed graph G and a starting vertex $v$ and a cutoff weight $w$, I want to find a simple walk with net weight < $w$ that visits as many nodes as possible. Currently, I have a recursive function which is incredibly slow, is there some sort of heuristic function for such a problem?
For my particular purposes, I am looking at superpermutation graphs for k letters, $S_k$, with only 1-edges and 2-edges. $S_k$ is vertex transitive, with each vertex having one 1-edge (weight 0) and one 2-edge (weight 1).