You can't "avoid" dead ends. Without looking forward, you'll not know its a dead end... I guess you just don't want your exploring vehicle / person / whatever to stop when a dead end is reached, right? So, I suppose that the "avoid dead ends" rule is meant as "if possible".
I assume you want to develop some kind of strategy game, where one needs to first send some troops to "unknown" areas to know what kind of resources are there etc. And your question is about how to naturally explore this unknown area quickly.
About 15 years ago invented some algorithm that's based on animal behavior. I jokey called it the "Algorithm of the 'shitting' hamster". The name just explains the algorithm quite easily: Imagine a hamster would explore your maze and on every field on the map it moves to, it shits. And well, now it stinks there! The hamster of course doesn't like that and always moves next field it can reach that stinks the least. This ways it will explore the map quite quickly. To give you a better understanding: At each map position it will first move in one of the directions where it did not come from (as it stinks most from there). When it reaches the map field a second time it will take one of the other two directions first. And when it visits the field quite often, it will even go back the way it initially came from. Which means that it will leave the dead ends.
It will even work very well with multiple "hamsters". Or better: imagine it were ants... They will spread into different direction themselves. For the implementation you only need a counter for each field on the map, which counts the number of "visits" (the same counter is used for the entire group).
You can even extend this algorithm to let them find the quickest way back home, by letting each "ant" (or "hamster") count up a "step counter" for each step since it left it's start position. On each map field you store the minimum "step counter" values as following: Initialize the map-values with "maximum". While exploring: If you reach a new map field check if your "step counter" is lower than the stored value on the map, if so ... store your value there. To find a short way home: look for the lowest "step counter" value of the neighboring fields and following the path...
There are lots of ways to extend this to fit special tasks. For example: I adapted this kind of algorithms in the early 90s to simulate some kind of anthill, where ants were exploring a random map that contained some sugar. In the simulation the ants explored the map, until they found sugar and brought it to the anthill (fastest way back home). They also directed the other ants to the sugar they found (by placing some markers on the map that burred out, as soon others were following the path). Eventually, the sugar at one position was depleting and the ants were automatically stopping to follow the "markers" (as they blurred out) and were looking for new resources. So, the basic algorithm has been really practically tested... You just need to be a bit creative to adapt this to your problem.
Okay... I hope you got the key idea and that it hopefully helps you.
Stefan
PS: Let me know if you need more detailed explanations...
