Wyzwanie optymalizacji determinantów

13

Rozważ 30 na 30 macierzy Toeplitza, których wszystkie wpisy to 0 lub 1. To wyzwanie jest prostym wyzwaniem optymalizacyjnym w celu znalezienia macierzy z największą możliwą determinantą.

Brak danych wejściowych

Wyjście A 30 na 30 Macierz Toeplitza, z których wszystkie są równe 0 lub 1 wraz z wyznacznikiem.

Wynik Wyznacznik macierzy, którą wyprowadzasz. Jeśli dwie osoby otrzymają ten sam wynik, pierwsza odpowiedź wygrywa.

Dotychczasowe wpisy

  • 65 455 857,159,975 w Matlabie autorstwa Nicka Algera (z grubsza (10 ^ 13,8)
  • 65 455 857,159,975 w Pythonie autor: isaacg (około 10 ^ 13,8)
  • 39 994 961 772 988 w Mathematica do 2012 rcampion (około 10 ^ 13,6)
  • 39 788,537,400,052 in R autor Flounderer (około 10 ^ 13,6)
  • 8 363 855 075 832 w Pythonie autor: Vioz- (około 10 ^ 12,9)
  • 6,984,314,690,903 w Julii przez Alexa A. (około 10 ^ 12,8)

Irytujące dodatkowe ograniczenia 16 lipca 2015 r

Jeśli jest to w ogóle możliwe, użyj arytmetyki arbitralnej lub o wysokiej precyzji, aby obliczyć ostateczną determinantę wyjściową, abyśmy mogli być pewni, co to naprawdę jest (zawsze powinna być liczbą całkowitą). W pythonie powinno to być pomocne.

code-challenge  math  optimization 
— Społeczność
źródło
Dziwi mnie, że ten problem nie został jeszcze rozwiązany. Czy odpowiedź znana jest z matryc krążących?
— xnor
1
@NickAlger Jeśli biblioteka jest publicznie dostępna dla wszystkich, możesz jej użyć.
— orlp
2
@immibis Niestety jest ich 2 ^ 59.
1
Interesujące jest to, że dwie niezależne metody osiągnęły macierz Toeplitza z dokładnie wyznacznikiem maksymalnej macierzy krążącej. Nie mam matematycznej intuicji, dlaczego - czy ten wyznacznik jest po prostu wspólny dla binarnych macierzy Toeplitza?
— lirtosiast
1
@ Min_25 Do jutra powinienem mieć maksymalnie 19. Otrzymasz kod / wartości w powiązanym pytaniu, Lembik. Dzięki algorytmom heurystycznym osiągnąłem dokładnie takie same wartości dla n = 30, jak do tej pory pozostałe dwa plakaty. Wiele razy, z udziałem losowości. Także z matrycami krążącymi w wyniku za każdym razem, gdy osiągnę to maksimum, chociaż moje wyszukiwanie nie jest ograniczone do krążących macierzy. BTW, kolejny zaskakujący (dla mnie) fakt: maksimum dla n = 15 wynosi dokładnie 2 ^ 17.
— Reto Koradi

Odpowiedzi:

11

Matlab, 65 455 857,159,975 (10 ^ 13,8159)

Metoda polega na wznoszeniu się gradientu we wnętrzu sześcianu [0,1] ^ 59, z wieloma losowymi początkowymi domysłami i zaokrąglaniu na końcu, aby wszystkie zera i jedynki.

Matryca:

0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0
0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1
1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1
1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1
1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0
0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1
1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1
1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1
1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0
0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1
1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0
0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0
0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0
0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1
1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0
0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0
0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1
1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0
0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1
1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1
1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0
0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1
1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0
0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0
0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0
0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0
0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1
1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1
1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1
1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0

Kod:

% Toeplitz 0-1 determinant optimization

n = 30;
m = n + n-1;

toeplitz_map = @(w) toeplitz(w(n:-1:1), w(n:end));

objective = @(w) det(toeplitz_map(w));

detgrad = @(A) det(A)*inv(A)';

toeplitz_map_matrix = zeros(n^2,m);
for k=1:m
    ek = zeros(m,1);
    ek(k) = 1;
    M = toeplitz_map(ek);
    toeplitz_map_matrix(:,k) = M(:);
end

gradient = @(w) (reshape(detgrad(toeplitz_map(w)),1,n^2)*...
                 toeplitz_map_matrix)';

%check gradient with finite differences
w = randn(m,1);
dw = randn(m,1);
s = 1e-6;
g_diff = (objective(w+s*dw) - objective(w))/s;
g = gradient(w)'*dw;
grad_err = (g - g_diff)/g_diff

warning('off')
disp('multiple gradient ascent:')
w_best = zeros(m,1);
f_best = 0;
for trial=1:100000
    w0 = rand(m,1);
    w = w0;
    alpha0 = 1e-5; %step size
    for k=1:20
        f = objective(w);
        g = gradient(w);
        alpha = alpha0;
        for hh=1:100
            w2 = w + alpha*g;
            f2 = objective(w2);
            if f2 > f
                w = w2;
                break;
            else
                alpha = alpha/2;
            end
        end

        buffer = 1e-4;
        for jj=1:m
            if (w(jj) > 1)
                w(jj) = 1 - buffer;
            elseif (w(jj) < 0)
                w(jj) = 0 + buffer;
            end
        end
    end

    w = round(w);
    f = objective(w);
    if f > f_best
        w_best = w;
        f_best = f;
    end
    disp(trial)
    disp(f_best)
    disp(f)
end

M = toeplitz_map(w_best);

Matematyka obliczania gradientu:

W produkcie elementarnym wewnętrznym (Tj., Produkt wewnętrzny Hilberta-Schmidta) gradient wyznacznika ma reprezentatywność Riesz G podaną przez

G = det (A) A ^ (- *).

Mapa J od zmiennych optymalizacyjnych (wartości diagonalnych) do macierzy toeplitz jest liniowa, więc ogólny gradient g jest kompozycją tych dwóch map liniowych,

g = (vec (G) * J) ”,

gdzie vec () jest operatorem wektoryzacji, który pobiera macierz i rozwija ją do wektora.

Wejście wewnętrzne gradientu:

Po tym wszystkim, co musisz zrobić, to wybrać początkowy wektor wartości przekątnych w_0, a dla niektórych małych stopni kroku iteracja alfa:

  1. w_proposed = w_k + alpha * g_k

  2. aby uzyskać w_ (k + 1), weź w_proposed i skróć wartości poza [0,1] do 0 lub 1

  3. powtarzaj, aż będziesz zadowolony, następnie zaokrąglij wszystko do 0 lub 1.

Mój wynik osiągnął ten wyznacznik po przeprowadzeniu około 80 000 prób z jednolitymi losowymi domysłami.

— Nick Alger
źródło
Podane łącze OEIS dotyczyło macierzy krążących, które są szczególnym przypadkiem matryc Topelitz. Tak więc nadal jest możliwe.
— isaacg
@isaacg A także bardzo prawdopodobne!
Tak, oczywiście, myliłem się co do tego. Zredagowałem swój post, aby go naprawić.
— Nick Alger,
1
Tak, osiągnął tę wartość przy iteracji 250 i pozostał tam przez 100 000 iteracji. Wektor definiujący matrycę Toeplitz 18x18 z determinantą 2994003 wynosił [0,0,0,1,0,1,1,1,1,0,1,1,0,0,0,1,0,1,0, 0,0,1,0,1,1,1,1,1,,1,1,0,0,0,1,0], gdzie kolejność idzie od dolnego lewego do prawego górnego rogu.
— Nick Alger,
2
Przyznałem Ci zwycięstwo, gdy wpadłeś na nowy pomysł i uzyskałeś najwyższy numer IIRC. Aha, a to pokazuje, dlaczego twoja odpowiedź działa math.stackexchange.com/questions/1364471/… .
11

Python 2 z Numpy, 65 455 857,159,975 ~ = 10 ^ 13,8

To wspinaczka pod górę, tak prosta, jak to tylko możliwe. Ostateczne obliczenie determinanty wykonane przy użyciu SymPy w celu uzyskania dokładnego wyniku. Wszystkie macierze znalezione z tym wyznacznikiem są w obiegu.

Macierze znalezione z tą determinantą, podane jako wartość przekątnej od dolnego lewego do górnego prawego:

01000100101101000011100111011101000100101101000011100111011
01011101110011100001011010010001011101110011100001011010010
01100001000111011101001110100101100001000111011101001110100
01110100111010010110000100011101110100111010010110000100011
01011101110001000011010010111001011101110001000011010010111
01000101100010110100111101110001000101100010110100111101110
01000100101101000011100111011101000100101101000011100111011

Pierwszy, jako macierz:

[[1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1]
 [1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1]
 [1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0]
 [0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1]
 [1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1]
 [1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1]
 [1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0]
 [0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0]
 [0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1]
 [1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1]
 [1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1]
 [1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0]
 [0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0]
 [0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0]
 [0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0]
 [0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1]
 [1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0]
 [0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1]
 [1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1]
 [1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0]
 [0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1]
 [1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0]
 [0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0]
 [0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1]
 [1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0]
 [0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0]
 [0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0]
 [0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1]
 [1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0]
 [0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1]]

Kod:

import numpy as np
import sympy as sp
import random
import time
SIZE = 30

random.seed(0)

def gen_diag():
    return [random.randint(0, 1) for i in range(SIZE*2 - 1)]

def diag_to_mat(diag):
    return [diag[a:a+SIZE] for a in range(SIZE-1, -1, -1)]

def diag_to_det(diag):
    matrix = diag_to_mat(diag)
    return np.linalg.det(matrix)

def improve(diag):
    old_diag = diag
    really_old_diag = []
    while really_old_diag != old_diag:
        really_old_diag = old_diag
        for flip_at in range(SIZE * 2 - 1):
            new_diag = old_diag[:]
            new_diag[flip_at] ^= 1
            old_diag = max(old_diag, new_diag, key=diag_to_det)
    return old_diag

overall_best_score = 0
time.clock()
while time.clock() < 500:
    best = improve(gen_diag())
    best_score = diag_to_det(best)
    if best_score > overall_best_score:
        overall_best_score = best_score
        overall_best = best
        print(time.clock(), sp.Matrix(diag_to_mat(overall_best)).det(), ''.join(map(str,overall_best)))


mat = diag_to_mat(overall_best)

sym_mat = sp.Matrix(mat)

print(overall_best)
print(sym_mat.det())
— isaacg
źródło
1
To szalone. Dobra robota.
— Alex A.,
.227 jest trochę niepokojący. Czy uważasz, że istnieje sposób, aby być pewnym, czym tak naprawdę jest wyznacznik?
Wydaje się, że stackoverflow.com/questions/6876377/... może pomóc w ocenie ostatecznej determinanty?
@Lembik Thanks - SymPy załatwiło sprawę.
— isaacg
To naprawdę świetnie!
10

R, 39 788 537 400 052

Oto moja próba wykonania algorytmu genetycznego, ale tylko z rozmnażaniem bezpłciowym. Mam nadzieję, że poprawnie zrozumiałem wyzwanie. Edycja: przyspieszyłem trochę, wypróbowałem inne losowe ziarno i ograniczono do 100 pokoleń.

    options(scipen=999)

toeplitz <- function(x){
# make toeplitz matrix with first row
# x[1:a] and first col x[(a+1):n]
# where n is the length of x and a= n/2
# Requires x to have even length
#
# [1,1] entry is x[a+1]

N <- length(x)/2
out <- matrix(0, N, N)
out[1,] <- x[1:N]
out[,1] <- x[(N+1):length(x)]
for (i in 2:N){
  for (j in 2:N){
    out[i,j] <- out[i-1, j-1]
  }
} 

out
}

set.seed(1002)

generations <- 100
popsize <- 25
cols <- 60
population <- matrix(sample(0:1, cols*popsize, replace=T), nc=cols)
numfresh <- 5 # number of totally random choices added to population

for (i in 1:generations){

fitness <- apply(population, 1, function(x) det(toeplitz(x)) )
mother <- which(fitness==max(fitness))[1]

population <- matrix(rep(population[mother,], popsize), nc=cols, byrow=T)
for (i in 2:(popsize-numfresh)){
  x <- sample(cols, 1)
  population[i,x] <- 1-population[i,x]
}
for (i in (popsize-numfresh +1):popsize){
  population[i,] <- sample(0:1, cols, replace=T)
}


print(population[1,])
print(fitness[mother])
print(det(toeplitz(population[1,]))) # to check correct

}

Wynik:

print(population[1, 1:(cols/2)]) # first row
print(population[1, (cols/2+1):(cols)]) # first column (overwrites 1st row)

to <- toeplitz(population[1,])

for (i in 1:(cols/2)) cat(to[i,], "\n")

1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 
0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 
1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 
0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 
0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 
0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 
1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 
1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 
1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 
1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 
0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 
1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 
1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 
1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 
0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 
0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 
0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 
0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 
1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 
0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 
1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 
0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 
0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 
0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 
0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 
1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 
0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 
1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 
1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1
— Flądrarz
źródło
To jest bardzo miłe. Obecnie wygrywasz daleko.
Już nie :)
3

Julia, 6,984,314,690,902,998

To po prostu konstruuje 1 000 000 losowych macierzy Toeplitza i sprawdza ich determinanty, rejestrując maksimum napotkane. Mam nadzieję, że ktoś wymyśli eleganckie rozwiązanie analityczne, ale tymczasem ...

function toeplitz(a, b)
    n = length(a)
    T = Array(Int, n, n)
    T[1,:] = b
    T[:,1] = a
    for i = 2:n
        T[i,2:n] = T[i-1,1:n-1]
    end
    T
end

d = 0
A = Any[]

for i = 1:1000000
    # Construct two random 0,1 arrays
    r1 = rand(0:1, 30)
    r2 = rand(0:1, 30)

    # Compute the determinant of a toeplitz matrix constructed
    # from the two random arrays
    D = det(toeplitz(r1, r2))

    # If the computed determinant is larger than anything we've
    # encountered so far, add it to A so we can access it later
    D > d && begin
        push!(A, (D, r1, r2))
        d = D
    end
end

M,N = findmax([i[1] for i in A])

println("Maximum determinant: ", M, "\n")
println(toeplitz(A[N][2], A[N][3]))

Możesz wyświetlić wyniki tutaj .

— Alex A.
źródło
Zastanawiam się, jak dokładne jest obliczanie wyznacznika. Uważam, że obliczenia leżące u podstaw są wykonywane z podwójną precyzją? Ponieważ cyfry po przecinku to 0,998, prawdopodobnie istnieje duża szansa, że ​​najbliższa liczba całkowita jest nadal poprawną determinantą. Zasadniczo zaczniesz mieć problemy z precyzją zmiennoprzecinkową, stosując obliczenia ogólnego przeznaczenia, np. Oparte na standardowym rozkładzie LR, na te matryce, gdy staną się dość duże.
— Reto Koradi,
@RetoKoradi Wygląda na to, że używa dekompozycji LU, aby uzyskać wyznacznik.
— Alex A.,
3

Mathematica, 39 994,961,721,988 (10 ^ 13,60)

Prosta metoda optymalizacji symulowanego wyżarzania; brak optymalizacji lub strojenia jeszcze.

n = 30;
current = -\[Infinity];
best = -\[Infinity];
saved = ConstantArray[0, {2 n - 1}];
m := Array[a[[n + #1 - #2]] &, {n, n}];
improved = True;
iters = 1000;
pmax = 0.1;
AbsoluteTiming[
 While[improved || RandomReal[] < pmax,
   improved = False;
   a = saved;
   Do[
    Do[
      a[[i]] = 1 - a[[i]];
      With[{d = Det[m]},
       If[d > best,
          best = d;
          current = d;
          saved = a;
          improved = True;
          Break[];,
          If[d > current || RandomReal[] < pmax (1 - p/iters),
           current = d;
           Break[];,
           a[[i]] = 1 - a[[i]];
           ]
          ];
        ;
       ],
      {i, 2 n - 1}];,
    {p, iters}];
   ];
 ]
best
Log10[best // N]
a = saved;
m // MatrixForm

Przykładowe dane wyjściowe:

{20.714876,Null}
39994961721988
13.602
(1  1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0
0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0
0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0
0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0
0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1
1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0
0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0
0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0
0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0
0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1
1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1
1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0
0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1
1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1
1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0
0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1
1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1
1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1
1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0
0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1
1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1
1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0
0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0
0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0
0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0
0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1
1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0
0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1
1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1
1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1

)
— 2012 rcampion
źródło
1

Python 2, 8 363 855 075 832

W grę wchodzi bardzo podstawowa, prawie nieistniejąca strategia.

from scipy import linalg

start = 2**28
mdet  = 0
mmat  = []
count = 0
powr  = 1
while 1:
 count += 1
 v = map(int,bin(start)[2:].zfill(59))
 m = [v[29:]]
 for i in xrange(1,30):
     m += [v[29-i:59-i]]
 d = 0
 try: d = linalg.det(m, check_finite=False)
 except: print start
 if d > mdet:
     print d
     print m
     mdet = d
     mmat = m
     start += 1
     powr = 1
 else:
     start += 2**powr
     powr += 1
     if start>(2**59-1):
         start-=2**59-1
         powr = 1
 if count%10000==0: print 'Tried',count

Oto najlepsza macierz, jaką znalazła po ~ 5 580 000 próbach:

1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0
1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1
1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0
0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1
1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1
0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0
1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0
0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0
1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1
1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0
0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0
0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0
0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0
0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0
1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1
0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1
1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1
1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0
1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1
1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1
1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1
1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0
1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1
0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0
1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1
0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1

Nadal biegnie...

— Kade
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.