Задача о передвижении дивана: численное решение с площадью 2,222? ⇐ Python

[Anonymous]

Я получил численное решение задачи о движущемся диване с площадью примерно 2,222. Это значение превышает текущую ведущую нижнюю границу (диван Гервера) ≈2,2195.
Мой диван сохраняет более близкую близость к углу (0,0) во время движения по сравнению с диваном Гервера.
Код для построения графиков доступен на GitHub. Правдоподобен ли этот численный результат? Спасибо за ваши идеи.




Минимальный воспроизводимый код Python, приведенный ниже, может достичь области 2,195 за 1 секунду.
import time
import numpy as np
import taichi as ti
import matplotlib.pyplot as plt

ti.init(arch=ti.gpu)

# Number of (x,y) points, including start and end, i.e., d(theta) = 1 / (n1-1)
# The larger this number is, the denser the serrations within the arc for area calculation
n1 = 200

# Sofa x-coordinate differentiation
n_sofa_dx = 2000

# Sofa width: corridor width is 1, sofa width slightly greater than 3, plus gaps left on both sides
sofa_img_width = 4
world_div_sofa = sofa_img_width / n_sofa_dx

# Resolution of the sofa edge image
sofa_img_dpi = 800

# The upper boundary is limited by y=1 and x=1 on the left and right sides, respectively. The lower boundary is limited by x=0, y=0, (0,0)
sofa_bound = ti.Vector.field(2, ti.f32, shape=n_sofa_dx)

# Position of the first (x,y) point (slightly greater than: sofa width / 2 - 1), which is also the critical point for theta = 0
xy_turn = -0.75

# Iterate for the optimal solution
sofa_area_max = 0

# Initialize trigonometric function values -pi/2 * i/n (0 1e-6:
upper_bound_min = ti.min(upper_bound_min, (1.0 - y_center - sin_theta * x_sofa) / cos_theta)
upper_bound = ti.min(upper_bound, upper_bound_min)

# lower_bound = max(min(_, _))
lower_bound_min = 0.5
if sin_theta < -1e-6:
lower_bound_min = ti.min(lower_bound_min, ( x_center + cos_theta * x_sofa) / sin_theta)
if cos_theta > 1e-6:
lower_bound_min = ti.min(lower_bound_min, (-y_center - sin_theta * x_sofa) / cos_theta)
lower_bound = ti.max(lower_bound, lower_bound_min)

sofa_bound[1] = upper_bound
sofa_bound[0] = lower_bound

@ti.kernel
def sofa_to_area() -> ti.f32:
area = 0.0
for i in range(n_sofa_dx):
x = sofa_bound
area += ti.max(x[1] - x[0], 0)
area *= world_div_sofa
return area

def xy_to_area():
xy_to_sofa()
return sofa_to_area()

################################
# iter
################################

def iter_once(i, f_mutate=None, delta=0.1, sigma=1.0):

global iter_count
global sofa_area_max

backup_xy()
f_mutate(i, delta, sigma)
smooth_xsin()
smooth_ycos()
area_new = xy_to_area()

if area_new > sofa_area_max:
sofa_area_max = area_new
else:
revovery_backup_xy()

iter_count += 1
if iter_count % 100 == 0:
speed = int(iter_count / (time.time() - t0 + 1e-6))
print(f"\rarea_max={sofa_area_max:.5f}, area={area_new:.5f}, speed={speed}/sec, sigma={sigma:.2f} ", end="")

def get_random_delta():
return np.clip(np.random.randn() * max(1 - sofa_area_max / 2.2, 0.01), -0.1, 0.1)

t0 = time.time()
iter_count = 0
try:
while 1:
for sigma in (n1, n1//2, n1//4, n1/16, n1/64, n1/256):
# Start point (0,0), end point (-0.5, -0.5) are fixed
for i in np.random.permutation(range(1, n1-1)):
iter_once(i, mutate_xsin, get_random_delta()/sigma, sigma)
iter_once(n1-1-i, mutate_ycos, get_random_delta()/sigma, sigma)

except KeyboardInterrupt:
pass


Подробнее здесь: https://stackoverflow.com/questions/798 ... a-of-2-222