例如, 在棋弈中的格局即为问题的状态。
用来描述一个问题的全部状态以及这些状态之间的相互关系。包含三个部分:
S—问题的初始状态集合
F—操作集合
G—目标状态的集合
用“状态”和“操作”来表示问题及其变化,形成状态空间,求解问题的过程就是在状态空间树中搜索表示解的状态的过程。
搜索时,从某个初始状态出发,每次使用一个操作使得问题能够从一种状态变为另外一种状态,直到到达目标状态为止。
假设有7个钱币,任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币,两位选手轮流进行,直到每一堆都只有一个或两个钱币,不能再分为止,哪个遇到不能分的情况,则就为输。
假设对方先走,我方是否有必胜策略?
还有哪些类似的问题可以使用状态空间来描述? 比如,井字棋、五子棋、拾火柴等游戏。画出井字棋问题的状态空间树。
过河问题如何使用状态空间法表示?
画出过河问题的状态空间图。
假定盘中放有n根火柴,由弈者A和B两人参加比赛。比赛的规则是:两名弈者轮流从盘中取走火柴,每次从盘中取走1,2或3根火柴均为合法着,否则为非法着。拿走盘中最后一根火柴的弈者为输。假定A方先走,A有必胜策略吗?若有就找出A的必胜策略。