еще про кубики

[avva]

В дополнение к предыдущей записи про прекрасную головоломку "кубики Сома".

Прочитал статью, в которой программным путем находят все возможные решения, в 1985-м году на Фортране. Там это сводят к чистой линейной алгебре, проблема оптимизации

Comments

[xaxam]

Толя, я надеюсь, что вы слышали про такую задачу - piano mover's problem. Бытовая формулировка - можно ли вынести рояль из городской квартиры по коридорам и лестничной клетке.

Математическая задача гораздо интересней: вам предъявляют систему полиномиальных неравенств ("рояль вписывается в данный коридор") и спрашивают, является ли множество их решений связным ("рояль в комнате" и "рояль на улице").

Она сложна: в размерности n нужно примерно 2^2^n операций (от степени полиномов зависит менее критично). И проблема вовсе не в том, какими параметрами задают конфигурационное пространство, а какая-то высшая сила, непреодолимая.

Эта вот двойная экспонента - проклятие комбинаторных геометров...

[livelight]

А рояль крутить можно? Как это в полиномиальных уравнениях выглядит?

[xaxam]

Пространство конфигураций рояля - точка в шестимерном пространстве (скажем, координаты центра масс и три эйлеровых угла поворота). Условие, что рояль не пересекается с коридором - очень много разных соотношений, в основном квадратичных) типа неравенств. Скажем, если рояль считать кирпичом, а коридор - бесконечным, то это будут 8 уравнений "вершина попадает в коридор". Но если мы обносим угол, то этих условий недостаточно: одна вершина может быть ещё в комнате, другая - уже в коридоре, но сам рояль будет задевать угол.

Тем не менее все такие соотношения будут полиномиальными.

[livelight]

Уравнений этих не видел, но если они все эквивалентны геометрической задаче про рояль и коридоры - то откуда там двойной экспоненте взяться? Каждый коридор - выпуклая фигура, даже если его рассматривать в расширенном пространстве точек+поворотов, а задача поиска всех пересечений коридоров (в каждом из которых рояль имеет в своём распоряжении объединение их пространств) и пути рояля в этом графе из коридоров и их пересечений никак не тянет больше, чем на одинарную экспоненту (и о только если мы каким-то образом получим полный булеан разных пересечений коридоров, что вряд ли, учитывая их выпуклость)

[xaxam]

Есть целая наука про то, насколько сложными могут быть криволинейные алгебраические многогранники в n-мерном пространстве (множества, определённые алгебраическими равенствами и неравенствами). Например, можно оценить сверху множество кусков, из которых они состоят (обычные многогранники, заданные линейными неравенствами - выпуклы и состоят из одного куска). Можно дать явную оценку на число "дырок" разной размерности (топологические числа Бетти). Все эти оценки - явные, и предъявляются явные алгоритмы, позволяющие сказать, принадлежат ли две данные точки многогранника к одной компоненте связности (в точности задача о переноске рояля