Skip to content


Trabalho Prático e Dicas com Prolog – IA – 2015/1

Especificações:

O que deve ser feito: um programa em prolog que seja capaz de apresentar os passos necessários para atravessar 3 padres e 3 índios em um rio, utilizando para tal um barco de dois lugares e considerando que não podem ficar mais índios do que padres em nenhuma das duas margens dos rios, pois os índios são canibais.

Valor do Trabalho: 1,5 pts; conforme apresentado no Programa de Ensino (folha impressa que lhes entreguei no primeiro dia de aula e que  também está presente no link: PEP2015-IA).

O Trabalho deve ser enviado para o e-mail do professor com o código fonte e o relatório anexados até o dia 24/05/2015.

  • Código Fonte: código em prolog que execute corretamente no SWI Prolog, fornecendo o resultado correto do trabalho;
  • Relatório contendo:
    • Descrição do trabalho;
    • Descrição das dificuldades encontradas;
    • Descrição do funcionamento do código;
    • Descrição dos predicados do trabalho;
    • Descrição do material de apoio utilizado para implementar o código;
    • Conclusão sobre o que aprenderam sobre a linguagem prolog.

Quem enviar até o dia 20/05/2015 (data inicial prevista para entrega) terá uma pontuação extra de 0,2 pontos.


Dicas:

Exemplo 1 (gerando todos os caminhos em um grafo):

%%% Arestas com pesos:
aresta(a, b, 5).
aresta(a, c, 3).
aresta(b, c, 4).
aresta(b, d, 7).
aresta(c, e, 3).
aresta(d, e, 3).
aresta(e, f, 4).
%%%

/* Para toda 'Origem' e 'Lista'
 * 'Lista' é caminho de 'Origem' se:
 *    existe aresta que liga 'Origem' a um 'Próximo' vértice e
 *    Se existe caminho 'L1' que liga o 'Próximo' a outros vértices:
 *       'Origem' e 'L1' pertencem à 'Lista'
 *    Senão:
 *       'Origem' pertence à Lista.
 * ______________________________________
 * Se possui aresta para o próximo:
 *    pergunta o destino do próximo
 *    pergunta o próximo caminho
 *    adiciona o proximo caminho ao atual
 * senao:
 *    o caminho atual é a Origem
 * ______________________________________
 */
caminhos(Origem, Lista) :-
    aresta(Origem, Proximo, _),
    caminhos(Proximo, L1),
    Lista = [Origem | [L1]].

caminhos(Origem, Lista) :-
    Lista = [Origem].

arvore(Origem, Lista) :-
    arvoreAux(Origem, Lista, []).

arvoreAux(Origem, ListaFinal, ListaInicial) :-
    caminhos(Origem, L),
    \+ member(L, ListaInicial),
    arvoreAux(Origem, ListaFinal, [L|ListaInicial]),
    !.
arvoreAux(_, ListaInicial, ListaInicial) :- !.

Testes:

?- caminhos(a, Arvore).
Arvore = [a, [b, [c, [e, [f]]]]] ;
Arvore = [a, [b, [c, [e]]]] ;
Arvore = [a, [b, [c]]] ;
Arvore = [a, [b, [d, [e, [f]]]]] ;
Arvore = [a, [b, [d, [e]]]] ;
Arvore = [a, [b, [d]]] ;
Arvore = [a, [b]] ;
Arvore = [a, [c, [e, [f]]]] ;
Arvore = [a, [c, [e]]] ;
Arvore = [a, [c]] ;
Arvore = [a].

?- arvore(a, L), write(L).
[[a],[a,[c]],[a,[c,[e]]],[a,[c,[e,[f]]]],[a,[b]],[a,[b,[d]]],[a,[b,[d,[e]]]],[a,[b,[d,[e,[f]]]]],[a,[b,[c]]],[a,[b,[c,[e]]]],[a,[b,[c,[e,[f]]]]]]
L = [[a], [a, [c]], [a, [c, [e]]], [a, [c, [e|...]]], [a, [b]], [a, [b|...]], [a, [...|...]], [a|...], [...|...]|...].

Ideia para o Trabalho

Somente para gerar ideias. Discutiremos na próxima aula sobre o trabalho

% Problema dos padres e índios
%      |~  ~  |
%  PPP |[] ~  |
%  III | ~   ~|
%      | ~  ~ |
:- dynamic(indios/1, padres/1, ladoDoBarco/1).

% Marcação de quantos índios estão do lado esquerdo do rio:
indios(3).
padres(3).
ladoDoBarco(e).

mudarLadoDoBarco :-
    retract( ladoDoBarco(e) ),
    asserta( ladoDoBarco(d) ),
    !.
mudarLadoDoBarco :-
    retract( ladoDoBarco(d) ),
    asserta( ladoDoBarco(e) ),
    !.

obterPar(P, I) :-
    padres(X),
    indios(I),
    X >= 2,
    P is X-2.
obterPar(P, I) :-
    padres(P),
    indios(X),
    X >= 2,
    I is X-2.
obterPar(P, I) :-
    padres(X),
    indios(Y),
    X >= 1,
    Y >= 1,
    P is X-1,
    I is Y-1.

listaDePares(Lista) :-
    listaDePares([], Lista), !.

listaDePares(ListaFinal, ListaFinal) :-
    indios(0), padres(0), !.
listaDePares(ListaInicial, Lista) :-
    obterPar(P, I),
    \+ member([P,I], ListaInicial),
    retract(padres(_)),
    retract(indios(_)),
    asserta(padres(P)),
    asserta(indios(I)),
    listaDePares([[P,I], ListaInicial], Lista).


Observações para a implementação dessa ideia:

Quando implementar o trabalho, você deverá modificar/adaptar as seguintes características:

  • Garantir que o predicado “obterPar” retorne todos os pares (vértices/nodos/estados) possíveis. Porém, sempre verificando o lado do barco.
    Outra alternativa é fazer esse predicado retornar somente os pares corretos, já seguindo a restrição de terem mais padres do que índios (ou a mesma quantidade) nas duas margens.
  • Ao verificar se o vértice/nodo/estado ( “\+ member([P,I], ListaInicial)”) já pertence a lista, você também deve considerar:
    • sempre a quantidade de padres e índios do mesmo lado da margem;
    • o lado que está o barco.
      Isso é necessário porque o estado [3,1] com o barco do lado esquerdo do rio é diferente do estado [3,1] com o barco do lado direito do rio. Dessa forma, deve-se verificar e guardar na ListaInicial os estados [PadresDoLadoEsquerdo, IndiosDoLadoEsquerdo, LadoDoBarco] ao invés de fazer como no exemplo acima, que está: [Padres,Indios] sem se importar com a quantidade de cada lado e também com a posição do barco.
  • Criar as restrições necessárias para que novos vértices/nodos/estados sejam válidos, ou seja, com a menor ou igual quantidade de índios do que padres nos dois lados do rio.

Postado em Inteligência Artificial.