148 lines
2.8 KiB
C
148 lines
2.8 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <errno.h>
|
|
#include <time.h>
|
|
|
|
#include "alryslib.c"
|
|
|
|
|
|
double round_value(double value, int digits)
|
|
{
|
|
int p = pow(10, digits);
|
|
return (int)floor(value * p) / (double)p;
|
|
}
|
|
|
|
double local_search(double *steps, int size, int start, int stop, int digits)
|
|
{
|
|
int i, j, k, kmax;
|
|
double v, s, smax, cmax, backup, first, delta;
|
|
|
|
smax = score(steps, size);
|
|
|
|
for(k = start; k < stop; k += 2)
|
|
{
|
|
steps[k] = round_value(steps[k], digits);
|
|
}
|
|
|
|
first = -pow(10, -digits + 1);
|
|
delta = pow(10, -digits);
|
|
|
|
for(i = 0; i < 20; ++i)
|
|
{
|
|
kmax = -1;
|
|
cmax = -1.0;
|
|
for(k = start; k < stop; k += 2)
|
|
{
|
|
backup = steps[k];
|
|
for(j = 0; j < 21; ++j)
|
|
{
|
|
v = first + j * delta;
|
|
|
|
steps[k] = backup + v;
|
|
s = score(steps, size);
|
|
if(smax < s)
|
|
{
|
|
smax = s;
|
|
kmax = k;
|
|
cmax = backup + v;
|
|
}
|
|
}
|
|
steps[k] = backup;
|
|
}
|
|
if(kmax < 0) break;
|
|
steps[kmax] = cmax;
|
|
}
|
|
|
|
return score(steps, size);
|
|
}
|
|
|
|
double random_walk(double *steps, int size, int digits)
|
|
{
|
|
int k, l;
|
|
double v, delta;
|
|
|
|
delta = pow(10, -digits);
|
|
|
|
k = rand() % ((size - 8)/ 4 - 2);
|
|
l = rand() % 11;
|
|
v = (rand() % 3 - 1) * delta * l;
|
|
steps[8 + k * 4] += v;
|
|
v = (rand() % 3 - 1) * delta * l;
|
|
steps[10 + k * 4] += v;
|
|
++k;
|
|
v = (rand() % 3 - 1) * delta * l;
|
|
steps[8 + k * 4] += v;
|
|
v = (rand() % 3 - 1) * delta * l;
|
|
steps[10 + k * 4] += v;
|
|
|
|
return local_search(steps, size, MAX(8 + k * 4 - 8, 8), MIN(size - 4, 8 + k * 4 + 8), digits);
|
|
}
|
|
|
|
int main(int argc, char *argv[])
|
|
{
|
|
FILE *fp;
|
|
char *end;
|
|
long digits;
|
|
int size;
|
|
double delta, t, s, sbest, snext, scale;
|
|
double steps[1024], next[1024], best[1024];
|
|
|
|
errno = 0;
|
|
digits = (argc == 3) ? strtol(argv[1], &end, 10) : -1;
|
|
if(errno != 0 || end == argv[1] || digits < 2 || digits > 4)
|
|
{
|
|
fprintf(stderr, "Usage: explore [2-4] input_file\n");
|
|
return EXIT_FAILURE;
|
|
}
|
|
|
|
if((fp = fopen(argv[2], "r")) == NULL)
|
|
{
|
|
fprintf(stderr, "Cannot open input file.\n");
|
|
return EXIT_FAILURE;
|
|
}
|
|
|
|
input(fp, steps, &size);
|
|
|
|
srand(time(NULL));
|
|
|
|
memcpy(best, steps, size * 8);
|
|
sbest = score(best, size);
|
|
|
|
fprintf(stderr, "%f\n", sbest);
|
|
|
|
s = sbest;
|
|
t = 1.0;
|
|
|
|
scale = pow(10, digits + 3);
|
|
|
|
while(t > 0.1)
|
|
{
|
|
t *= 0.999;
|
|
|
|
memcpy(next, steps, size * 8);
|
|
snext = random_walk(next, size, digits);
|
|
|
|
if(sbest < snext)
|
|
{
|
|
sbest = snext;
|
|
fprintf(stderr, "%f\n", sbest);
|
|
memcpy(best, next, size * 8);
|
|
}
|
|
|
|
delta = snext - s;
|
|
if(delta >= 0 || rand() < RAND_MAX * exp(delta / t * scale))
|
|
{
|
|
s = snext;
|
|
memcpy(steps, next, size * 8);
|
|
}
|
|
}
|
|
|
|
fprintf(stderr, "-> %f\n", sbest);
|
|
|
|
output(best, size);
|
|
|
|
return EXIT_SUCCESS;
|
|
}
|
|
|