Busca no espaço de estados

“Existem 2 jarros, um com capacidade para 4 litros de água e outro com capacidade para 3 litros. utilizando somente operações de ENCHER, ESVASIAR, DERRAMAR AGUA DE UM JARRO EM OUTRO, devemos encontrar uma seqüencia de operações que deixará o jarro com capacidade para 3 litros com 2 litros de água.”

Objetos e estados

• Objetos = (J3, J4);
• Estado inicial = (0,0);
• Estado Final = (2, -);

Operações possiveis

• ENCHER
• ESVASIAR
• DERRAMAR AGUA DE UM JARRO EM OUTRO

REGRAS

1. Encher J3
2. Encher J4
3. Esvaziar J3
4. Esvaziar J4
5. Derramar J3 no J4
6. Derramar J4 no J3

Algoritmo de Busca

T <- Vazio
E <- S0

enquanto E != 0, faça
	S <- removeprimeiro(E)
		se S Existe em (pertence a) G então
		Devolva caminho
	fim_se

	T <- T U S
	E <- E U Sucessores(S,A)
Fim_enquanto

Desenvolvi em java um programa que resolve esse problema;

import java.util.*;

public class Main {

 public static void main(String[] args) {
 // TODO code application logic here
 //ArrayList<Double> g = new ArrayList<Double>();

 Lista s0 = new Lista();
 Lista t = new Lista();
 Lista e = new Lista();
 Lista g = new Lista();
 Jarro jar = new Jarro();

 g.inserirValor(2.0);
 g.inserirValor(2.1);
 g.inserirValor(2.2);
 g.inserirValor(2.3);
 g.inserirValor(2.4);

 double s = 0.0;
 double solucao = 0;
 e.inserirValor(s);

 while(e.getLength() != 0){
 s=e.getPrimeiro();

 if(g.existe(s) == true){
 solucao = s;
 break;
 }

 t.inserirValor(s);
 jar.setJarros(s);

 if(t.existe(jar.primeiraRegra())!=true){
 e.inserirValor(jar.primeiraRegra());
 }

 if(t.existe(jar.segundaRegra())!=true){
 e.inserirValor(jar.segundaRegra());
 }

 if(t.existe(jar.terceiraRegra())!=true){
 e.inserirValor(jar.terceiraRegra());
 }

 if(t.existe(jar.quartaRegra())!=true){
 e.inserirValor(jar.quartaRegra());
 }

 if(t.existe(jar.quintaRegra())!=true){
 e.inserirValor(jar.quintaRegra());
 }

 if(t.existe(jar.sextaRegra())!=true){
 e.inserirValor(jar.sextaRegra());
 }

 e.excluirValor(s);
 s0.inserirValor(s);
 }

 System.out.println(solucao);

 }
}

class Jarro {
 private double jarros;

 public double getJarros() {
 return jarros;
 }

 public void setJarros(double jarros) {
 this.jarros = jarros;
 }

 public double primeiraRegra() {
 double tmp = jarros;
 int x = (int) jarros;

 double j = 0;

 for (int i = x; i < 3; i++) {
 j++;
 }
 tmp += j;
 return tmp;
 }

 public double segundaRegra() {
 double tmp = jarros;
 double fracao = tmp;
 fracao *= 10;
 fracao %= 10;
 int x = (int) fracao;

 double j = 0;

 for (int i = x; i < 4; i++) {
 j++;
 }
 fracao = j;
 fracao /= 10;
 tmp += fracao;
 return tmp;
 }

 public double terceiraRegra() {
 double tmp = jarros;
 int x = (int) jarros;
 double j = x;
 tmp -= j;
 return tmp;
 }

 public double quartaRegra() {
 double tmp = jarros;
 double fracao = tmp;
 fracao *= 10;
 fracao %= 10;
 fracao /= 10;
 tmp -= fracao;
 return tmp;
 }

 public double quintaRegra() {
 double tmp = jarros;
 double fracao = tmp;
 int y = (int) tmp;
 fracao *= 10;
 fracao %= 10;

 int x = (int) fracao;
 if (y > 0 && x > 0) {
 while (x < 4 && y > 0) {
 x++;
 y--;
 }
 }
 fracao = x;
 fracao /= 10;
 tmp = y;
 tmp += fracao;
 return tmp;
 }

 public double sextaRegra() {
 double tmp = jarros;
 double fracao = tmp;
 int y = (int) tmp;
 fracao *= 10;
 fracao %= 10;
 int x = (int) fracao;
 if (x > 0 && x > 0) {
 while (y < 3 && x > 0) {
 x--;
 y++;
 }
 }
 fracao = x;
 fracao /= 10;
 tmp = y;
 tmp += fracao;
 return tmp;
 }
}

class Lista {
 private ArrayList<Double> quantidade = new ArrayList<Double>();

 public void inserirValor(double x){
 quantidade.add(x);
 }

 public void excluirValor(double x){
 quantidade.remove(x);
 }

 public double getPrimeiro(){
 return quantidade.get(0);
 }

 public int getLength(){
 return quantidade.size();
 }

 public double getValor(int x){
 return quantidade.get(x);
 }

 public boolean existe(double x){
 for(int i=0;i<quantidade.size();i++){
 if(x==quantidade.get(i)){
 return true;
 }
 }
 return false;
 }
}