Сложная проблема динамического программирования

Question

Это урезанная версия проблемы с компьютерным зрением, которую мне нужно решить.Предположим, вам заданы параметры n, q, и вам нужно подсчитать количество способов присвоения целых чисел 0 .. (q-1) элементам сетки n-на-n, так что для каждого назначения все следующие значения истинны

1. Нет двух соседей (по горизонтали или вертикали), имеющих одинаковое значение.
2. Значение в позициях (i, j) равно 0
3. Значение в позиции (k, l) равно 0

Поскольку (i, j, k, l) не заданы, выходные данные должны представлять собой массив приведенных выше оценок, по одному для каждого действительного значения (i, j, k, l)

Подход грубой силы ниже.Цель состоит в том, чтобы получить эффективный алгоритм, который работает для q <= 100 и для n <= 18. </p>

def tuples(n,q):
  return [[a,]+b for a in range(q) for b in tuples(n-1,q)] if n>1 else [[a] for a in range(q)]

def isvalid(t,n):
  grid=[t[n*i:n*(i+1)] for i in range(n)];
  for r in range(n):
    for c in range(n):
      v=grid[r][c]
      left=grid[r][c-1] if c>0 else -1
      right=grid[r][c-1] if c<n-1 else -1
      top=grid[r-1][c] if r > 0 else -1
      bottom=grid[r+1][c] if r < n-1 else -1
      if v==left or v==right or v==top or v==bottom:
        return False
  return True

def count(n,q):
  result=[]
  for pos1 in range(n**2):
    for pos2 in range(n**2):
      total=0
      for t in tuples(n**2,q):
        if t[pos1]==0 and t[pos2]==0 and isvalid(t,n):
          total+=1

      result.append(total)

  return result

assert count(2,2)==[1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1]

Обновление 11/11 Я также спрашивал об этом на TopCoder форумов , и их решение является наиболее эффективным из тех, что я когда-либо видел (около 3 часов для n = 10, любое q, по оценке автора)

Answer 1

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

Риск сводится к нулю, а риск - лишь небольшое время выполнения.

Answer 2

Это не ответ, а просто вклад в дискуссию, которая слишком длинна для комментария.

tl;др;Любой алгоритм, который сводится к «Вычислить возможности и сосчитать их», такой как подход Эрика Липперта или метод грубой силы, не будет работать для цели @ Ярослава q <= 100 и n <= 18.

Давайте сначалаПодумайте об одном n x 1 столбце.Сколько существует допустимых номеров этой колонки?Для первой ячейки мы можем выбрать между q числами.Поскольку мы не можем повторять по вертикали, мы можем выбрать между q - 1 числами для второй ячейки и, следовательно, q - 1 числами для третьей ячейки и так далее.Для q == 100 и n == 18 это означает, что существует q * (q - 1) ^ (n - 1) = 100 * 99 ^ 17 допустимых раскрасок, что очень приблизительно 10 ^ 36.

Теперь рассмотрим любые два допустимых столбца (назовите их столбцами хлеба), разделенных буферным столбцом (назовите это горчичной колонкой).Вот тривиальный алгоритм, чтобы найти правильный набор значений для столбца горчицы, когда q >= 4.Начните с верхней ячейки столбца горчицы.Нам остается только беспокоиться о соседних ячейках столбцов хлеба, которые имеют не более 2 уникальных значений.Выберите любой третий номер для столбца горчицы.Рассмотрим вторую клетку горчичного столбца.Мы должны рассмотреть предыдущую горчичную ячейку и 2 соседние хлебные ячейки с общим количеством не более 3 уникальных значений.Выберите 4-е значение.Продолжайте заполнять столбец горчицы.

У нас есть не более 2 столбцов, содержащих жестко запрограммированную ячейку 0. Таким образом, используя столбцы горчицы, мы можем сделать по крайней мере 6 хлебных столбцов, каждый с примерно 10 ^ 36 решениями дляв общей сложности не менее 10 ^ 216 действительных решений, дайте или возьмите порядок величин для ошибок округления.

Согласно Википедии, во Вселенной около 10 ^ 80 атомов.

Поэтому будь умнее.

Answer 3

Обновление 11/11. Я также спрашивал об этом на форумах TopCoder, и их решение является наиболее эффективным из тех, что я когда-либо видел (около 41 часа при n = 10, любое q, по оценке автора)

Я автор. Не 41, всего 3 смущающе распараллеливаемых процессорных часа. Я насчитал симметрий. Для n = 10 существует только 675 действительно различных пар (i, j) и (k, l). Моей программе нужно ~ 16 секунд на каждую.

Answer 4

Я не математик, но мне кажется, что должно быть аналитическое решение этой проблемы, а именно:

Во-первых, теперь можно вычислить много разных расцветок для платы NxN с Q цветами (в том числе те соседи, которые определены как имеющие общий край, не получают одинаковый цвет). Это должна быть довольно простая формула.

Затем выясните, сколько из этих решений имеет 0 в (i, j), это должно быть дробью 1 / Q.

Затем выясните, сколько из оставшихся решений имеют 0 в (k, l) в зависимости от манхэттенского расстояния | ik | + | jl | и, возможно, расстояния до края доски и «четности» этих расстояний, как в делении расстояния на 2, делится на 3, делится на Q.

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

Answer 5

Несколько замечаний, которые могут помочь и другим ответчикам:

1. Значения 1..q являются взаимозаменяемыми - это могут быть буквы и результат будет таким же.
2. Ограничения, которые не совпадают ни с одним соседом, очень мягкие, поэтому метод грубой силы будет чрезмерно дорогим. Даже если бы вы знали значения во всех ячейках, кроме одной, все равно было бы по крайней мере q-8 возможностей для q> 8.
3. Вывод этого будет довольно длинным - каждому набору i, j, k, l потребуется строка. Количество комбинаций примерно такое: n ² (n ² -3), поскольку два фиксированных нуля могут быть где угодно, кроме смежных, если только они не должны подчиняться первому правилу , Для n = 100 и q = 18, максимально сложный случай, это ~ 100 ⁴ = 100 миллионов. Так что это ваша минимальная сложность, и это неизбежно, поскольку проблема в настоящее время заявлена.
4. Существуют простые случаи - когда q = 2, существуют две возможные шахматные доски, поэтому для любой данной пары нулей ответ равен 1.

Точка 3 делает всю программу O (n ² (n ² -3)) как минимум, а также предполагает, что вам потребуется что-то достаточно эффективное для каждой пары нули, так как простое написание 100 миллионов строк без каких-либо вычислений займет некоторое время. Для справки, в секунду на строку, это 1x10 ⁸ с ~ 3 года или 3 месяца на 12-ядерном корпусе.

Я подозреваю, что для пары нулей есть элегантный ответ, но я не уверен, что есть аналитическое решение для него. Учитывая, что вы можете сделать это с 2 или 3 цветами в зависимости от положения нулей, вы можете разбить карту на серию областей, каждая из которых использует только 2 или 3 цвета, а затем это просто количество различных комбинаций 2 или 3 в q (qC2 или qC3) для каждого региона, умноженное на количество регионов, умноженное на количество способов разбиения карты.

Answer 6

Я создаю вклад, основанный на вкладе в дискуссию Дейва Аарона Смита.

Давайте пока не будем рассматривать последние два ограничения ((i,j) и (k,l)).

Только с одним столбцом (nx1) решение равно q * (q - 1) ^ (n - 1).

---

Сколько вариантов для второго столбца? (q-1) для верхней ячейки (1,2), но затем q-1 или q-2 для ячейки (2,2), если (1,2) / (2,1) имеют или не имеют одинаковый цвет.

То же самое для (3,2): q-1 или q-2 решений.

Мы можем видеть, что у нас есть двоичное дерево возможностей, и нам нужно суммировать по этому дереву. Давайте предположим, что левый потомок всегда «одного цвета сверху и слева», а правый потомок - «разных цветов».

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

Но давайте теперь рассмотрим распределение вероятностей для раскраски второго столбца: если мы хотим повторить процесс, нам нужно иметь равномерное распределение во втором столбце, это было бы так, как если бы первое никогда не существовало, и среди всех Окрашивая первые два столбца, мы можем сказать, что такие вещи, как 1/q, имеют цвет 0 в верхней ячейке второго столбца.

Без равномерного распределения это было бы невозможно.

Проблема: равномерно ли распределение?

Ответ: Мы бы получили такое же количество решений, построив сначала второй столбец, первый, а затем третий. Распределение второго столбца в этом случае является равномерным, поэтому оно также имеет место в первом случае.

Теперь мы можем применить ту же «идею дерева» для подсчета количества возможностей для третьего столбца.

Я попытаюсь развить это и построить общую формулу (поскольку дерево имеет размер 2 ^ n, мы не хотим его подробно исследовать).