鉴于您知道发生了某些变化，如何推断未知变量的状态？

Question

存在一个游戏，其状态由 n 个布尔变量 p_1、p_2、...、p_n 量化。假设 0 <= n <= 10。游戏的目的是跟踪尽可能多的变量的状态，以及它们何时会改变状态（见下文）。

一次只能观察到一部分变量。当变量的状态从 true 变为 false 时，我们总是会收到通知，但只有当观察到相关变量时，我们才会获知哪个变量发生了变化。

如果某些 p_i 在时间 t 将状态从 true 更改为 false，则它会将状态从 false 更改回 [=15] =] 时间 t + 60.

以下是一些示例情况和所需的行为。假设有三个变量，p_1、p_2、p_3.

所有变量都是可观察的。一个变量改变状态，通过观察它是 p_1。我们知道 p_1 将在 t + 60.
p_1 和 p_2 是可观察的。变量改变状态。应该可以推断是p_3。我们知道 p_3 将在 t + 60.
p_1 是可观察的，并且已知 p_2 在时间 t - 30 将状态更改为 false。变量改变状态。根据观察，它不是 p_1，p_2 只会在 t + 30 将状态更改为 true，因此它是 p_3。
没有可观察到的变量已知 p_1 在时间 t - 30 将状态更改为 false，p_2 在 [=] 将状态更改为 false 49=]，并且 p_3 在 t - 80 处将状态更改为 false。变量改变状态。在 t + 1 处观察到 p_2 的值为 true。因为p_1仍然是false，而p_2已经被观察到true，所以应该推断p_3是false，并且会在 t + 60.

true

p_1 和 p_2 是可观察的。已知 p_3 在时间 t - 70 将状态更改为 false。没有变量改变状态。应该推断 p_3 为真，因为它会在 t - 10 处从 false 变为 true，如果它从 true 变为 false，我们会被告知变量正在改变状态。

我尝试过的一种方法涉及在每次通知变量状态更改时迭代每个变量，并根据以下条件排除可能的匹配：

是否可见且未改变状态
它的最后一次状态变化是否已知并且在过去还不够远以至于它已经变回。

然后，对于状态已知的剩余变量，根据变量在特定状态下最后一次观察到的时间，变量可能已经改变状态的时间，确定它们最后一次变量变化的上限和下限（返回, from false to true), etc. 那么如果那个范围内只有一个变量变化事件，那么应该就是这个变量对应的事件。结果太麻烦了，没继续。每一行都是一个负担，因为状态的可能组合似乎太多了，我不会考虑任何事情。

考虑到问题陈述，上述方法是否合理？是否有一种通用的方法可以对此类问题进行建模，以便更优雅地解决它们？

Answer 1

根据@NicoSchertler 的建议，我想出了一个解决方案，它通过基于 Observations 和 Hypotheses 的序列创建状态集来处理不确定性。观察是特定（观察到的）变量的已知状态，而假设是状态的通知，但没有关于它适用于哪个变量的信息。我们能够假设假设不能应用于正在观察的变量。此解决方案不处理开始状态未知（尚）的情况。

有一个单一的起始状态对应于每个变量都是true的情况。当提供 hypothesis 时，可能会生成多个 (n) 后继状态，方法是假设每个未观察到的变量都是 hypothesis 的主题。导致矛盾的后继状态被丢弃。当提供 observation 时，将为每个当前状态生成一个后继状态。任何导致矛盾的状态都会被丢弃。以这种方式，假设和观察的序列导致变量可能处于的一组可能状态。

为了我的特定目的，我想知道基于这些状态可以知道什么（而不是例如是否存在有效的解决方案）。合并状态并返回一个结果，如果该变量在所有状态中具有相同的状态，则给出每个变量的状态。

给定 n 个状态和 m 个通知，最坏情况下的复杂度是 n^m，这可能非常有限，但对于我有限的应用程序来说应该没问题。

这里是JavaScript实现和测试代码。

solver.js

// Time for state to change back.
var STATE_CHANGE = 6e4;
// Possible notification lag.
var EPSILON = 2e3;

// Comparison operations.
function lt(a, b) {
  return a - b < EPSILON;
}

function gt(a, b) {
  return b - a < EPSILON;
}

function eq(a, b) {
  return Math.abs(a - b) < EPSILON;
}

// Object clone.
function clone(obj) {
  return JSON.parse(JSON.stringify(obj));
}

module.exports = Solver;

/**
 * Solver solves boolean dynamic state.
 * @param {Array<string>} variables - array of variable names.
 */
function Solver(variables) {
  this.variables = {};
  this.states = [];
  this._time = null;
  var state = {};
  var time = Date.now();
  var self = this;
  // TODO: Handle unknown or variable start.
  variables.forEach(function (variable) {
    self.variables[variable] = {
      observed: false
    };
    state[variable] = {
      state: true,
      intervals: [{
        state: true,
        start: time,
        observed: false,
        end: null
      }]
    };
  });
  this.states.push(state);
}

// Set subset of variables as observed, the rest assumed not.
Solver.prototype.setObserved = function(variables) {
  var unobserved_variables = Object.keys(this.variables).filter(function (variable) {
    return variables.indexOf(variable) === -1;
  });
  var self = this;
  variables.forEach(function (variable) {
    self.variables[variable].observed = true;
  });
  unobserved_variables.forEach(function (variable) {
    self.variables[variable].observed = false;
  });
};

// Hypothesis has time, state.
Solver.prototype.addHypothesis = function(h) {
  this.updateVariables();
  var states = [];
  for (var i = 0; i < this.states.length; i++) {
    var newStates = this.applyHypothesis(this.states[i], h);
    if (newStates)
      Array.prototype.push.apply(states, newStates);
  }
  this.states = states;
};

// Observation has time, state, variable.
Solver.prototype.addObservation = function(o) {
  this.updateVariables();
  var states = [];
  for (var i = 0; i < this.states.length; i++) {
    var newState = this.applyObservation(this.states[i], o);
    if (newState)
      states.push(newState);
  }
  this.states = states;
};

// Get set of possible states.
Solver.prototype.getStates = function() {
  this.updateVariables();
  return this.states.slice();
};

// Get consolidated state.
// Each variable has state (true|false|null), change (if false). change
// is number or array (if there is disagreement)
Solver.prototype.getState = function() {
  this.updateVariables();
  // Construct output.
  var out = {};
  var state = this.states[0];
  for (var name in state) {
    var variable = state[name];
    if (variable.state) {
      out[name] = {
        state: variable.state
      };
    } else {
      var time = variable.intervals[variable.intervals.length - 1].end;
      out[name] = {
        state: variable.state,
        time: time
      };
    }
  }
  // Compare results across all states.
  return this.states.slice(1).reduce(function (out, state) {
    for (var name in out) {
      var out_variable = out[name],
          variable = state[name];
      // Check for matching states.
      if (out_variable.state === variable.state) {
        // Falsy check time.
        if (!out_variable.state) {
          // TODO: check undefined in case interval not updated?
          var change = variable.intervals[variable.intervals.length - 1].end;
          if (out_variable.time instanceof Array) {
            if (out_variable.time.indexOf(change) === -1) {
              out_variable.push(change);
            }
          } else if (out_variable.time !== change) {
            var times = [out_variable.time, change];
            out_variable.time = times;
          } // Else matches, so no problem.
        }
      } else {
        // Conflicted states.
        out_variable.state = null;
        // In case it was set.
        delete out_variable.time;
      }
    }
    return out;
  }, out);
};

// Update `false` state variables based on false end
// time, if present.
Solver.prototype.updateVariables = function() {
  var time = this._time || Date.now();
  for (var i = 0; i < this.states.length; i++) {
    var state = this.states[i];
    for (var name in state) {
      var variable = state[name];
      // Update changeback.
      if (!variable.state) {
        if (variable.intervals.length > 0) {
          var last = variable.intervals[variable.intervals.length - 1];
          if (last.end && last.end <= time) {
            // update to true.
            variable.state = true;
            variable.intervals.push({
              state: true,
              start: time,
              end: null
            });
          }
        }
      }
    }
  }
};

// Return state with observation applied or null if invalid.
Solver.prototype.applyObservation = function(state, observation) {
  var variable = state[observation.variable];
  if (variable.state && !observation.state) {
    // Change in observed variable true -> false
    variable.state = observation.state;
    variable.intervals.push({
      state: variable.state,
      start: observation.time,
      end: observation.time + STATE_CHANGE
    });
    return state;
  } else if (variable.state && observation.state) {
    // Expected state.
    return state;
  } else if (!variable.state && observation.state) {
    // Potentially updating variable.
    var time = variable.intervals[variable.intervals.length - 1];
    if (eq(time, observation.time)) {
      // update state.
      variable.state = observation.state;
      variable.intervals.push({
        state: observation.state,
        start: observation.time,
        end: null
      });
      return state;
    } else {
      // Could not update this variable.
      return null;
    }
  } else if (!variable.state && !observation.state) {
    // Expected state.
    return state;
  }
};

// Returns multiple states or null if invalid
Solver.prototype.applyHypothesis = function(state, hypothesis) {
  hypothesis = clone(hypothesis);
  var states = [];
  for (var name in state) {
    // Skip observed variables, no guessing with them.
    if (this.variables[name].observed)
      continue;
    var newState = clone(state);
    var variable = newState[name];
    // Hypothesis is always false.
    if (variable.state) {
      // Change in observed variable true -> false
      variable.state = hypothesis.state;
      variable.intervals.push({
        state: variable.state,
        start: hypothesis.time,
        end: hypothesis.time + STATE_CHANGE
      });
    } else {
      newState = null;
    }
    if (newState !== null) {
      states.push(newState);
    }
  }
  if (states.length === 0) {
    return null;
  } else {
    return states;
  }
};

测试-solver.js

var Solver = require('./solver');

var p_1 = "p_1",
    p_2 = "p_2",
    p_3 = "p_3";
var solver = new Solver([p_1, p_2, p_3]);

var t = Date.now();

solver.setObserved([p_1, p_2, p_3]);
solver._time = t + 5e3;
solver.addObservation({
  variable: p_1,
  state: false,
  time: t + 5e3
});

var result = solver.getState();
if (!result[p_1].state && result[p_1].time === t + 65e3 &&
    result[p_2].state &&
    result[p_3].state) {
  console.log("PASS: Test 1.");
} else {
  console.log("FAIL: Test 1.");
}

solver = new Solver([p_1, p_2, p_3]);
solver.setObserved([p_1, p_2]);
solver._time = t + 5e3;
solver.addHypothesis({
  state: false,
  time: t + 5e3
});

result = solver.getState();
if (result[p_1].state &&
    result[p_2].state &&
    !result[p_3].state && result[p_3].time === t + 65e3) {
  console.log("PASS: Test 2.");
} else {
  console.log("FAIL: Test 2.");
}

solver = new Solver([p_1, p_2, p_3]);
solver.setObserved([p_1]);
solver._time = t - 30e3;
solver.addObservation({
  variable: p_2,
  time: t - 30e3,
  state: false
});
solver._time = t;
solver.addHypothesis({
  state: false,
  time: t
});

var result = solver.getState();
if (result[p_1].state &&
    !result[p_2].state && result[p_2].time === t + 30e3 &&
    !result[p_3].state && result[p_3].time === t + 60e3) {
  console.log("PASS: Test 3.");
} else {
  console.log("FAIL: Test 3.");
}

solver = new Solver([p_1, p_2, p_3]);
solver._time = t - 80e3;
solver.addObservation({
  variable: p_3,
  time: t - 80e3,
  state: false
});
solver._time = t - 75e3;
solver.addObservation({
  variable: p_2,
  time: t - 75e3,
  state: false
});
solver._time = t - 30e3;
solver.addObservation({
  variable: p_1,
  time: t - 30e3,
  state: false
});
solver._time = t;
solver.addHypothesis({
  state: false,
  time: t
});
result = solver.getState();
if (!result[p_1].state && result[p_1].time === t + 30e3 &&
    result[p_2].state === null &&
    result[p_3].state === null) {
  console.log("PASS: Test 4.");
} else {
  console.log("FAIL: Test 4.");
}
solver._time = t + 1;
solver.addObservation({
  variable: p_2,
  time: t + 1,
  state: true
});
var result = solver.getState();
if (!result[p_1].state && result[p_1].time === t + 30e3 &&
    result[p_2].state &&
    !result[p_3].state && result[p_3].time === t + 60e3) {
  console.log("PASS: Test 5.");
} else {
  console.log("FAIL: Test 5.");
}

鉴于您知道发生了某些变化，如何推断未知变量的状态？

How to infer state of unknown variables given that you know something changed?

language-agnostic

algorithm

logic

inference