Блог

Возможно, это дублирующий вопрос, но я не смог найти его в stack overflow.

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

Например, возьмем переменные a , b , c x и y . Все их значения представляют собой неизвестное число от 0 до 1 (оба включительно). У меня есть следующие уравнения:

 1: a   b   c = 1
2: a   b   x = 2
3: b   c   y = 2
4: a   x <= 1    ->    0 <= a   x <= 1
5: c   y <= 1    ->    0 <= c   y <= 1
  

Решение этого дает следующий результат:

 2: a   x   b = 2
   (something between 0 and 1)   b = 2
   b = 2 - (something between 0 and 1)
   1 <= b <= 2
   b = 1 (since 0 <= b <= 1 applies too)

1: a   b   c = 1
   a   1   c = 1
   a   c = 0
   a = -c
   a = 0  (since 0 <= a <= 1 and 0 <= c <= 1 apply)
   c = 0

2: a   b   x = 2   |   3: b   c   y = 2
   0   1   x = 2   |      1   0   y = 2
   x = 1           |      y = 1

-> a = 0, b = 1, c = 0, x = 1 and y = 1
  

Я решил это на бумаге, моей реальной целью было доказать следующую ситуацию с сапером, присвоив каждой нераскрытой ячейке переменную соответственно x a b c y . Поскольку x , y и b оказываются единицами, они могут быть помечены:

Моя общая цель — решать платы minesweeper с использованием этой техники, но ее можно использовать в другом программном обеспечении. Однако, если я хочу, чтобы компьютер решил задачу о тральщике с использованием этой техники, пользователь должен использовать алгоритм для решения таких ситуаций с любым количеством переменных и любым количеством уравнений. Существует ли общий алгоритм, который делает это? И если есть, как я должен реализовать этот алгоритм?

Чтобы сделать вещи очевидными

• Уравнение — это одна переменная или сумма некоторых переменных, имеющая ограниченный или постоянный результат, который всегда положительный.
• Переменная — это неизвестное значение между нулем и единицей (оба значения включительно).
• Алгоритм учитывает количество переменных с соответствующими именами переменных и уравнения, которые определяют некоторые переменные.
• Алгоритм пытается вычислить как можно больше значений. Значения, которые не удалось определить, остаются неопределенными.

В общем случае у вас есть N-мерное векторное пространство, в котором N независимых переменных могут меняться. Каждое из ваших ограничений определяет область векторного пространства, и пересечение всех таких областей является областью, которую вы хотите определить. На самом деле, вы ищете самое простое (наименее сложное) описание этой области, поскольку область уже описывается набором ограничений. Существует три возможности: во-первых, в регионе нет решений; во-вторых, в регионе существует конечное число решений; в-третьих, в регионе существует бесконечно много решений.

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

 1: a   b   c = 1
2: a   b   x = 2
3: b   c   y = 2

1: a = 1 - b - c
2: 1 - b - c   b   x = 2
3: b   c   y = 2

1: a = 1 - b - c
2: c = x - 1
3: b   x - 1   y = 2

1: a = 1 - b - c
2: c = x - 1
3: b = 3 - x - y

1: a = y - 1
2: c = x - 1
3: b = 3 - x - y
  

Это все, на что мы способны. Далее мы подставляем в нашу полную систему неравенств:

 A: 0 <= a <= 1
B: 0 <= b <= 1
C: 0 <= c <= 1
D: 0 <= x <= 1
E: 0 <= y <= 1
F: 0 <= a   x <= 1
G: 0 <= c   y <= 1

A: 0 <= y - 1 <= 1
B: 0 <= 3 - x - y <= 1
C: 0 <= x - 1 <= 1
D: 0 <= x <= 1
E: 0 <= y <= 1
F: 0 <= y - 1   x <= 1
G: 0 <= x - 1   y <= 1

A: 1 <= y <= 2
B: 3 >= x   y >= 2
C: 1 <= x <= 2
D: 0 <= x <= 1
E: 0 <= y <= 1
F: 1 <= y   x <= 2
G: 1 <= x   y <= 2
  

На этом этапе вам нужно искать ограничения для каждой переменной по отдельности (если таковые имеются) и находить пересечение этих ограничений.

 A: 1 <= y <= 2 
                > taken together, the only solution is y = 1
E: 0 <= y <= 1 /  this is the intersection of intervals [0,1] and [1,2]

C: 1 <= x <= 2 
                > taken together, the only solution is x = 1
D: 0 <= x <= 1 /  this is the intersection of intervals [0,1] and [1,2]

B: 3 >= x   y >= 2   taken together, this means x   y = 2
F: 1 <= y   x <= 2  > this is the intersection of [1,2] and [2,3]
G: 1 <= x   y <= 2 /  note that G turns out to be redundant after subbing
  

Решение x = 1, y = 1 согласуется с нашей системой неравенств. Это единственное такое решение. Мы можем выполнить обратную замену в нашей системе уравнений, чтобы получить значения других переменных:

 1: a = y - 1
     = 1 - 1
     = 0
2: c = x - 1
     = 1 - 1
     = 0
3: b = 3 - x - y
     = 3 - 1 - 1
     = 1
  

Итак, решение a = 0, b = 1, c = 0, x = 1, y = 1 работает и является единственным решением. Практически все эти шаги должны быть тем, что вы можете автоматизировать.