We demonstrate via simulations that transient perturbations introduced by non-zero diagonal elements in a Hopfield network can improve NP-hard graph optimization efficiency by more than a factor of two. Such perturbations enhance the known effects of circuit noise typical of memristor-based networks in escaping local minima (incorrect solutions) and finding the global minimum (correct solution) of the Hopfield energy. We provide systematic simulations of NP-hard graph problems with controlled nonidealities in memristor arrays modeled as noise amplitude and diagonal perturbations. Furthermore, our approach improves Hopfield network optimization efficiencies to solve NP-hard problems regardless of the graph size (30x30, 60x60, and 80x80) and connectivity (30%, 50%, and 70%).