heuristic suite

Suíte heurística

Nota importante

O projeto não está mais sob manutenção. Visite Linq para A* para obter a versão mais recente.

Visão geral

A suíte heurística é uma implementação experimental de uma série de algoritmos heurísticos na programação genérica. O projeto tem como objetivo fornecer uma infraestrutura que possa ser aplicada a qualquer quebra -cabeça - desde que o quebra -cabeça possa ser resolvido com o algoritmo.

Algoritmos implementados:

• UM*
• Aprofundamento iterativo A* (Ida*)
• Melhor primeira pesquisa
• Melhor Pesquisa Recursiva (RBFs)

A implementação é totalmente orientada a objetos e tem vantagens do mecanismo de comparação de estrutura .NET de estrutura interno, como o ICOMPARER (T) e o iEqualityComparer (t) para criar grande compatibilidade com o padrão .NET padrão e o ecossistema .NET inteiro. O código -fonte pode ser facilmente trazido para outras plataformas, como Unity e Xamarin.

Resolvendo quebra -cabeça com algoritmo

Para aplicar o algoritmo ao quebra -cabeça, são necessárias as seguintes implementações:

1. Definição da etapa O tipo que define a etapa do quebra -cabeça será necessário para implementar a interface ISTEP (TKEY). A propriedade Key serve a dois propósitos:

   • Para testar se duas etapas são equivalentes. Por exemplo: a mesma posição na placa.
   • Para comparar duas etapas para determinar qual tem melhor pontuação. Por exemplo: a distância entre a posição A e a meta e a distância entre a posição B e o objetivo, quanto mais próxima é uma pontuação melhor.

2. As etapas de comparação de etapas são comparadas entre si, com base na propriedade Key para determinar qual tem melhor pontuação. A comparação pode ser feita de uma das seguintes maneiras:

   • A implementação do ICOMPARABLE (TKEY).
   • Uma instância personalizada do ICOMPARER (TKEY).
   • A função H (n) explicitamente dada é Key .

3. As etapas disponíveis da etapa atual da próxima etapa podem ser fornecidas implementando a interface INextStepFactory(TKey, TStep) ou fornecendo NextStepFactory Delegate.

Depois disso, o algoritmo pode ser executado invocando o método FindSolution com from as etapas goal como parâmetros. Se a solução existir, cada uma das etapas poderá ser obtida chamando o método Enumerate . As etapas podem ser Reverse antes do início da enumeração.

Comparador heurístico e comparador heurístico discreto

O projeto fornece HeuristicComparer e DiscreteHeuristicComparer para diferentes cenários de comparação de etapas.

• Se a propriedade Key puder ser comparada diretamente entre si sem a função H (n) explícita, por padrão, DiscreteHeuristicComparer será usado para uma comparação mais rápida de etapas.
• Se a função H (n) for explicitamente necessária para comparar cada uma das etapas, o HeuristicComparer será usado para executar a estimativa tradicional f (n) = g (n) + h (n) .

Preferência de função heurística

A enumeração HeuristicFunctionPreference permite que os usuários alterem o equilíbrio da estimativa f (n) = g (n) + h (n) . Quando duas etapas são avaliadas da mesma pontuação, a enumeração decide qual funcionar, g (n) ou h (n) , será considerada primeiro. O equilíbrio alterado pode afetar o comportamento do algoritmo heurístico.

Exemplos

• Localização de caminho (algorithmforce.example.pathfinding)

  O exemplo demonstra o quebra -cabeça mais comum e tradicional que usa algoritmos heurísticos para resolver.

• 8-puzzle (algorithmforce.example.eightpuzzle)

  O exemplo demonstra como resolver o 8-puzzle com o algoritmo heurístico. As etapas iniciais e de gol do quebra -cabeça são mostradas abaixo:

• Puzzle invertido de moedas (algorithmforce.example.coinsflipping)

  Este exemplo demonstra como o jogo ai resolve o quebra -cabeça que lançam moedas. No quebra -cabeça, apenas um par de moedas adjacentes pode ser invertido ao mesmo tempo. Todas as dez moedas que são a cabeça são o objetivo. O quebra -cabeça é inspirado no Brilliant.org.

Mais exemplos serão adicionados no futuro.

Plataforma

Atualmente, o projeto tem como alvo o .NET Core e .Net Framework 4.5 ou acima.