Алгоритм, который может вычислить значения переменных на основе результата конкретных сумм тех

Question

Это может быть повторяющийся вопрос, но я не смог найти его при переполнении стека.

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

Например, возьмем переменные 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 оказываются одним целым, их можно пометить:

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

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

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

Answer 1

В общем, у вас есть 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 работает и является единственным решением. Практически все эти шаги должны быть вещами, которые вы можете автоматизировать.