状態空間表現と最適の期待値

最近トップコーダーの問題を解きながらベイズネットの木をメモリーに作成しました。この図に確率変数の値がノードになります。
The objective of this problem was to find the optimal strategy for selling an item to one of two customers, given the possible arrival times, probability of arrival, and price for the customers. This can be computed by building a model of the state space of arrivals and sales, which is a binary tree. In addition, this is a Bayes Net, because the probability of a child node is the joint probability of the parent node and child node. e.g. P(sell to C1 at time 6) = P(C1 arrives at 6, sell to C1 at 6) where the "C1 arrives at 6" node is the parent of the sale node. It is practical to construct such a tree, because each customer can have at most 10 possible arrival times, and each will arrive at only one time. Thus, there are at most 11^2 = 121 possible arrival pairs, as each may not arrive at all. Considerint the sale node which can be added onto each arrival (and which has no children), there are O(121+110+10) nodes, as there are 11*10 sales for the second customer and 10 sales for the first, if we consider all possible sale scenarios. It is assumed that the tree contains no meaningless nodes.
The key insight is Bayes' Rule: P(reaching parent and child)=P(reaching parent)*P(reach child|reach parent).
If we compare P(reach parent,reach child1) and P(reach parent, reach child2) for the same parent, we are implicitly comparing child probabilities. If we compare expectation EV(parent,child1) and EV(parent,child2) we are implicitly comparing EV(child1|parent) and EV(child2|parent), as
EV(child1|parent) = EV(child1,parent)/P(parent)
EV(child2|parent) = EV(child2,parent)/P(parent)
This problem also falls into the genres of scheduling and dynamic programming.