I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search can do this, but I was left wondering if you could minimize the backtracking.
I looked into how it's actually done for Roomba and from what I read on Robotics stack exchange, it doesn't use a deterministic algorithm that guarantees shortest distance, because it doesn't know the room layout and obstacles ahead of time.
But what if we did know the full layout of the room at the start? Is there a way to use a map to generate a path through the room with minimum backtracking? In this example, the map is an undirected graph without weights (or every joining edge distance is 1), and it likely contains cycles.
The problem sounds similar to travelling salesman and Hamiltonian paths, but I don't think it maps to them exactly. Travelling salesman and Hamiltonian paths have the requirement that vertices are only visited once. In the Roomba example, we don't care if it vacuums the same spot twice, we just want it to thoroughly vacuum the whole room (don't miss anywhere) as fast as possible.