C ++ (heurystyczny): 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086
Jest to nieco poniżej wyniku Petera Taylora, będąc o 1 do 3 niższym dla n=7, 9i 10. Zaletą jest to, że jest znacznie szybszy, więc mogę uruchomić go dla wyższych wartości n. I można to zrozumieć bez jakiejkolwiek fantazyjnej matematyki. ;)
Bieżący kod jest zwymiarowany do uruchomienia n=15. Czasy pracy zwiększają się z grubsza o współczynnik 4 dla każdego wzrostu w n. Na przykład było to 0,008 sekundy dla n=7, 0,07 sekundy dla n=9, 1,34 sekundy dla n=11, 27 sekund dla n=13i 9 minut dla n=15.
Użyłem dwóch kluczowych obserwacji:
- Zamiast operować na samych wartościach, heurystyka działa na liczeniu tablic. W tym celu najpierw generowana jest lista wszystkich unikalnych tablic zliczających.
- Korzystanie z tablic zliczających o małych wartościach jest bardziej korzystne, ponieważ eliminują one mniej miejsca na rozwiązanie. Opiera się to na każdym liczyć
cz wyłączeniem zakres c / 2do 2 * cinnych wartości. W przypadku mniejszych wartości cten zakres jest mniejszy, co oznacza, że przy jego użyciu wykluczonych jest mniej wartości.
Generuj unikalne tablice liczące
Wykorzystałem tę brutalną siłę, iterując wszystkie wartości, generując tablicę zliczeń dla każdej z nich i ujednolicając wynikową listę. Z pewnością można to zrobić bardziej efektywnie, ale jest wystarczająco dobre dla rodzajów wartości, z którymi operujemy.
Jest to niezwykle szybkie w przypadku małych wartości. W przypadku większych wartości narzut staje się znaczny. Na przykład n=15używa około 75% całego środowiska wykonawczego. To zdecydowanie byłby obszar, na który należy zwrócić uwagę, gdy próbuje się wznieść znacznie wyżej n=15. Problemem może stać się nawet użycie pamięci do budowania listy tablic zliczających dla wszystkich wartości.
Liczba unikalnych tablic zliczających wynosi około 6% liczby wartości n=15. Ta względna liczba maleje wraz ze nwzrostem.
Chciwy wybór wartości tablicy zliczającej
Główna część algorytmu wybiera zliczanie wartości tablic z wygenerowanej listy, stosując proste podejście zachłanne.
W oparciu o teorię, że korzystanie z tablic zliczających z małą liczbą jest korzystne, tablice zliczające są sortowane według sumy ich zliczeń.
Są one następnie sprawdzane w kolejności i wybierana jest wartość, jeśli jest zgodna ze wszystkimi poprzednio używanymi wartościami. Oznacza to jedno pojedyncze przejście liniowe przez unikalne tablice zliczające, w których każdy kandydat jest porównywany z wcześniej wybranymi wartościami.
Mam kilka pomysłów, w jaki sposób heurystykę można potencjalnie poprawić. Wydawało się to jednak rozsądnym punktem wyjścia, a wyniki wyglądały całkiem dobrze.
Kod
To nie jest wysoce zoptymalizowane. W pewnym momencie miałem bardziej rozbudowaną strukturę danych, ale potrzebowałem więcej pracy, aby ją uogólnić n=8, a różnica w wydajności nie wydawała się bardzo znacząca.
#include <cstdint>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>
typedef uint32_t Value;
class Counter {
public:
static void setN(int n);
Counter();
Counter(Value val);
bool operator==(const Counter& rhs) const;
bool operator<(const Counter& rhs) const;
bool collides(const Counter& other) const;
private:
static const int FIELD_BITS = 4;
static const uint64_t FIELD_MASK = 0x0f;
static int m_n;
static Value m_valMask;
uint64_t fieldSum() const;
uint64_t m_fields;
};
void Counter::setN(int n) {
m_n = n;
m_valMask = (static_cast<Value>(1) << n) - 1;
}
Counter::Counter()
: m_fields(0) {
}
Counter::Counter(Value val) {
m_fields = 0;
for (int k = 0; k < m_n; ++k) {
m_fields <<= FIELD_BITS;
m_fields |= __builtin_popcount(val & m_valMask);
val >>= 1;
}
}
bool Counter::operator==(const Counter& rhs) const {
return m_fields == rhs.m_fields;
}
bool Counter::operator<(const Counter& rhs) const {
uint64_t lhsSum = fieldSum();
uint64_t rhsSum = rhs.fieldSum();
if (lhsSum < rhsSum) {
return true;
}
if (lhsSum > rhsSum) {
return false;
}
return m_fields < rhs.m_fields;
}
bool Counter::collides(const Counter& other) const {
uint64_t fields1 = m_fields;
uint64_t fields2 = other.m_fields;
for (int k = 0; k < m_n; ++k) {
uint64_t c1 = fields1 & FIELD_MASK;
uint64_t c2 = fields2 & FIELD_MASK;
if (c1 > 2 * c2 || c2 > 2 * c1) {
return false;
}
fields1 >>= FIELD_BITS;
fields2 >>= FIELD_BITS;
}
return true;
}
int Counter::m_n = 0;
Value Counter::m_valMask = 0;
uint64_t Counter::fieldSum() const {
uint64_t fields = m_fields;
uint64_t sum = 0;
for (int k = 0; k < m_n; ++k) {
sum += fields & FIELD_MASK;
fields >>= FIELD_BITS;
}
return sum;
}
typedef std::vector<Counter> Counters;
int main(int argc, char* argv[]) {
int n = 0;
std::istringstream strm(argv[1]);
strm >> n;
Counter::setN(n);
int nBit = 2 * n - 1;
Value maxVal = static_cast<Value>(1) << nBit;
Counters allCounters;
for (Value val = 0; val < maxVal; ++val) {
Counter counter(val);
allCounters.push_back(counter);
}
std::sort(allCounters.begin(), allCounters.end());
Counters::iterator uniqEnd =
std::unique(allCounters.begin(), allCounters.end());
allCounters.resize(std::distance(allCounters.begin(), uniqEnd));
Counters solCounters;
int nSol = 0;
for (Value idx = 0; idx < allCounters.size(); ++idx) {
const Counter& counter = allCounters[idx];
bool valid = true;
for (int iSol = 0; iSol < nSol; ++iSol) {
if (solCounters[iSol].collides(counter)) {
valid = false;
break;
}
}
if (valid) {
solCounters.push_back(counter);
++nSol;
}
}
std::cout << "result: " << nSol << std::endl;
return 0;
}
L1[i]/2 <= L2[i] <= 2*L1[i].