Finding a hamiltonianISH path in a graph
This is the longest path problem.  It's NP-hard to find the longest path in a general graph.  You can try applying any standard algorithm for finding longest paths.  Search on this site for "longest path" and "Hamiltonian path" to find many references.  Since you're willing to accept suboptimal solutions, you might look for a heuristic or approximation algorithm (e.g., using a local search algorithm).