Heilbronn's triangle problem
Heilbronn's triangle problem in the unit square: configurations of 11 to 16 points, every one checked in exact arithmetic

| 1 | #!/usr/bin/env python3 |
| 2 | """A plain starting point: simulated annealing on the smallest triangle, in floating point. |
| 3 | |
| 4 | Usage: search.py N [SEED] [STEPS] > n<N>.txt (a few seconds for the defaults) |
| 5 | |
| 6 | It finds valid configurations some way below the best known ones. What it prints is judged by ../verify.py, exactly. |
| 7 | """ |
| 8 | import itertools |
| 9 | import math |
| 10 | import random |
| 11 | import sys |
| 12 | |
| 13 | |
| 14 | def smallest(p): |
| 15 | return min(abs((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) / 2 for a, b, c in itertools.combinations(p, 3)) |
| 16 | |
| 17 | |
| 18 | def anneal(n, seed=0, steps=100000): |
| 19 | rng = random.Random(seed) |
| 20 | p = [(rng.random(), rng.random()) for _ in range(n)] |
| 21 | now = best = smallest(p) |
| 22 | kept = p[:] |
| 23 | for k in range(steps): |
| 24 | heat = 1e-3 ** (1 + k / steps) # the temperature falls from 1e-3 to 1e-6 |
| 25 | step = 0.2 * 0.005 ** (k / steps) # and the moves shrink from 0.2 to 0.001 |
| 26 | i = rng.randrange(n) |
| 27 | old = p[i] |
| 28 | p[i] = tuple(min(1.0, max(0.0, c + rng.gauss(0, step))) for c in old) |
| 29 | new = smallest(p) |
| 30 | if new >= now or rng.random() < math.exp((new - now) / heat): |
| 31 | now = new |
| 32 | if new > best: |
| 33 | best, kept = new, p[:] |
| 34 | else: |
| 35 | p[i] = old |
| 36 | return best, kept |
| 37 | |
| 38 | |
| 39 | if __name__ == "__main__": |
| 40 | if len(sys.argv) < 2: |
| 41 | sys.exit(__doc__.strip()) |
| 42 | given = [int(a) for a in sys.argv[1:4]] |
| 43 | n, seed, steps = given + [0, 100000][len(given) - 1:] |
| 44 | best, kept = anneal(n, seed, steps) |
| 45 | print(f"# n = {n}: smallest triangle about {best:.6f}, found by examples/search.py {n} {seed} {steps}") |
| 46 | for x, y in kept: |
| 47 | print(f"{x:.6f} {y:.6f}") |