Universidade Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Teoria dos Grafos Professor: Marco Antonio M. Carvalho Lista de Exercícios 08 1. Modele cada um dos problemas abaixo como um problema de busca em grafos de estados, detalhando: (i) o que são os estados, (ii) o estado inicial e o estado final, (iv) as transições, (v) a função objetivo, (vi) o fator de ramificação do problema e (vii) se estamos interessados somente no estado final ou no caminho que leva até o caminho final. a. Três canibais e três missionários estão viajando juntos e chegam à margem de um rio. Eles desejam atravessar para a outra margem para, desta forma, continuar a viagem. O único meio de transporte disponível é um barco que comporta no máximo duas pessoas. Há uma outra dificuldade: em nenhum momento o número de canibais pode ser superior ao número de missionários pois desta forma os missionários estariam em grande perigo de vida; b. Em um tabuleiro de xadrez de dimensão 8x8, disponha oito rainhas de forma que nenhuma delas seja atacada por outra. Para tanto, é necessário que duas rainhas quaisquer não estejam numa mesma linha, coluna, ou diagonal; c. Um aspirador de pó autônomo é equipado com dois sensores, um de localização e outro de sujeira, de maneira que o aspirador sabe onde está e sabe se o local está sujo ou não. O aspirador ainda possui as seguintes funções: ir para a esquerda, ir para a direita, aspirar ou standby. Deseja-­‐se que este aspirador limpe todas as salas de um prédio (de acordo com a planta abaixo), no menor número de estados possível; d. Em uma mesa, existem três blocos de madeira com os rótulos A, B e C. Um bloco pode estar empilhado sobre outro ou diretamente sobre a mesa (a situação inicial é ilustrada na figura abaixo). Deseja-­‐se manipular os blocos de tal maneira que ao final tenhamos uma única pilha, ordenada lexicograficamente do topo para a base. Somente um bloco pode ser manipulado por vez. C A B e. O jogo da velha.