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;
}
}
}
