Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar um algoritmo que solucione o Problema das 3 Jarras ?

+1 voto
39 visitas
perguntada Jun 22 em Matemática por JoaoMaria (71 pontos)  
editado Jun 27 por JoaoMaria

Dado 3 jarras de capacidades 8, 5 e 3 litros. nenhuma delas tem qualquer marcação de medidas
A imagem será apresentada aqui.
O jarro de 8 litros está cheio de água, os demais estão vazios.
Usando essas 3 jarras, como separar 4 litros em um deles?

Compartilhe

1 Resposta

+1 voto
respondida Jun 22 por JoaoMaria (71 pontos)  
editado Jul 7 por JoaoMaria

Esse problema pode ser resolvido utilizando-se grafos. Antes de explicarmos o modelo adotado cabe algumas definições básicas acerca de grafos.
\(\quad\)Conceito Básicos da Teoria de Grafos
\(\quad\)Grafos
Um grafo \(G(V,A)\) é definido pelo par de conjuntos V e A, onde:
\(\quad\)V - conjunto não vazio: os vértices ou nodos do grafo;
\(\quad\)A - conjunto de pares ordenados \(a=(v,w), v\) e \(w ∈ V \): as arestas do grafo.
Seja, por exemplo, o grafo G(V,A) dado por:
\(\quad\)V = { p | p é uma pessoa }
\(\quad\)A = { (v,w) | < v é pai/mãe de w > }
Esta definição representa toda uma família de grafos. Um exemplo de elemento desta família (veja figura abaixo), é dado por:
\(\quad\)V = { Emerson, Isadora, Renata, Antonio, Cecília, Alfredo }
\(\quad\)A = {(Isadora, Emerson), (Antonio, Renata), (Alfredo, Emerson), (Cecília, Antonio), (Alfredo, Antonio) }
A imagem será apresentada aqui.
A relação definida por A não é simétrica pois se , não é o caso de . Há, portanto, uma orientação na relação, com um correspondente efeito na representação gráfica do Grafo.
O grafo acima é dito ser um grafo orientado (ou digrafo), sendo que as conexões entre os vértices são chamadas de arcos.

\(\quad\)Problema das três jarras - solução utilizando grafos
Sejam \(c_1\), \(c_2\) e \(c_3\) as capacidades das três jarras \(j_1\), \(j_2\) e \(j_3\). Então, um possível modelo para este problema é definir o grafo G(V,A) como:
\(V = \{ (q_1, q_2, q_3)\) onde \(q_n \) representam as quantidades de agua nas três jarras, sendo que:
\(0 \le q_1 \le c_1; 0 \le q_2 \le c_2; 0 \le q_3 \le c_3; q_1 + q_2 + q_3 = 8\} \)

\(A = \{ (e_1,e_2)\) | o estado \(e_2\) é alcançado partindo-se do estado \(e_1\) por meio de um único movimento de transposição de água de uma jarra para outra. Tal transposição é completada quando a jarra de origem é esvaziada ou quando a jarra de destino torna-se cheia\(\}\)
Sejam \(j_x\) e \(j_y\) respectivamente as jarras de origem e de destino da transposição. Segundo a definição das arestas acima, uma transposição é possível se a jarra de origem não estiver vazia \((q_x > 0)\) e o jarra de destino não estiver cheia \((q_y < c_y)\). A quantidade de água a ser transposta é dada pelo mínimo entre o que tem na jarra origem \((q_x)\) e o que ainda cabe na jarra de destino \((c_y - q_y)\). Como resultado de uma transposição, a quantidade do jarra \(j_x\) é diminuída em \(t\) litros, enquanto que a quantidade da jarra \(j_y\) é acrescida de \(t\) litros.
Assim, teremos:
\(\quad\)pré condição - \(q_x > 0\) e \((q_y < c_y)\) e \((x ¹ y)\)
\(\quad\)ação - transposição de \(t = min(q_x, c_y - q_y)\) litros de \(p_x \rightarrow p_y\)
\(\quad\)pós condição - \(q'_x = q_x - t\) e \(q'_y = q_y + t\)
Considerando esta regra e escrevendo um algoritmo de busca em profundidade (DFS - Depth First Search), podemos obter todos os estados alcançáveis partindo-se do estado inicial \((8,0,0)\) até chegar ao nodo de destino \((4,4,0)\). O grafo resultante desta busca é apresentado na figura que se segue:
A imagem será apresentada aqui.

Para encontrar a melhor solução, pode-se obter o caminho de custo mínimo que vai do nodo \((8,0,0)\) até o \((4,4,0)\), considerando que cada aresta tem peso 1. Para tanto é necessário que se vá guardando a melhor solução à medida que as soluções vão sendo encontradas. o algoritmo geraEstados(), codificado em Python, é a implementação do caminho de custo mínimo, no qual a variável "visitado" é utilizada para armazenar a melhor solução.
Abaixo apresentamos a solução completa codificada em Python.
Iniciamos pelas bibliotecas que são utilizadas:

import os
import copy
import networkx as nx
import matplotlib.pyplot as plt

Abaixo, apresentamos as variáveis globais e a rotina que lê dados de um arquivo que será informado no programa principal

# Numero de jarras
numJarras=0
# Capacidade Maxima das Jarras
cap = []
# Litros a serem separados
estadoAlvo=0
# Lista dos estados visitados
visitado = {}
# Lista do caminho solução
cam = []

def le_dados(arq):
    return [[float(x) for x in line.split()] for line in arq]

Esse é o algoritmo recursivo codificado em Python que implementa a melhor solução de busca em profundidade.

def geraEstados(estado):
    # As Tres jarras sáo a,b,c
    a = estado[0]
    b = estado[1]
    c = estado[2]
    for i in range(numJarras-1,0,-1):
        if (estado[i] == alvo ):
            ans.append(estado)
            return True

    # Desempilha se o estado já foi visitado
    if ((a,b,c) in visitado):
        return False

    visitado[(a,b,c)] = 1

    # Esvaziar Jarra a
    if (estado[0] > 0):
        # Esvaziar a em b
        if (estado[0] + estado[1] <= capacidade[1]):
            if (geraEstados((0, estado[0] + estado[1] , estado[2]))):
                ans.append(estado)
                return True
        else:
            if (geraEstados((estado[0] - (capacidade[1] - estado[1]), capacidade[1], estado[2]))):
                ans.append(estado)
                return True
        # Esvaziar a em c
        if (a + c <= capacidade[2]):
            if (geraEstados((0, estado[1], estado[0] + estado[2]))):
                ans.append(estado)
                return True
        else:
            if (geraEstados((estado[0] - (capacidade[2] - estado[2]), estado[1], capacidade[2]))):
                ans.append(estado)
                return True

    # Esvaziar b
    if (estado[1] > 0):
        # Esvaziar b em a
        if (estado[0] + estado[1] <= capacidade[0]):
            if (geraEstados((estado[0] + estado[1], 0, estado[2]))):
                ans.append(estado)
                return True
        else:
            if (geraEstados((capacidade[0], estado[1] - (capacidade[0] - estado[0]), estado[2]))):
                ans.append(estado)
                return True
        # Esvaziar b em c
        if (estado[1] + estado[2] <= capacidade[2]):
            if (geraEstados((estado[0], 0, estado[1] + estado[2]))):
                ans.append(estado)
                return True
        else:
            if (geraEstados((estado[0], estado[1] - (capacidade[2] - estado[2]), capacidade[2]))):
                ans.append(estado)
                return True

    # Esvaziar c
    if (estado[2] > 0):
        # Esvaziar c em a
        if (estado[0] + estado[2] <= capacidade[0]):
            if (geraEstados((estado[0] + c, estado[1], 0))):
                ans.append(estado)
                return True
        else:
            if (geraEstados((capacidade[0], estado[1], estado[2] - (capacidade[0] - estado[0])))):
                ans.append(estado)
                return True
        # Esvaziar c em b
        if (estado[1] + estado[2] <= capacidade[1]):
            if (geraEstados((estado[0], estado[1] + estado[2], 0))):
                ans.append(estado)
                return True
        else:
            if (geraEstados((estado[0], capacidade[1], estado[2] - (capacidade[1] - estado[1])))):
                ans.append(estado)
                return True

    return False

Abaixo, apresentamos o programa principal. Inicialmente ele pede o nome do arquivo que contém as seguintes informações:
Número de jarras
Capacidade das jarras
Estado Inicial das jarras
Estado final das jarras
Desse modo essa solução pode ser implementada para quaisquer quantidades de jarras, desde que \(q_1>q_2\dots q_n\) e que o estado inicial seja \((q_1, 0,\dots ,0)\).
Além disso, ele apresenta as informações lidas e chama a rotina geraEstados()

if __name__ == "__main__":
    nome_arq = input('Entre com o nome do arquivo de dados =>')
    nome_arq = "Jarras.txt"
    arq = open(nome_arq, "r")
    dados = le_dados(arq.readlines())
    numJarras = int(dados[0][0])
    #  for i in range(len(dados[1]))
    cap = dados[1]
    estadoInicial = dados[2]
    estadoAlvo = dados[3][0]
    # estadoInicial=(8,0,0)
    print("Número de jarras=",numJarras)
    print("Capacidade das Jarras")
    for i in range(0,len(cap)):
        print("Jarra ",i+1," cap=",cap[i]," Lts")
    print("Estado Inicial=",estadoInicial)
    print("EStado Alvo=",estadoAlvo)
    print("\nIniciando ...")
    quant=copy.deepcopy(estadoInicial)
    geraEstados(quant)
    cam.append(estadoInicial)
    cam.reverse()
    for i in cam:
        print(i)

Resultado

    Entre com o nome do arquivo de dados =>Jarras.txt
Número de jarras= 3
Capacidade das Jarras
Jarra  1  cap= 8.0  Lts
Jarra  2  cap= 5.0  Lts
Jarra  3  cap= 3.0  Lts
Estado Inicial= [8.0, 0.0, 0.0]
EStado Alvo= 4.0

Iniciando ...
[8.0, 0.0, 0.0]
[3.0, 5.0, 0.0]
[0.0, 5.0, 3.0]
[5.0, 0.0, 3.0]
[5.0, 3.0, 0.0]
[2.0, 3.0, 3.0]
[2.0, 5.0, 1.0]
[7.0, 0.0, 1.0]
[7.0, 1.0, 0.0]
[4.0, 1.0, 3.0]
[4.0, 4.0, 0.0]

O grafo resultante da aplicação deste algoritmo, que representa a melhor solução para o problema, é apresentado na figura que se segue:

A imagem será apresentada aqui.

O arquivo Jarras.txt utilizado foi:

3
8 5 3
8 0 0
4

Onde:
1 - Na primeira linha é informado o número de jarras
2 - Na segunda linha são informados as capacidades das jarras (da maior para a menor)
3 - Na terceira linha são informados o estado inicial de utilização de cada jarra
4 - Na quarta linha é informado a quantidade de litros que se deseja separar

comentou Jul 6 por IgorNascimento (51 pontos)  
Não conseguir reproduzir o código. Você poderia disponibilizar o arquivo Jarras.txt?

O que utilizei foi:
1 2 3
8 5 3
8 0 0
3
comentou Jul 7 por JoaoMaria (71 pontos)  
editado Jul 7 por JoaoMaria
Inclui o arquivo Jarras.txt na resposta. Também detalhei como as informações são dispostas nele.
Muito obrigado pela avaliação
...