Leaderboard

Refeito: vide informações na versão 11.3.3 Boa Sorte! # BigMaxRedutor v11.3.3 Solver C++20 para Lottery Covering Designs C(v, k, t, m) com t ≤ m. Encontra coberturas (k-sets) de tamanho mínimo b tais que todo m-set do universo é coberto em pelo menos t elementos por algum k-set. ## Arquitetura Pipeline em camadas, do mais leve ao mais agressivo: 1. **Smart-shrink / greedy-extend** — ajuste de b a partir de solução inicial existente. 2. **PDO paralelo** (8 workers, Parallel Diversification by Operators) — exploração estocástica com perturbação adaptativa. 3. **TLS-Dir** (Targeted Local Search Directed) — busca local dirigida com: - Random walk em platô com orçamento de movimentos laterais adaptativo (`LATERAL_BUDGET_BASE = 500`, `MAX = 2000`) - Tabu list de 512 estados para evitar ciclos - **LAHC** (Late Acceptance Hill Climbing) com histórico de 500 e até 10.000 iterações por chamada - Micro-greedy 1-swap e 2-swap exaustivos como último recurso 4. **Perturb-repair** acionado quando TLS-Dir estagna em platô profundo: - 4 modos rotativos: `pool` (remoção de jogos menos úteis), `ruin` (remoção uniforme), `force` (inclusão guiada de k-set que cobre m-sets descobertos), `double` (duas inclusões simultâneas para incompatibilidades combinatórias) - Remoção de 8 a 16 jogos por tentativa - Escolha de qual jogo remover é **guiada por overlap**: minimiza `excl_outside` = m-sets exclusivos do jogo que não seriam cobertos pelos k-sets sendo introduzidos - Probe (30s) → extended (120s) → aggressive (300s) escalonado por promissoridade 5. **SearchB** (binary search em b) para encontrar o menor b viável. ## Telemetria Saída `.jsonl` por execução com campos por chamada do TLS-Dir: `lat_ok`, `lat_tabu` (movimentos laterais aceitos vs rejeitados por tabu), `lahc_inv`, `lahc_ok` (invocações vs escapes do LAHC), `mg1_inv`, `mg1_ok`, `mg2_inv`, `mg2_ok` (micro-greedy 1-swap e 2-swap, invocações vs sucessos). Cada sucesso do `perturb_repair` registra `mode=` e `sub=fase` identificando qual estratégia destravou o problema. O relatório final do `perturb_repair` mostra distribuição percentual de invocações por modo e taxa de escalonamento para extended/aggressive. ## Robustez - Checkpoint salva via `write tmp → fsync → rename`. Atômico em termos de visibilidade e durável em termos de disco. No Windows usa `_commit()` do CRT (evita colisão de macros do `<windows.h>`). - `covered_t` é `uint16_t` saturado (suporta multiplicidade até 65.535), revertido de `uint8_t` em v10.1 após bug de saturação em problemas com `b > 255`. - `recalc_excl` com flag `excl_dirty` evita recálculos O(b·|ms_per|) redundantes quando não há `apply_swap` desde o último recálculo. ## Sumário das mudanças v11.3.3 - `LATERAL_BUDGET_BASE` 50 → 500 - `LATERAL_BUDGET_MAX` 500 → 2000 - `TABU_LIST_SIZE` 128 → 512 - `LAHC_MAX_ITERS` 3000 → 10000 - `LAHC_TIMEOUT_S` 30 → 60 - `PR_REMOVE_MIN` 3 → 8, `PR_REMOVE_MAX` 12 → 16 - Substituição guiada por overlap em `_pr_force_include` e `_pr_double_force_include` - Telemetria de modo no `perturb_repair` (`mode=%s sub=%s`) - `fsync` no checkpoint via `_commit()` portátil - Flag `excl_dirty` em `run_tls_directed` ## Arquivos principais | Arquivo | Responsabilidade | |---|---| | `bigmax_types.h` | Tipos, constantes, tabela binomial, sistema combinatório | | `bigmax_cover.h` | rank/unrank, expansão combinatória, cache de cobertura | | `bigmax_greedy.h` | Construção inicial e extensão direcionada | | `bigmax_worker.h` | PDO worker e TLS-Dir | | `bigmax_perturb_repair.h` | Kick estrutural com 4 modos | | `bigmax_shrink_repair.h` | Pool de jogos menos úteis para shrink | | `bigmax_checkpoint.h` | Persistência atômica + métricas JSONL | | `bigmax_solver.h/.cpp` | Orquestração de rounds e Record Breaker | | `main.cpp` | CLI | ## Requisitos - C++20 (testado com MSVC 2022 e g++ 11+) - Sem dependências externas; `<filesystem>`, `<thread>`, `<future>` da stdlib ## Limites conhecidos - `BinomTable::MAX_N = 64`. Problemas com V > 64 não compilam. - Cache `CoverCache::MAX_SIZE = 65536` (entradas LRU). - Para problemas com cost ≤ 4 em platôs combinatorialmente fechados (todos os jogos com `excl ≥ 1`), o solver tende a estagnar — é o diagnóstico empírico de que b está próximo do mínimo prático.