Jump to content
Fórum Script Brasil
  • 0

Busca bidirecional C#


guileoline
 Share

Question

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;
}
}
}
Link to comment
Share on other sites

1 answer to this question

Recommended Posts

  • 0

não consigo encontrar no menu do HD DUO S2 como fazer uma busca manual de uma TP especifica. O canal f#o#x S#p#o#r#t#s esta listado mas sem sinal, e gostaria de colocar o TP 11780h29900. Estou no 70?w. Como proceder passo a passo? Obrigado

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

  • Forum Statistics

    • Total Topics
      149.8k
    • Total Posts
      646.6k
×
×
  • Create New...