.. -*- coding: utf-8 -*- .. |Python| replace:: ``Python`` .. |IPython| replace:: ``IPython`` .. |PythonAnywhere| replace:: `PythonAnywhere `__ .. |RST| replace:: `reST `__ .. |Sphinx| replace:: `Sphinx `__ .. |HTML| replace:: ``HTML`` .. |Trinket| replace:: `Trinket `__ .. |Colab| replace:: `Google Colab `__ .. |Replit| replace:: `Replit `__ .. |Runestone| replace:: `Runestone `__ .. |cscircles| replace:: ``cscircles`` .. |fazsentido| replace:: Faz sentido? ``¯\_(ツ)_/¯`` .. |SURPRESO| replace:: ``(☉_☉)`` .. |HEIN| replace:: ``¯\_(ツ)_/¯`` .. |HELP| replace:: ``(҂◡_◡)`` .. |VALEU| replace:: ``\(•◡•)/`` .. |CONFUSO| replace:: ``ఠ_ఠ`` .. |LOUCO| replace:: ``(⊙_◎)`` .. |TRISTE| replace:: ``(ಥ﹏ಥ)`` .. |ENTER| replace:: ``ENTER`` .. |Return| replace:: ``Return`` .. |Forward| replace:: ``Forward >`` .. |Last| replace:: ``Last >>`` .. |First| replace:: ``<< First`` .. |Back| replace:: ``< Back`` .. |Run| replace:: ``Run`` Ideia de Ariadne ================ .. index:: Ariadne Na mitologia grega, `Ariadne `_ era uma princesa cretense e filha do rei `Minos `_ de Creta. Ariadne é conhecida, entre outras coisas, por ter dado uma **baita ideia** para que `Teseu `_ se guiasse dentro de uma labirinto e derrotasse o `Minotauro `_. .. image:: ./imgs/1440px-Sleeping_Ariadne_2.* :width: 1440 :height: 1080 :scale: 25 :alt: Statue of Sleeping Ariadne in the Vatican Museums, By Wknight94 - Own work, CC BY-SA 3.0 :align: center :target: https://commons.wikimedia.org/w/index.php?curid=6742102 Bem, uma das versões do mito diz que ... o rei Minos atacou Atenas depois que seu filho, Androgeu, foi morto em Atenas. Após terem sido derrotados por Minos, como reparação, os atenienses concordaram em de :math:`x` anos em :math:`x` anos oferecerem como sacrifício jovens atenienses ao Minotauro que habitava no centro de um labirinto. O valor de :math:`x` depende da versão do mito. .. index:: Teseu .. index:: Minotauro Minos colocou sua filha Ariadne no comando do labirinto onde eram feitos sacrifícios. Um dos sacrifícios incluiu o ateniense Teseu, filho do rei Egeu, que havia se voluntariado para entrar no labirinto para matar o Minotauro. Ariadne se apaixonou-se por Teseu à primeira vista |:heart:| |:love_you_gesture_medium_light_skin_tone:| e forneceu-lhe uma espada |:dagger:| para matar o Minotauro e um novelo de linha |:thread:|, o `fio de Ariadne `_, para que ele pudesse se guiar no labirinto e encontrar a saída depois de ter derrotado o Minotauro. Teseu matou o Minotauro e é na mitologia grega é um grande herói de Atenas. .. image:: ./imgs/The_golden_fleece_and_the_heroes_who_lived_before_Achilles.jpg :width: 881 :height: 1080 :scale: 30 :alt: By Internet Archive Book Images - https://www.flickr.com/photos/internetarchivebookimages/14786798643/Source book page: https://archive.org/stream/goldenfleeceherocolu/goldenfleeceherocolu#page/n291/mode/1up, No restrictions. :align: center :target: https://commons.wikimedia.org/w/index.php?curid=42109868 .. index:: Dionísio Não tem nada a ver, mas... depois... Ariadne foi abandonado por Teseu |:broken_heart:| na ilha de Naxos, onde Dionísio a viu dormindo, se apaixonou |:heartpulse:| |:love_you_gesture_medium_light_skin_tone:| por Ariadne e mais tarde se casou |:wedding:| com ela. Dionísio não tem nada a ver com que vamos discutir mais adiante, mas a ideia da Ariadne... tem tudo a ver! .. image:: ./imgs/Theseus_and_the_Minotaur.gif :width: 340 :height: 563 :scale: 50 :alt: By H.A.Guerber - The story of Greeks], Public Domain :align: center :target: https://commons.wikimedia.org/w/index.php?curid=32308901 .. .. image:: ./imgs/1613px-Antonio_Canova_Teseo_defeats_the_centaur.* :width: 1613 :height: 1080 :scale: 25 :alt: Antonio Canova: Theseus Fighting the Centaur (1804–1819). Kunsthistorisches Museum, Vienna, By Falcodigiada - Own work, CC BY-SA 4.0 :align: center :target: https://commons.wikimedia.org/w/index.php?curid=86003279 Destino ------- .. index:: fio de Ariadne .. index:: Ariadne .. index:: Teseu .. index:: fio de Ariadne O lugar de destaque, de muito destaque, mesmo que visitaremos nessa nossa jornada, neste capítulo é a baita `ideia de Ariadne `_ em usar um fio |:thread:| para que Teseu registrasse as rotas percorridas. A cada passo feito por Teseu no labirinto ele desenrolava o fio, deixando-o preso ao chão. No labirinto os corredores sem fio algum eram aqueles em que Teseu não havia passado, os corredores com um fio eram aqueles em que Teseu havia percorrido em uma das direções e os corredores com dois fios eram os em que Teseu havia percorrido em ambas as direções depois de ter fracassado, ter chegado a um beco sem saída, em uma tentativa de rota. .. image:: ./imgs/labirinto.png :width: 1175 :height: 791 :scale: 35 :alt: http://www.mazegenerator.net/ :align: center :target: http://www.mazegenerator.net/ Para Teseu o fio de Ariadne foi fundamental para não andar pelo labirinto desorientado, sem se perder, e para, depois de derrotar o Minotauro, voltar facilmente |:cake:| ao portal de entrada do labirinto. O fio serviu para marcar físicamente todos os seus passos |:footprints:|, todas as suas decisões tomadas ao longo caminho. Essas marcas ou registros foram usadas para não repetir rotas já tentadas e para que a cada momento houvesse a possibilidade de retroceder até algum determinado ponto em que houvesse algum outro caminho ainda não tentado. Um mecanismo com o fio de Ariadne pode ser aplicado a problemas em que a solução é o formada por uma série de passos em que opções ou decisões feitas de tempos em tempos. Um solução, se existe, é alcançada por meio de uma tentativa exaustiva de todas as rotas disponíveis, sem que tenhamos o risco de revisitar rotas já tentadas. A ideia central do fio de Ariadne aplicado a um problema qualquer é a criação e manutenção de registros |:pencil:|, um *log*, que nos permita sabermos a cada instante quais são as opções disponíveis que ainda não foram exploradas. Uma das funções dos registros é permitir o retrocesso, isto é, reverter decisões anteriores e tentar novas alternativas. Tendo em mão |:open_hands_tone3:| os registros |:book:|, a aplicação da estratégia do algoritmo em quaquer ponto em que uma decisão deve ser tomada é basicamente seguinte. Se os registros |:book:| indicam que desse ponto * não há opções que possivelmente nos levem ao *sucesso*, nos levem a uma *solução*, registramos |:writing_hand:| esse ponto como sendo de *fracasso* e voltamos ao último local em que os registros indicam que há ainda opções a serem consideradas e prossiguimos daquele ponto; * há ainda opções a serem consideradas, fazemos uma escolha arbitraria entre aquelas que ainda não foram registradas |:writing_hand_tone4:| como fracassadas e seguimos a opção escolhida até onde for possível. Este algoritmo terminará ao **encontrarmos uma solução** ou ao verificarmos que os registros |:book:| nos dizem que todas as possíveis opções iniciais nos levarão ao fracasso, todas as opções iniciais foram registradas |:writing_hand_tone2:| como *fracasso*; neste último caso, **não há solução**. Se embora tenhamos encontrado uma solução desejarmos realizar um exame minucioso, podemos registrar |:writing_hand_tone2:| o sucesso, voltar à decisão anterior e continuar como se nunca tivêssemos encontrado uma solução. Nesse caso o algoritmo consideraria todas as opções e encontraria **todas as soluções**. .. image:: ./imgs/Longleat_maze.jpg :width: 896 :height: 600 :scale: 40 :alt: The maze of Longleat House, By Rurik - Own work, Public Domain :align: center :target: https://commons.wikimedia.org/w/index.php?curid=2066323 A ideia do fio de Ariadne é utilizada em algoritmos fundamentais e cotidianamente utilizados em computação como a `busca em largura `_ (`Breadth-first search `_) e a `busca em profundidade `_ (`Depth-first search `_). O que veremos nesse capítulo é essencialmente a *busca em profundidade*. A *busca em largura* ficará para um dos próximos passeios. .. A ideia do fio de Ariadne, cujo nome vem da lenda de Ariadne, é resolver um problema por vários meios - como um labirinto físico, um quebra-cabeça lógico ou um dilema ético - por meio de uma aplicação exaustiva da lógica a todas as rotas disponíveis. É o método particular utilizado que é capaz de seguir completamente para traçar passos ou tomar ponto a ponto uma série de verdades encontradas em uma busca contingente, ordenada que chega a uma posição final. Esse processo pode assumir a forma de um registro mental, uma marcação física ou mesmo um debate filosófico; é o próprio processo que assume o nome. Implementação O elemento-chave para aplicar o fio de Ariadne a um problema é a criação e manutenção de um registro — físico ou não — das opções disponíveis e esgotadas do problema o tempo todo. Esse registro é chamado de "thread", independentemente de sua mídia real. O objetivo do registro é permitir o retrocesso - isto é, reverter decisões anteriores e tentar alternativas. Dado o registro, a aplicação do algoritmo é direta: A qualquer momento que houver uma escolha a ser feita, faça uma arbitrariamente entre aquelas que ainda não foram marcadas como falhas e siga-a logicamente até onde for possível. Se o resultado for uma contradição, volte para a última decisão tomada, marque-a como um fracasso e tente outra decisão no mesmo ponto. Se não houver outras opções lá, volte para o último local no registro que tenha opções, marque a falha nesse nível e prossiga. Este algoritmo terminará ao encontrar uma solução ou marcar todas as escolhas iniciais como falhas; neste último caso, não há solução. Se se deseja um exame minucioso, embora tenha sido encontrada uma solução, pode-se voltar à decisão anterior, marcar o sucesso e continuar como se nunca tivesse sido encontrada uma solução; o algoritmo esgotará todas as decisões e encontrará todas as soluções. Introdução ---------- Ariadne deu a `Teseu `_ uma espada |:dagger:| e um carretel com linha |:thread:|. Apesar da espada ter sido muito útil para Teseu derrotar o `Minotauro `_, estamos totalmente interessados no papel que o carretel de linha |:thread:| teve nessa aventura. Para entendermos o problema que estamos visitando e inspecionarmos principalmente a estratégia empregada para solucioná-lo investigaremos |:detective_tone3:| bem cuidadosamente |:mag:| |:eye:| a animação a seguir. Na animação o herói ateniense Teseu é mostrado entrando no labirinto, procurando o Minotauro e saindo do labirinto após ter encontrado e derrotado o Minotauro. Teseu é interpretado pela tartaruga |:turtle:| que está se movimentando pelo labirinto O papel do Minotauro é feito pela tartaruga |:turtle:| que está parada no labirinto. Contemplemos :nerd_face: um pouco a animação antes de prosseguirmos como nossa diversão. .. image:: ./imgs/fio_de_ariadne1.gif :width: 961 :height: 853 :scale: 50 :alt: Animação da estratégia de Ariadne :align: center O livro de anotações |:blue_book:| em que são registramos |:pencil2:| todas as decisões, todos passos, tomadas por Teseu é o próprio labirinto. No labirinto os retângulos totalmente preenchido, pintados |:orange_square:|, são as suas **paredes**. Posições **livres** são os corredores nos quais Teseu ainda não passou e são indicadas por um espaço vazio |:black_square_button:|, exceto a posição onde está o Minotauro |:turtle:|. As demais posições tem uma marca em seu interior que pode ser um círculo |:black_circle:|, um quadrado |:red_square:|, ou um triângulo |:small_red_triangle:|. Os círculos |:black_circle:|, quadrados |:red_square:| e triângulos |:small_red_triangle:| são os **registros** |:pencil:| feitos no caderno de anotações |:book:| que é o labirinto. Os círculos e os quadrados fazem as vezes do **fio de Ariadne** utilizado para marcar os corredores percorridos por Teseu na sua procura pelo Minotauro. A primeira vez que Teseu percorre um corredor deixa um círculo. Depois de Teseu passar por corretor, explorar todos os corredores alcançáveis a partir deste, e retroceder, Teseu marca esse corredor com um quadrado |:red_square:|. Em cada momento da sua busca Teseu olha para as quatro direções adjacentes, ``NORTE``, ``SUL``, ``LESTE`` e ``OESTE``. Durante a sua procura pelo Minotauro, em cada uma das direções, Teseu vê |:eyes:| uma parede, ou um corredor que ele: * ainda não percorreu |:black_square_button:|; * percorreu apenas uma vez |:black_circle:| e um mostra a Teseu de onde veio e um caminho direto até saída, para quando ele decidir que está na hora de vazar |:man_running_dark_skin_tone:|; ou * percorreu em ambas a direção |:red_square:| e que levou a um beco sem saída e sem Minotauro. Com isso podemos entender a baita ideia da Ariadne! O seu fio seria usado por Teseu para registrar |:books:| os corredores percorridos e permitem a ele retroceder até um ponto onde já passou a procurar de outros corredores ainda não percorridos, tudo isso em busca do Minotauro. Um fato super bacana, *relação invariante* da ideia, é que a todo momento os círculos |:black_circle:| mostram a Teseu um caminho direto e reto de sua posição até a saída do labirinto |:face_exhaling:|. Os triângulos mostram os corredores em que Teseu passou até a saída após, para a alegria dos atenienses, ter derrotado o Minotauro. .. index:: Problema de Teseu De uma forma meio vaga o problema que trataremos nesse capítulo será o de Teseu. **Problema (de Teseu)**: Dado um labirinto com o Minotauro e uma posição inicial para Teseu, encontrar um caminho de Teseu até o Minotauro. A solução desse problema é frequentemente adaptada para resolver problemas que em que a solução pode ser obtida percorrendo-se de maneira sistemática uma estrutura formadas por objetos que possuem uma relação de vizinhança que nós diz para cada objetos quem são seu vizinho. |:confounded:| No caso do nosso labirinto os objetos são posições e a relação de vizinhança é dada através da adjacência: os vizinhos de uma posição são as posições verticais e horizontais e verticais adjacentes a ela. |:thinking:| A ideia de Ariadne poderia ser usado por Teseu para percorrer todos os corredores do labirinto sem se perder, como pode ser observado quando examinamos a animação abaixo. .. image:: ./imgs/fio_de_ariadne2.gif :width: 961 :height: 853 :scale: 50 :alt: Animação da estratégia de Ariadne :align: center As animações nesta seção são o resultado de pequenas alterações feitas no código no capítulo `Recursão `_, seção `4.11. Explorando um Labirinto `_, do livro `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_. .. _my_Labirinto: Labirintos ---------- .. image:: ./imgs/Labyrinth_at_Chartres_Cathedral.jpg :width: 1280 :height: 960 :scale: 30 :alt: Walking the labyrinth at Chartres Cathedral, CC BY-SA 3.0 :align: center :target: https://commons.wikimedia.org/w/index.php?curid=510275 .. index:: labirinto Para começar precisamos fazer um combinado do que será para nós um labirinto, como iremos representá-lo e como poderemos manipulá-lo. Nesse seção vamos dizer quais são as regras do jogo. Para nós um labirinto será representado através de um objeto que irá retratar um região retangular dividido em ``nlins`` linhas e ``ncols`` colunas. Cada posição desse labririnto é referenciada por um par de índices ``[lin,col]`` em que ``lin`` indica a linha e ``col`` indica a coluna da posição. Faremos o acordo de que os elementos das posições serão caracteres, strings de comprimento 1. Cada um desses caracteres terá seu significado especifico serão códigos. Usaremos os seguintes apelidos para esses códigos. .. code-block:: python :caption: marcas.py :name: marcas-py # apelidos para as marcas usadas nos registros do labirinto PAREDE = '#' TESEU = 'T' MINOTAURO = 'M' LIVRE = ' ' FIO = '*' BECO = 'b' TESEU_MINOTAURO = '$' MINOTAURO_DERROTADO = 'X' SAIDA = 's' Para criar um objeto ``Labirinto`` fazemos .. code-block:: python In [1]: from labirinto import Labirinto In [2]: lbrnt = Labirinto("deadalus.txt") In [3]: type(lbrnt) Out[3]: labirinto_str.Labirinto O argumento ``daedalus.txt`` é o nome de um arquivo com os caracteres que estão em cada posição do labirinto apelidado de ``lbrnt``. O arquivo ``daedalus.txt`` foi usado na primeira animação da introdução e seu conteúdo é .. code-block:: python In [4]: more deadalus.txt # exibe o conteúdo do arquivo deadlus.txt ###################### # # ## ## # T # # # ### # ## # # # ## #### # ## ### ###### ### # # # ## ## # ##### ###### ##### # # # ####### # # # ####### # M## # # # # # ### ################## ### No arquivo ``deadalus.txt`` os caracteres são aqueles apelidados no arquivo ``marcas.py``: * ``PAREDE`` indica parede; * ``TESEU`` mostra a posição em que Teseu está; * ``MINOTAURO`` é onde está o Minotauro; * ``LIVRE`` apresenta um corredor não explorado por Teseu; * ``FIO`` aponta um corredor que Teseu percorreu em apenas uma das direções, apenas uma vez; * ``BECO`` é um corredor que conduz a um beco sem saída, Teseu percorreu esse corredor em ambas as direções; Um objeto ``Labirinto`` pode ser exibido pela função ``print()``. .. code-block:: python In [5]: print(f"Labirinto inicial:\n{lbrnt}") Labirinto inicial: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| # | | | | # | | | | # | # | | # | # | | | | | | # | | | T | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | | # | | | | # | | | | | | | | # | # | # | | # | | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 3| # | | # | | # | | | # | # | | | # | # | # | # | | | | # | | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 4| # | # | # | | # | # | # | # | # | # | | | | | # | # | # | | # | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 5| # | | | | | | | | | | | # | # | | | # | # | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 6| # | # | # | # | # | | # | # | # | # | # | # | | | | # | # | # | # | # | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 7| # | | | | | | # | | | | # | # | # | # | # | # | # | | | # | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 8| # | | # | # | # | # | # | # | # | | | | # | | | M | # | # | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 9| # | | | | | | | | | | # | | | | # | | | # | | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 10| # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ Os símbolos ``+``, ``-`` e os números não fazem parte do labirinto. Só estão ai para visualizarmos melhor o labirinto. Para consultarmos o conteúdo da posição de índices ``[lin, col]`` de um objeto da classe ``Labirinto``, como ``lbrnt``, escrevemos .. code-block:: python In [7]: lbrnt[1, 21] # posição de Teseu Out[7]: 'T' In [8]: lbrnt[8, 15] # posição do Minotauro Out[8]: 'M' In [8]: lbrnt[4, 2] # parede Out[8]: '#' Contaremos com mais alguns métodos para manipularmos um objeto ``Labirinto`` na nossa solução do Problema de Teseu. ``Labirinto.corredor(lin, col)`` é um método que **recebe** um par de inteiros ``lin`` e ``col`` e **retorna** ``True`` se ``[lin, col]`` é uma posição de um corredor do labirinto e **retorna** ``False`` em caso contrário. .. code-block:: python In [4]: lbrnt.corredor(9, 1) Out[4]: True In [5]: lbrnt.corredor(10, 1) Out[5]: False In [6]: lbrnt.corredor(11, 1) # [11, 1] nem está no labirinto... Out[6]: False In [7]: lbrnt.corredor(10, 18) # é uma entrada/saída Out[7]: True In [8]: lbrnt.corredor(1, 21) # é uma entrada/saída Out[8]: True O método ``Labirinto.registre(lin, col, marca)`` que **recebe** índices ``[lin, col]`` de uma posição do labirinto e um caractere ``marca`` para colocar nessa posição. O efeito é o mesmo que se fizéssemos ``Labirinto[lin, col] = marca``. .. code-block:: python In [9]: from marcas import * In [10]: lbrnt.registre(10, 18, BECO) In [11]: lbrnt[10, 18] Out[11]: 'b' In [12]: lbrnt[1, 20] Out[12]: ' ' In [13]: lbrnt.registre(1, 20, TESEU) In [14]: lbrnt[1, 20] Out[14]: 'T' In [15]: lbrnt[1, 21] Out[15]: 'T' In [16]: lbrnt.registre(1, 21, FIO) In [17]: lbrnt[1, 21] Out[18]: '*' In [21]: lbrnt[3, 15] Out[21]: ' ' In [22]: lbrnt[3, 15] = BECO # o mesmos lbrnt.registre(3, 15, BECO) In [23]: lbrnt[3, 15] Out[23]: 'b' Mais um método que utilizaremos é ``Labirinto.minotauro(lin, col)`` que **recebe** os índices ``[lin, col]`` de uma posição do labirinto e retorna ``True`` se o Minotauro está na posição ``[lin, col]`` e **retorna** ``False`` em caso contrário. .. code-block:: python In [5]: lbrnt[8, 15] Out[5]: 'M' In [6]: lbrnt.minotauro(8, 15) Out[6]: True In [7]: lbrnt[1, 19] Out[7]: ' ' In [8]: lbrnt.minotauro(1, 19) Out[8]: False In [9]: lbrnt[2, 20] Out[9]: '#' In [10]: lbrnt.minotauro(2, 20) Out[10]: False Por último, um objeto ``Labirinto`` sabe a posição inicial de entrada de Teseu no labirinto e a posição do Minotauro. Os atributos de estados ``teseu_lin``, ``teseu_col`` dizem a posição inicial de Teseu e os atributos de estado ``minouro_lin`` e ``minotauro_col`` são os responsáveis pela posição secreta do Minotauro. Se não tivermos Minotauro no labirinto suporemos que ``minouro_lin`` e ``minotauro_col`` são ``None``. .. code-block:: python In [11]: lbrnt.teseu_lin Out[11]: 1 In [12]: lbrnt.tedeu_col Out[12]: 21 In [13]: lbrnt.minotauro_lin Out[13]: 8 In [14]: lbrnt.minotauro_col Out[14]: 15 Pequena aventura ---------------- Para aquecer os nossos motores escrevemos uma solução para uma versão super simplificada do problema de Teseu em que o labirinto é um mero corredor. Bem, um corredor não dá para ser chamado de um labirinto... Tudo bem, o que vale a intenção e isso servirá para testarmos ideias! O labirinto que usaremos é algo como :: 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| T | | | | | | | M | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu está na entrada do corredor na posição ``[1,0]`` e o Minotauro está paradinho na posição ``[1,7]``. .. code-block:: python In [1]: from labirinto import Labirinto In [2]: lbrnt = Labirinto("corredor.txt") In [3]: more corredor.txt ############# T M # ############# Faremos uma função ``teseu()`` que resolve o **Problema (simplificado de Teseu)**: Dado um "labirinto horizontal" com Teseu na entrada, a posição mais à esquerda, encontrar um caminho de Teseu até o Minotauro. Faremos três versões de uma função recursiva ``teseu()`` para o problema simplificado. A expressão da solução de forma recursiva se ajusta como uma luva. |:gloves:| A reflexão que faremos agora é semelhante àquela que fizemos na seção :ref:`my_Rastros` em que traçavamos um paralelo entre a execução função ``factorialR(k)`` para o calculo recursivo de fatorial de ``k`` e as bonicas `Matryoshka `_ |:nesting_dolls:|. Examinemos um pouco a animação a seguir antes de partirmos para a nossa solução. Na animação o papel do Teseu e desempenhado pela tartaruga que se move. Em uma solução recursiva, cada chamada a função ``teseu()``, cria mais um Teseu no labirinto que corresponde a uma chamada ainda ativa, que não foi encerrada, da função ``teseu()``. Nessa animação cada posição em que nas nossas animações anteriores havia um círculo |:black_circle:|, o fio de Ariadne, é mostrado agora mais um Teseu. Cada Teseu representa portanto uma chamada da função ``teseu()`` que ainda está ativa. Tudo se passa como se uma tarefa grande que Teseu deveria realizar foi desmembrada em tarefa menores, uma tarefa realizada por cada um dos Teseus: cada Teseu deve seguir o roteiro descrito na função ``teseu()`` para a posição em que se encontra. .. image:: ./imgs/teseu_simplificado.* :width: 815 :height: 375 :scale: 70 :alt: Animação para Teseu Simplificado :align: center A nossa função estará preparada para o causo em que o Minotauro não está no labirinto. vai que ele saiu do labirinto para tomar um ar. |:sun_with_face:| |:sunglasses:| .. image:: ./imgs/teseu_simplificado2.* :width: 815 :height: 375 :scale: 70 :alt: Animação para Teseu Simplificado :align: center A função ``teseu()`` receberá um "labirinto horizontal" ``lbrnt``, no fundo um mero corredor, e a posição ``[lin,col]`` do Teseu responsável pela posição. A **base da recursão** será quando ``[lin,col]`` é a posição de uma ``PAREDE`` ou a parte do corredor em está o Minotauro. Como no caso Teseu só pode andar para a direita, de uma posição ``[lin,col]`` para uma posição ``[lin,col+1]`` e função ``teseu()`` na sua versão mais simples fica com cara de *fatorial recursivo*. Tá na cara que uma |:wink:| que uma função recursiva como esse poderia ser facilmente adaptada para sua versão iterativa, com algum ``while...``. .. code-block:: python :caption: teseu_simplificada.py def teseu(lbrnt, lin, col): '''(Labirinto, int, int) -> bool RECEBE um labirinto lbrnt e a posição [lin,col] de Teseu no labirinto. RETORNA True se a busca recursiva Teseu pelo Minotauro é bem-sucedida e False em caso contrário. ''' # base da recursão: posição [lin,col] não é (parte de) corredor if not lbrnt.corredor(lin, col): return False # base da recursão: Minotauro esta na posição [lin,col] if lbrnt.minotauro(lin, col): return True # resolva recursivamente: passe a bola para um novo Teseu na direita encontrou = teseu(lbrnt, lin, col+1) return encontrou Essa versão da função ``teseu()`` é até bacaninha |:face_with_hand_over_mouth:| e resolvem o problema. Entretanto, faremos uma melhorias nessa versão que nos ajudarão mais adiante, mas que no momento podem ser até desnecessárias. Na nossa nova versão registraremos |:pencil:| todos os passos |:footprints:| feito pelo Teseu responsável pela recursão que trata da posição ``[lin,col]`` No código usamos os apelidos em :ref:`marcas-py` e as nova linhas estão em destaque. .. code-block:: python :caption: teseu_melhorado.py :emphasize-lines: 10,14,21,23 def teseu(lbrnt, lin, col): '''(Labirinto, int, int) -> bool RECEBE um labirinto lbrnt e a posição [lin,col] de Teseu no labirinto. RETORNA True se a busca recursiva Teseu pelo Minotauro é bem-sucedida e False em caso contrário. ''' # base da recursão: posição [lin,col] não é (parte de) corredor if not lbrnt.corredor(lin, col): return False # base da recursão: Minotauro esta na posição [lin,col] if lbrnt.minotauro(lin, col): lbrnt.registre(lin, col, MINOTAURO_DERROTADO) return True # registre a posição em que Teseu está lbrnt.registre(lin, col, FIO) # resolva recursivamente: passe a bola para um novo Teseu na direita encontrou = teseu(lbrnt, lin, col+1) # registre o resultado da busca if encontrou: # derrotou o Minotauro e esta voltando para a saída lbrnt.registre(lin, col, SAIDA) else: # não encontro o Minotauro e está voltando para a saída lbrnt.registre(lin, col, BECO) return encontrou Vejamos o resultado produzido por essa função melhora. Em particular vamos dar uma olhada nos livros de notas |:books:|. Olhemos os registros |:book:| feitos pala função no labirinto. .. code-block:: python In [1]: from labirinto import Labirinto In [2]: lbrnt = Labirinto("corredor.txt") In [3]: print(lbrnt) 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| T | | | | | | | M | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ In [4]: from teseu_simplificado import teseu In [5]: teseu(lbrnt, lbrnt.teseu_lin, lbrnr.teseu_col) Out[5]: True In [6]: print(lbrnt) 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| s | s | s | s | s | s | s | X | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ |:thinking:| Hmm. A chamada ``teseu(lbrnt, 1, 0)`` retornou ``True``. Depois da chamada a posição ``[1, 7]`` em que estava o Minotauro ficou marcada com o caractere ``MINOTAURO_DERROTADO`` e as posições da entrada do labirinto até o Minotauro estão com um sinal de ``SAIDA``. As marcas ``SAIDA`` foram todas deixadas enquanto Teseu voltava das chamadas recursivas. Cada uma das chamadas, cada Teseu reponsável pela posição ficou encarredado de fazer esse registro antes de passar a bola para o Teseu que o chamou. Apliquemos agora a função melhorada a um labirinto horizontal em que o Minotauro não está presente e vejamos o resultado. .. code-block:: python In [8]: lbrnt = Labirinto("corredor_sem_minotauro.txt") In [9]: print(lbrnt) 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| T | | | | | | | | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ In [10]: teseu(lbrnt, 1, 0) Out[10]: False In [11]: print(lbrnt) 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| b | b | b | b | b | b | b | b | b | b | b | b | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Desta vez a função retornou ``False``, já que o Minotauro não estava no labirinto. Vemos a marca ``BECO`` em todas as posições. Teseu recursivamente andou todo o corredor a procura do Minoutauro, não encontrou, e na volta da recursão cada Teseu marcou a posição sob sua responsabilidade com ``BECO`` sinalizando que o Minoutauro não está naquela direção. Para compreendermos a recursão é indispensável percebermos que há um Teseu responsável por cada posição e que cada Teseu está associado a uma chamada da função ``teseu``. |:confounded:| Para entendermos completamente, e assistamos um passo |:footprints:| a passo |:footprints:| da função ``teseu()`` faremos uma última versão mais verborrágica. Nessa versão Teseu tem um radio transmissor e nos informa a cada momento onde está e o que está fazendo na sua missão no labirinto. É conveniente colocar no meio do código chamadas à uma função ``pause()`` que está a seguir. .. code-block:: python def pause(): input("Tecle ENTER para continuar.") .. index:: ``teseu()`` Chamadas à ``pause()`` nos permitem que monitoremos |:mag:| cada passo de Teseu, ou dos Teseus, no labirinto. No código a seguir as linhas com o código da nossa primeira versão, o nosso esqueleto de solução, estão em destaque. .. code-block:: python :caption: teseu_verborragico.py :emphasize-lines: 7,9,16,22,25,26,29,31,32,34,36 def teseu(lbrnt, lin, col): '''(Labirinto, int, int) -> bool RECEBE um labirinto lbrnt e a posição [lin,col] de Teseu no labirinto. RETORNA True se a busca recursiva Teseu pelo Minotauro é bem-sucedida e False em caso contrário. ''' # base da recursão: posição [lin,col] não é (parte de) corredor if not lbrnt.corredor(lin, col): return False # base da recursão: Minotauro esta na posição [lin,col] if lbrnt.minotauro(lin, col): lbrnt.registre(lin, col, TESEU_MINOTAURO) print(f'{lbrnt}\nTeseu da posição [{lin},{col}]: "Estou com o Minotauro!"') pause() # pare e aprecie lbrnt.registre(lin, col, MINOTAURO_DERROTADO) print(f'{lbrnt}\nTeseu da posição [{lin},{col}]: "Derrotei o Minotauro! Missão cumprida! Vamos para a saída!"') pause() return True # registre a posição em que Teseu está lbrnt.registre(lin, col, TESEU) print(f'{lbrnt}\nTeseu da posição [{lin},{col}]: "Avançamos até a posição [{lin},{col}]."') pause() # pare e aprecie lbrnt.registre(lin, col, FIO) # resolva recursivamente: passe a bola para um novo Teseu na direita encontrou = teseu(lbrnt, lin, col+1) # registre o resultado da busca lbrnt.registre(lin, col, TESEU) if encontrou: print(f'{lbrnt}\nTeseu da posição [{lin},{col}]: "Missão cumprida! Vamos para a saída!"') lbrnt.registre(lin, col, SAIDA) else: print(f'{lbrnt}\nTeseu da posição [{lin},{col}]: "Minha posição leva a um beco sem saída. Voltar!"') lbrnt.registre(lin, col, BECO) pause() # pare e aprecie return encontrou Aqui vai a longa sequência de mensagens enviadas pelo(s) Teseu(s) para o nosso centro de controle. .. code-block:: python In [1]: from labirinto_str import Labirinto In [2]: lbrnt = Labirinto("corredor.txt") In [3]: from teseu_simplificado import teseu In [4]: teseu(lbrnt, lbrnt.teseu_lin, lbrnt.teseu_col) 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| T | | | | | | | M | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,0]: "Avançamos até a posição [1,0]." Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | T | | | | | | M | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,1]: "Avançamos até a posição [1,1]." Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | T | | | | | M | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,2]: "Avançamos até a posição [1,2]." Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | * | T | | | | M | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,3]: "Avançamos até a posição [1,3]." Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | * | * | T | | | M | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,4]: "Avançamos até a posição [1,4]." Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | * | * | * | T | | M | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,5]: "Avançamos até a posição [1,5]." Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | * | * | * | * | T | M | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,6]: "Avançamos até a posição [1,6]." Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | * | * | * | * | * | $ | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,7]: "Estou com o Minotauro!" Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | * | * | * | * | * | X | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,7]: "Derrotei o Minotauro! Missão cumprida! Vamos para a saída!" Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | * | * | * | * | T | X | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,6]: "Missão cumprida! Vamos para a saída!" Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | * | * | * | T | s | X | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,5]: "Missão cumprida Vamos para a saída!" Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | * | * | T | s | s | X | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,4]: "Missão cumprida! Vamos para a saída!" Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | * | T | s | s | s | X | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,3]: "Missão cumprida! Vamos para a saída!" Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | * | T | s | s | s | s | X | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,2]: "Missão cumprida! Vamos para a saída!" Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| * | T | s | s | s | s | s | X | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,1]: "Missão cumprida! Vamos para a saída!" Tecle enter para continuar. 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+---+ 0| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 1| T | s | s | s | s | s | s | X | | | | | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ 2| # | # | # | # | # | # | # | # | # | # | # | # | # | +---+---+---+---+---+---+---+---+---+---+---+---+---+ Teseu da posição [1,0]: "Missão cumprida! Vamos para a saída!" Tecle enter para continuar. Out[4]: True Todas essas ações que procuram mimetizar a ideia da Ariadne, registros |:pencil:| e labirinto como livro de anotações |:book:|, serão usadas na solução do problema de Teseu. Aventura de Teseu ----------------- .. image:: ./imgs/Theseus_and_the_Minotaur_in_the_Labyrinth_-_Google_Art_Project.jpg :width: 1034 :height: 1080 :scale: 20 :alt: By Edward Burne-Jones - lgFxdQtUgyzs7Q at Google Cultural Institute, zoom level maximum, Public Domain :align: center :target: https://commons.wikimedia.org/w/index.php?curid=29661124 Na nossa solução para o problema de Teseu estenderemos as ideias presentes na solução do problema simplificado. Acrescentaremos apenas mais algumas elementos na base da recursão referentes a mais algumas possibilidades para retrocedermos. Devemos ainda levar em consideração as demais direções nas quais Teseu pode se movimentar. A animação abaixo mostra a função ``teseu()`` durante o horário de serviço. .. image:: ./imgs/fio_de_ariadne_recursivo.gif :width: 959 :height: 843 :scale: 50 :alt: Animação da estratégia de Ariadne recursiva :align: center Hmm. |:thinking:| Notemos que a cada momento há várias tartarugas Teseu |:turtle:| |:turtle:| |:turtle:|... Do ponto de vista |:eyes:| de recursão é útil imaginarmos, como na animação, que no labirinto há vários Teseus, em vez de apenas um Teseu como no mito. Cada Teseu |:turtle:| corresponde a uma chamada recursiva ainda ativa da função ``teseu()`` e será o responsável pela posição em que está. Notemos pela animação que os Teseus das chamadas ativas formam um caminho do Teseu mais avançado até a saída do labirinto, fazem o papel do fio |:thread:| de Ariadne. O caminho de volta a entrada do labirinto será percorrido quando as chamadas recursivas estiverem sendo encerradas e, antes de retorno da chamada, um triângulo é registrado |:pencil:| no caderno de anotações |:books:| que é próprio labirinto. As posições com os triângulos são verdadeiramente a solução do problema. Desenvolveremos a seguir o roteiro que estará descrito em |Python| pela função ``teseu()`` no final desta seção. Mãos à obra! |:open_hands:| A função ``teseu()`` recebe um labirinto ``lbrnt``, objeto da classe ``Labirinto``, e uma posição ``[lin,col]`` que será de responsabilidade do Teseu da chamada. No início Teseu está na entrada do labirinto, na posição ``[lbrnt.teseu_lin, lbrnt.teseu_col]``. Para resolver o problema de Teseu a chamada inicial da função é .. code-block:: teseu(lbrnt, lbrnt.teseu_lin, lbrnt.teseu_col) Comecemos a considerar o casos bases de ``teseu()`` em que a função retorna imediatamente o valor ``False``. A função deve retornar ``False`` sempre que a posição ``[lin, col]`` está fora do labirinto ou está marcada com o símbolo: * ``PAREDE``, já que não podemos emparedar um Teseu; |:smile:| * ``BECO``, pois esse símbolo índica que a região do labirinto que tem essa posição como porta de entrada já fui completamente explorada pelos Teseus; * ``FIO``, uma vez que essa marca mostra por onde já passou a busca e que já há um Teseu responsável por essa posição. No código da função as linha :math:`6` a :math:`11` correspondem ao que acabamos de considerado. A função deve imediatamente retornar ``True`` se na posição estiver o Minotauro e deixar uma marca que nos diz que ali temos um ``MINOTAURO_DERROTADO``. Isso é de responsabilidade das linhas :math:`12` a :math:`15` do código da função. Com isso concluímos a base da recursão. |fazsentido| Se no roteiro a função não parou na base podemos afirma que a posição ``[lin,col]`` da chamada é ``LIVRE``. Nesse caso, o Teseu da chamada percorrerá o corredor correspondente e deve portanto marcá-lo como ``FIO``. Esse é o trabalho feito pelas linhas :math:`17` e :math:`18` do código da função. Feito tudo isso, o nosso roteiro chegou em um ponto que o Teseu da vez deve pedir ajuda aos seu clones para continuar a busca. O Teseu responsável pelo posição ``[lin,col]`` enxegar quatro posições vizinhas: * ``[lin-1,col]`` ao ``NORTE``; * ``[lin,col+1]`` a ``LESTE``; * ``[lin+1,col]`` ao ``SUL``; e * ``[lin,col-1]`` a ``OESTE``. A recursão deve avançar em cada uma dessas direções, uma por vez, e deve parar assim que um dos clones reportar que encontrou o Minotauro, retornou ``True``. Esse é o papel desempenhado pelas linhas :math:`20` a :math:`24` do código em que as chamada são feitas sequencialmente, uma após a outra. Como as chamadas estão sendo concatenadas com operador lógico ``or``, assim que uma retornar ``True`` as seguintes não serão feitas. Em programação o comportamento desses operadores lógicos |Python| é conhecido pelo nome de **curto circuito** (= `short circuit evaluation `_), Finalmente, quando há um retrocesso na busca, após as chamadas recursivas, no final da função, o Teseu responsável pela posição deixa nela uma marca indicando o ele e seus colegas Teseus descobriram ao investigar |:mag_right:| a região do labirinto que tem essa posição como porta de entrada. Por último, Teseu retorna ao clone, colega que o chamou, o resultado da busca, ``True`` ou ``False``. Quando os Teseus não encontraram o Minotauro é deixada a marca ``BECO`` |:red_square:| e quando o Minotauro é encontrado é deixado a marca ``SAIDA`` |:small_red_triangle:|. Tudo isso é feito a partir da linha :math:`26` até o final. .. index:: ``teseu()`` Vamos ao código que apresenta em |Python| o todo o roteiro apresentado. No código abaixo as linhas em destaque são aquelas que foram acrescentadas à função herdada da solução do problema simplificado. .. code-block:: python :caption: teseu.py :emphasize-lines: 9, 11, 21,22,23 :linenos: def teseu(lbrnt, lin, col): '''(Labirinto, int, int) -> bool RECEBE um labirinto lbrnt e a posição [lin,col] de Teseu no labirinto. RETORNA True se a busca recursiva Teseu pelo Minotauro é bem-sucedida e False em caso contrário. ''' # base da recursão: posição [lin,col] não é corredor if not lbrnt.corredor(lin, col): return False # base da recursão: posição [lin,col] nos leva a um beco sem saida if lbrnt[lin, col] == BECO: return False # base da recursão: ja passamos na posição [lin,col] é já há um Teseu responsável por ela if not lbrnt[lin, col] == FIO: return False # base da recursão: Minotauro esta na posição [lin,col] if lbrnt.minotauro(lin, col): lbrnt.registre(lin, col, MINOTAURO_DERROTADO) return True # registre a posição em que Teseu desta chamada está lbrnt.registre(lin, col, FIO) # resolva recursivamente: passe a bola para novos Teseus em posições adjacentes encontrou = teseu(lbrnt, lin-1, col ) or \ teseu(lbrnt, lin , col+1) or \ teseu(lbrnt, lin+1, col ) or \ teseu(lbrnt, lin , col+1) # registre o resultado da busca if encontrou: # derrotou o Minotauro e esta voltando para a saída lbrnt.registre(lin, col, SAIDA) else: # não encontro o Minotauro e está retrocedento lbrnt.registre(lin, col, BECO) return encontrou Por onde passamos ----------------- Passamos pela ideia de Ariadne de registramos |:pen:| os nossos passos |:footprints:| ao longo de algum caminho. Isso permite que quando chegamos a um beco sem saída retrocedamos rapidamente até algum ponto da nossa sequência de decisões em que haja ainda alguma possibilidade não explorada. |:face_with_spiral_eyes:| Esse ideia é aplicada na solução de vários problemas nos quais fazemos uma busca por um espaço de soluções em que os estados são dotados de uma relação de adjacência, cada estado sabe quais são os seus vizinhos. É isso que é feito por um algoritmo aplicado cotidianamente chamado de **busca em profundidade**. |:open_mouth:| Veja se entendeu ---------------- #. Implemente uma classe ``Labirinto`` que tenhe comportamento semelhante ao da classe ``Labirinto`` descrita na seção :ref:`my_Labirinto` e usada por nós ao longo do nosso passeio pela ideia de Ariadne e a aventura de Teseu. #. Escreva uma implementação iterativa da função ``teseu()``. #. Escreva uma função ``caminho()`` que **recebe** um objeto ``lbrnt`` da classe ``Labirinto`` após a execução de ``teseu(lbrnt,lbrnt.teseu_lin,lbrnt.teseu_lin)`` e **retorna** uma lista com as posições percorridas por Teseu do Minotauro até a entrada/saída do labirinto. O que é ... ----------- Aqui vai um lista de termos que usamos nesse capítulo e os seus significados. |:nerd:| .. glossary:: Ariadne Na mitologia grega, é a princesa de Creta, filha do rei Minos e da rainha Pasífae. Teseu Na mitologia grega, um grande herói ateniense. Minotauro Na mitologia grega, era uma criatura com a cabeça de um touro sobre o corpo de um homem. Labirinto Construção de percursos intrincados criados com a intenção de desorientar quem os percorre. Para saber mais --------------- * `Recursão e algoritmos recursivos `_ de `Projeto de Algoritmos `_ de Paulo Feofiloff. * `Recursão `_ de `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_ de Brad Miller e David Ranum. * `Recursão `_ de `Como Pensar Como um Cientista da Computação `_ de Brad Miller e David Ranum. * `Recursion `_ de `Introduction to Programming in Python `_. de Robert Sedgewick, Kevin Wayne e Robert Dondero.