Formulação de problemas como busca
Author
Marcos Castro de Souza
Last Updated
7 years ago
License
Creative Commons CC BY 4.0
Abstract
Esse trabalho tem como objetivo formular problemas como busca.
Esse trabalho tem como objetivo formular problemas como busca.
\documentclass[a4paper, 11pt]{article}
\usepackage{fullpage} % changes the margin
\usepackage[brazilian]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\begin{document}
%Header-Make sure you update this information!!!!https://preview.overleaf.com/public/tyvdycfnqdpp/images/4a3b41dc579356a7fa4d6c69518ac2baea928ae7.jpeg
\noindent
\large\textbf{Formulação de problemas como busca} \hfill \textbf{Marcos Castro de Souza} \\
Prof. Ana Carolina Lorena \hfill Deadline: 05/04/2016 \\
Disciplina: Inteligência Computacional
\section*{Objetivo do trabalho}
Formular problemas como busca identificando quatro componentes: estado inicial, operadores, teste de término e custo de caminho.
\section*{Problema: Torre de Hanói}
Descrição: tem-se 3 pinos e N discos de diâmetros diferentes onde é N >= 3. Os discos começam em um dos pinos em ordem crescente pelo diâmetro de cima para baixo em um dos pinos. O objetivo é passar todos os discos de um pino para outro qualquer usando um dos pinos como auxiliar de forma que um disco \textbf{nunca} fique em cima de outro disco menor em nenhuma situação.
\begin{enumerate}
\item \textbf{Estado inicial}: conjunto de discos em ordem crescente de diâmetro de cima para baixo em um dos pinos. A imagem a seguir mostra um exemplo de estado inicial.
\linebreak \linebreak\includegraphics[width=\textwidth]{hanoi_initial_state.png}
\item \textbf{Operadores}: cada movimento é feito somente com o disco que está mais acima (no topo da pilha), transferindo esse disco para um dos outros pinos de forma que não é permitido um disco de diâmetro maior sobre um disco de diâmetro menor. A imagem a seguir mostra um exemplo de movimentos realizados para N=3 discos.
\linebreak \linebreak\includegraphics[width=\textwidth]{hanoi_movs.png}
\item \textbf{Teste de término}: verifica se conseguiu transferir toda a torre para um dos outros pinos sem que um disco maior tivesse ficado sobre um disco menor em qualquer estado.
\item \textbf{Custo do caminho}: cada movimento de disco custa 1, portanto, o custo do caminho é o número total de movimentações realizadas.
\end{enumerate}
\section*{Problema: Palavras cruzadas (Jogo da velha)}
Descrição: o jogo da velha consiste em um jogo que possui um tabuleiro (matriz) de três linhas e três colunas. Dois jogadores escolhem uma marcação cada um, geralmente um círculo (O) e um xis (X). Cada rodada um jogador realiza uma marcação em uma posição vazia. Um jogador vence quando ele preenche uma linha, coluna ou diagonal com sua marcação.
\begin{enumerate}
\item \textbf{Estado inicial}: um tabuleiro 3x3 vazio.
\item \textbf{Operadores}: um jogador pode marcar em qualquer posição vazia do tabuleiro.
\item \textbf{Teste de término}: verifica se algum jogador fez jogo em linha, coluna ou diagonal ou se o tabuleiro está totalmente preenchido sem vencedor (empate). A imagem abaixo mostra um exemplo de estado de término onde o jogador "O" vence o jogo na diagonal:
\begin{center}
\includegraphics[width=0.3\textwidth]{tic_tac_toe_final.png}
\end{center}
\item \textbf{Custo do caminho}: quantidade de movimentos feitos por um jogador para vencer o jogo.
\end{enumerate}
\section*{Problema: Canibais e missionários}
Descrição: três missionários e três canibais devem atravessar um rio com um barco que pode transportar no máximo duas pessoas, com a restrição de que, para ambas as margens, se há missionários presentes naquela margem, eles não podem ser ultrapassados pelo número de canibais na mesma margem por causa que os canibais comeriam os missionários. O barco não pode atravessar o rio sem pessoas a bordo.
\begin{enumerate}
\item \textbf{Estado inicial}: todos (missionários e canibais) estão em uma das margens.
\linebreak \linebreak\includegraphics[width=\textwidth]{canibals.png}
\item \textbf{Operadores}: o barco pode ir de uma margem para outra transportando no mínimo uma e no máximo duas pessoas.
\item \textbf{Teste de término}: verifica se todos (missionários e canibais) estão na outra margem.
\item \textbf{Custo do caminho}: quantidade de vezes que o barco atravessou o rio.
\end{enumerate}
\section*{Problema: Grade retangular}
Descrição: buscar uma rota entre dois pontos de uma grade retangular.
\begin{enumerate}
\item \textbf{Estado inicial}: o ponto de onde começa a rota, trata-se da raiz da árvore de busca.
\item \textbf{Operadores}: o estado atual pode expandir para o norte, sul, leste ou oeste.
\item \textbf{Teste de término}: verifica se chegou ao ponto de destino.
\item \textbf{Custo do caminho}: é a profundidade da árvore que foi gerada.
\end{enumerate}
\end{document}