guileoline

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... alguém 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; } } }