В связи с загадкой Slither Link мне было интересно: предположим, что у меня сетка квадратных ячеек, и я хочу найти простой цикл ребер сетки, равномерно случайным образом среди всех возможных простых циклов.n×nn×nn\times n Один из способов сделать это - использовать цепь Маркова, состояния которой...
Рассмотрим следующую проблему: Входные данные : гиперплоскость ЧАС= { y ∈ RN:Tу = б }H={y∈Rn:aTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\} , задается вектором a ∈ ZNa∈Zn\mathbf{a} \in \mathbb{Z}^n и b ∈ Zb∈Zb \in \mathbb{Z} в стандартном двоичном представлении. Выход : x...
Я задавал этот вопрос несколько недель назад в mathoverflow , но не получил ответа. Здесь под 3D-сеткой с длиной стороны я имею в виду граф G = ( V , E ) с V = { 1 , … , k } 3 и E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | а - х | + | б - у | + | сkkkG=(V,E)G=(V,E)G=(V,E)V={1,…,k}3V={1,…,k}3V=...
Hiroimono является популярной головоломкой Complete. Я заинтересован в вычислительной сложности связанной головоломки.NпNPNP Проблема в: Входные данные : заданный набор точек на квадратной сетке x n и целое число kNnnNnnКkk Вопрос : существует ли прямолинейный многоугольник (его стороны параллельны...
Сначала спросили по математике. Без ответов. Предположим, у меня есть плоский граф с плоским вложением, как мне найти разложение дерева? Каково оптимальное разложение дерева by- квадратной сетки? Не совсем уверен, как определить «оптимальный», но следует различать разложение с одним большим мешком...