Ir ao conteúdo
  • Cadastre-se
guileoline

Busca bidirecional

Recommended Posts

Pessoal, bom dia. Não estou conseguindo implementar busca bidirecional na seguinte classe. Este algoritmo esta funcionando para matrizes até 3x7. Mas quando tento uma 8x8 que é O(n^64) fica inviavel... Alguem consegue me ajudar?

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using PasseioCavalo.DataStructure;
 
namespace PasseioCavalo
{
    public class PCAgente : Graph
    {
        private int[] estadoInicial;
        private int lin;
        private int col;
        public int iteracoes = 0;
        
        public PCAgente(int[] EstadoInicial, int l, int c)
        {
            estadoInicial = EstadoInicial;
            lin = l;
            col = c;
        }
 
        public int[] ObterSolucao()
        {
            if(ObterPosicaoAtual(estadoInicial) < 0)
            {
                for (int i = 0; i < estadoInicial.Length; i++)
                {
                    int[] estado = estadoInicial.Clone() as int[];
                    estado = 2;
                    Node inicial = new Node(CriarNome(estado), estado);
                    int[] solucao = BuscaSolucao(inicial);
                    if (solucao != null)
                        return solucao;
                }
                return null;
            }
            else{
                return BuscaSolucao(new Node(CriarNome(estadoInicial), estadoInicial));
            }
        }
 
        private int[] BuscaSolucao(Node inicial)
        {
            Queue<Node> queue = new Queue<Node>();
 
            queue.Enqueue(inicial);
            this.AddNode(inicial);
        
            while (queue.Count > 0)
            {
                iteracoes++;
                Node node = queue.Dequeue();
 
                if (AchouObjetivo(node))
                {
                    return GeraSolucao(node);
                }
 
                List<Node> estadosSucessores = FuncaoSucessor(node);
                foreach (Node n in estadosSucessores)
                {
                    if (Find(n.Name) == null)
                    {
                        this.AddNode(n);
                        this.AddEdge(n.Name, node.Name, 0);
                        queue.Enqueue(n);
                    }
                }
            }
            return null;
        }
 
        private List<Node> FuncaoSucessor(Node node)
        {
            List<Node> result = new List<Node>();
            int[] estadoAtual = (int[])node.Info;
            int valor = ObterPosicaoAtual(estadoAtual);
 
            int l = valor / col;
            int c = valor % col;
 
            int lmax = lin - 1;
            int cmax = col - 1;
 
            if ((l + 2) <= lmax && (c + 1) <= cmax)
            {
                int pos = ((l + 2) * col) + (c + 1);
                int[] estado = estadoAtual.Clone() as int[];
                if (estado[pos] != 1)
                {
                    estado[valor] = 1;
                    estado[pos] = 2;
                    result.Add(new Node(CriarNome(estado), estado));
                }
            }
            if ((l + 2) <= lmax && (c - 1) >= 0)
            {
                int pos = ((l + 2) * col) + (c - 1);
                int[] estado = estadoAtual.Clone() as int[];
                if (estado[pos] != 1)
                {
                    estado[valor] = 1;
                    estado[pos] = 2;
                    result.Add(new Node(CriarNome(estado), estado));
                }
                
            }
            if ((l - 2) >= 0 && (c + 1) <= cmax)
            {
                int pos = ((l - 2) * col) + (c + 1);
                int[] estado = estadoAtual.Clone() as int[];
                if (estado[pos] != 1)
                {
                    estado[valor] = 1;
                    estado[pos] = 2;
                    result.Add(new Node(CriarNome(estado), estado));
                }
            }
            if ((l - 2) >= 0 && (c - 1) >= 0)
            {
                int pos = ((l - 2) * col) + (c - 1);
                int[] estado = estadoAtual.Clone() as int[];
                if (estado[pos] != 1)
                {
                    estado[valor] = 1;
                    estado[pos] = 2;
                    result.Add(new Node(CriarNome(estado), estado));
                }
            }
 
            if ((c + 2) <= cmax && (l + 1) <= lmax)
            {
                int pos = ((l + 1) * col) + (c + 2);
                int[] estado = estadoAtual.Clone() as int[];
                if (estado[pos] != 1)
                {
                    estado[valor] = 1;
                    estado[pos] = 2;
                    result.Add(new Node(CriarNome(estado), estado));
                }
            }
            if ((c + 2) <= cmax && (l - 1) >= 0)
            {
                int pos = ((l - 1) * col) + (c + 2);
                int[] estado = estadoAtual.Clone() as int[];
                if (estado[pos] != 1)
                {
                    estado[valor] = 1;
                    estado[pos] = 2;
                    result.Add(new Node(CriarNome(estado), estado));
                }
            }
 
            if ((c - 2) >= 0 && (l + 1) <= lmax)
            {
                int pos = ((l + 1) * col) + (c - 2);
                int[] estado = estadoAtual.Clone() as int[];
                if (estado[pos] != 1)
                {
                    estado[valor] = 1;
                    estado[pos] = 2;
                    result.Add(new Node(CriarNome(estado), estado));
                }
            }
            if ((c - 2) >= 0 && (l - 1) >= 0)
            {
                int pos = ((l - 1) * col) + (c - 2);
                int[] estado = estadoAtual.Clone() as int[];
                if (estado[pos] != 1)
                {
                    estado[valor] = 1;
                    estado[pos] = 2;
                    result.Add(new Node(CriarNome(estado), estado));
                }
            }
            return result;
        }
 
        private int ObterPosicaoAtual(int[] estado)
        {
            for (int i = 0; i < estado.Length; i++)
                if(estado==2)
                    return i;
            return -1;
        }
 
        private int[] GeraSolucao(Node node)
        {
            List<Node> lista = this.DepthFirstSearch(node.Name);
            List<int> result = new List<int>();
 
            for (int i = 0; i < lista.Count; i++)
            {
                Node n = lista;
                int[] estado = (int[])n.Info;
                for (int j = 0; j < estado.Length; j++)
                    if (estado[j] == 2)
                    {
                        result.Add(j);
                        break;
                    }
            }
            result.Reverse();
            return result.ToArray();
        }
 
        
        private bool AchouObjetivo(Node node)
        {
            int[] estado = (int[])node.Info;
            int qtdeZero = 0;
            foreach (int i in estado)
                if (i == 0)
                    qtdeZero++;
            return qtdeZero == 0 ? true : false;
        }
 
        private string CriarNome(int[] valor)
        {
            string nome = "";
            foreach (int i in valor)
                nome += i.ToString();
            return nome;
        }
    }
}
 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×