TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
Loading...
Searching...
No Matches
TProcura

GitHub issues GitHub forks GitHub stars GitHub license

Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização:

  • procuras construtivas
  • procuras melhorativas (evolutivas e locais)
  • procuras adversas (minimax, alfa-beta, iterativo)

‍Documentação completa em:
👉 TProcura - Documentação

📑 Sumário

Sobre o Projeto

O TProcura junta testes paramétricos e implementação genérica de algoritmos de procura.
Em vez de alterar macros e recompilar a cada teste de mudança de parâmetros, propõe-se:

  • Estrutura para uma lista de parâmetros, gerida na superclasse
  • Gerar automaticamente todas as combinações de parâmertros que o utilizador desejar
  • Executar instâncias para cada combinação de parâmetros, e recolher indicadores solicitados
  • Exportar resultados em CSV para análises em Excel, R ou Python

A arquitetura baseia-se em superclasses que já implementam algoritmos de procura. O utilizador só precisa de:

  1. Herdar a classe adequada
  2. Redefinir métodos de geração de sucessores, avaliação ou operadores, para o problema concreto, conforme adequado
  3. Declarar novos parâmetros e indicadores, se desejar

Este projeto é utilizado nas Unidades Curriculares:

Funcionalidades

  1. Modo interativo, linha de comando ou MPI
  2. Geração automática de combinações de parâmetros
  3. Recolha de indicadores (tempo, custo, iterações, etc.)
  4. Exportação de resultados em CSV
  5. Procuras Construtivas:
    • Largura / Profundidade / Custo uniforme
    • Melhor-primeiro / A* / IDA* / Branch-and-Bound
  6. Procuras melhorativas:
    • Algoritmos Evolutivos - (futuro: Scatter Search, sistemas artificiais imunes, inteligência de enxames)
    • Escalada do Monte - (futuro: pesquisa tabu, arrefecimento simulado, GRASP, procura com vizinhança variável e muito alargada)
  7. Procuras adversas:
    • Minimax / Alfa-beta / iterativo / Hash-table de estados explorados (futuro: MCTS)

📦 Estrutura do Repositório

O repositório inclui 4 projetos principais, cada um com uma superclasse base para implementação de novos problemas:

TProcura
├─ TProcuraConstrutiva
│ └─ TProcuraAdversa
└─ TProcuraMelhorativa
  • TProcura: modos de execução (interativo, linha de comandos, MPI), gestão de parâmetros e indicadores, execução de testes.
  • TProcuraConstrutiva / TProcuraAdversa: algoritmos construtivos e adversos, exigem implementação de sucessores e heurística.
  • TProcuraMelhorativa: algoritmos melhorativos (solução inicial, vizinhança, mutação, cruzamento, avaliação).

Subclasses já fornecem operadores para diferentes representações, restando apenas implementar a avaliação.

── TProcuraMelhorativa
├─ TRepresentacaoBinaria
├─ TRepresentacaoInteira
├─ TRepresentacaoPermutacao
├─ TRepresentacaoReal
└─ TRepresentacaoArvore

Estrutura de Pastas

A estrutura do repositório é a seguinte:

TProcura
├─ Adversa/Construtiva/Melhorativa # pastas de projetos principais
│ └─ Teste # projeto de teste (não necessário para usar a biblioteca)
│ ├─ CasosTeste # ficheiros para testes de validação de alterações ao código
│ ├─ Resultados # ficheiros CSV de execução (não colocados no repositório)
│ └─ bin/x64 # (fora do repositório) pasta bin criada na compilação em linux ou x64 no Visual Studio
│ ├─ Debug
│ ├─ MPI
│ └─ Release
├─ Teste # mesma estrutura em todos os projetos
│ └─ ...
├─ docs # documentação em Markdown
└─ styles # estilos doxygen

Compilação e Execução

Na pasta <projeto>/Teste do projeto respetivo:

  • Linux:
    • Pré-requisito para MPI: instalar o Open MPI
      sudo apt-get update
      sudo apt-get install -y openmpi-bin libopenmpi-dev
    • Compilação: make ou make mpi
  • Windows (Visual Studio): selecionar a configuração desejada (Debug, Release ou MPI).

    ‍⚠️ Para MPI é necessário instalar previamente o MS MPI.

Executar o projeto:

  • Interativo: ./Executavel
  • Linha de comando: ./Executavel <argumentos> (ajuda: ./Executavel -h)
  • MPI: mpiexec -n 4 ./Executavel <argumentos>

Onde fica o executável:

  • Linux: <projeto>/Teste/bin/[Debug|MPI|Release]
  • Windows (Visual Studio): <projeto>/Teste/x64/[Debug|MPI|Release]

‍ℹ️ Os Makefile estão localizados em <projeto>/Teste, pois destinam-se apenas à compilação dos projetos de teste.

‍ℹ️ Os ficheiros CSV de resultados podem ser gravados em Resultados/ usando o parâmetro -R Resultados/<nome>.

Instalação

Clonar o projeto, compilar um dos projetos de teste e executar.

Opção 1 - Clonar o Repositório

git clone https://github.com/jcoelho72/TProcura.git

ou

Aceder a página do repositório e clique em **"Code" → "Open with Visual Studio"**.

Opção 2 - Download Manual

Aceder a página do repositório e clique em **"Code" → "Download ZIP"**.

Extraia os arquivos e siga as instruções de compilação (por exemplo, via Makefile, Visual Studio etc., conforme seu ambiente).

Opção 3 - Utilizar como Submódulo

Para integrar o TProcura como parte de outro projeto, utilize um submódulo:

git submodule add https://github.com/jcoelho72/TProcura.git

Uso

Para implementar um novo problema utilizando uma das superclasses pode:

  • identificar a superclasse mais adequada, e redefinir, criando uma subclasse;
  • readaptar um problema similar já implementado.

Superclasses:

Exemplos

Problemas de exemplo da classe TProcura:

  1. TesteTVetor

Problemas de exemplo da classe TProcuraConstrutiva:

  1. Aspirador (parte 1, parte 2)
  2. Puzzle 8
  3. 8 Damas
  4. Partição
  5. Artificial

Problemas de exemplo da classe TProcuraMelhorativa:

  1. 8 Damas CI (TCodificacaoInteira)
  2. 8 Damas CP (TCodificacaoPermutacao)
  3. Partição CB (TCodificacaoBinaria)
  4. ? (TCodificacaoReal)
  5. ? (TCodificacaoArvore)

Problemas de exemplo da classe TProcuraAdversa:

  1. Jogo do Galo
  2. Jogo em Linha

Esses exemplos servem tanto para testar o repositório quanto para servir de base para novas implementações.

Bibliografia

Licença

Distribuído sob a licença MIT. Veja o arquivo LICENSE para mais informações.