Guaranteed graph labyrinth solving sequence

Question

Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from vertex in question to an other one), one exit is labeled 'a', the other exit is labeled 'b'.

We have limitless 'memory' but, we don't recognize when we arrive at the same vertex again, so at each step we can only pick if we go exit a or exit b, or we recognize when we have entered the exit vertex. Show that there is an algorithm to get out of any maze!

Write the algorithm. If n is its input, then its output is a sequence 'a', 'b' that exits any maze with at most n vertices.

I got this assignment (math student) in a course to do with algorithms. I don't believe the actual code outputting the 'a', 'b' sequence is particularly difficult once the structure of the function is found mathematically.

I've had multiple ideas, it is clear, that were we to find a sequence that would guarantee a visit to all vertices, we would be done, as one of them must be the "end" vertex. This would be easy, if the edges weren't directed, because we would try all possible 1-long sequences by doing a 1-long sequence and tracing our steps back and doing the next, if we didnt reach the end. Then do the same with 2-long sequences, and so on. I think the longest sequnces we would have to try would be $ 2^n $ in length and we would get an incredibly long sequence but it could be shown to work. But this solution relies heavily on the fact that we could always trace our way back to the vertex at which we start and thereby doing something like a BFS. That doesn't work here, as we can't go back on edges we came from (at least not necessarily).

I also stumbled upon De Bruijn sequences. A De Bruijn sequence for a given alphabet (in this case, 'a' and 'b') and a given length 'n' is a cyclic sequence in which every possible subsequence of length 'n' appears exactly once. I don't see how this would work, but maybe if we collate this sequence 'n+1' times, we would visit all vertices, because we would be guaranteed to have tried all 'walks' from all vertices, but I don't see this rigorously at all.

That is why I come to you, I need some serious guidance, as I have no clue about this at all

(my related question in CS Stack Exchange: https://cs.stackexchange.com/questions/167241/graph-labyrinth-solving-sequence/167244?noredirect=1#comment346313_167244)

Answer 1

There are only finitely many possible labyrinths on $n$ vertices, where the data defining a labyrinth includes all of the edges, the start vertex, and the target vertex. Say there are $M$ labyrinths, and name them $L_1,L_2,\dots,L_M$. Given a labyrinth $L$ and an arbitrary vertex $v$ of $L$, let $\newcommand\sol{\text{sol}}\sol(L,v)$ be a sequence of $a$ and $b$ which, starting from $v$, takes you to the exit of $L$.

Let $w_1=\sol(L_1,v_1)$, where $v_1$ is the start vertex of $L_1$. The first part of the solution path will be $w_1$.

Let $v_2$ be the vertex you end up on after following the path $w_1$ on the labyrinth $L_2$. Then, let $w_2=\sol(L_2,v_2)$. The second portion of the solution path is $w_2$; as long as the true labyrinth is $L_2$, then we will be done after completing $w_1+w_2$.

Let $v_3$ be the vertex you end up on after following the concatenation of paths $w_1+w_2$ on the labyrinth $L_3$. Then, let $w_3=\sol(L_3,v_3)$. The third portion of the solution path is $w_3$.

We continue in this fashion. Assuming that $w_k$ has been defined, we let $v_{k+1}$ be the result of following the path $w_1+w_2+\dots+w_k$ on $L_{k+1}$, and then define $w_{k+1}=\sol(L_{k+1},v_{k+1})$.

Finally, the solution path which works on any labyrinth is $w_1+\dots+w_M$.

Answer 2

Define an $n$-labyrinth as a strongly connected directed graph on $0\leq m\leq n-2$ vertices labeled $s,e,1,2,...,m$, where each vertex $v$ is the source of two edges labeled $a,b$. ($s$ stands for "start", and $e$ stands for "end")

For any sequence $S$ in $\{a,b\}^*$, any $n$-labyrinth $L$, and any vertex $v$ of $L$ we denote $S_{v,L}$ the path in $L$ starting at $v$ and taking the sequence of edges in $L$ associated with the sequence $S$.

Here, I provide provide an outline for an algorithm that produces a finite sequence $S$ in $\{a,b\}^*$ such that for any $n$-labyrinth $L$, the path $S_{s,L}$ passes over the end vertex $e$.

---

First, generate a list of every possible $n$-labyrinth $(L_1,L_2,\ldots,L_k)$. (there are various ways to do this)

Now, let $S$ be the empty string.

For each $i$ in $1,2,...,k$, perform the following procedure:

Define $v$ as the final vertex in the path $S_{s,L_i}$.

Find a sequence $T$ such that $T_{v,L_i}$ is a path from $v$ to $e$. ($T$ exists since $L_i$ is strongly connected and can be found via a standard breadth-first search algorithm)

Append the string $T$ to the end of $S$.

Output the string $S$.

---

To see that the final output $S$ satisfies our requirements, note that for any particular $n$-labyrinth $L_i$, at the end of the step $i$ in the for loop, the sequence $S$ is by construction a sequence such that $S_{s,L_i}$ is a path from $s$ to $e$, and since subsequent itterations of the for loop only append characters to $S$, the final output $S$ is such that $S_{s,L_i}$ is guaranteed to pass over the vertex $e$.