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

[avva]

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

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

Comments

[tlkh]

Возможно, профессиональное. Я терпеть не могу игры и головоломки, которые включают в себя бектрекинг в уме. Мозг сразу возводит стенку - нафига я занимаюсь тем, что компьютер сделает быстрее и лучше?

[urease]

Это связано с проблемами памяти. У меня - точно такое же отношение к мысленному бэктрэкингу по причине памяти. Я перестал играть в шахматы в 10 лет после того как выяснилось, что бэктрэкинг приводит к сильной головной боли.

[tlkh]

Возможно, что блок, который ставит мозг (в виде резко концентрированного ощущения скуки) действительно ограждает от проявления подобных проблем.
Однако если мысленный бэктрекинг нужен по работе, то проблем нет. Мозг начинает возмущаться, когда он предлагается в виде развлечения - таких вот головоломок, или шашек-шахмат.

[spamsink]

Вот и я в детстве, уж на что любил разные математические задачки, в том числе олимпиадные, к шахматам не испытывал никакого интереса.

[urease]

Интуитивно, 102 строка не должна особенно влиять, спасая очень немного времени. Так?

[colt_browning]

Кстати, Вы читали биографию Конвея Siobhan Roberts "Genius at play"? Замечательная книга.

[xaxam]

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

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

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

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

[livelight]

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

[xaxam]

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

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

[livelight]

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

[p_a_s_h_a]

Ну, вот так всё же жизненно: там, где нужно найти одно решение - автоматизация - проигрыш. Там, где нужно найти порядка 240 решений - автоматизация - преимущество.