传教士与野人过河问题状态图

### 传教士与野人过河问题的状态图表示方法

对于传教士与野人过河问题，状态可以用三元组 \((m, c, b)\) 来表示，其中 \(m\) 和 \(c\) 分别代表当前岸上的传教士数量和野人数量，\(b\) 是一个二进制标志位，用来指示船的位置（0 表示船在初始岸，1 表示船在对岸）。合法状态需满足两个条件：一是传教士的数量始终大于等于野人的数量；二是传教士和野人的数量均不超过总人数。

#### 状态转移规则
每次移动可以改变这个三元组中的值。具体来说：

- 船上最多两人；
- 只有当船上有人时才允许横渡河流；
- 移动后的新状态也必须是合法的。

因此，可能的操作包括但不限于单个或成对地运送传教士、野人或者两者一起跨越河流。

#### 构建状态图
构建状态图的过程涉及枚举所有可能的状态组合以及它们之间的转换路径。每一步都应验证新的状态是否有效并记录下来形成节点间的边连接关系。最终得到一张完整的无向图，在这张图里寻找一条从起始位置到达终点的有效路径即为解决问题的方法之一[^1]。

from collections import namedtuple

State = namedtuple('State', ['missionaries', 'cannibals', 'boat'])

def is_valid(state):
    """Check if the state is valid."""
    missionaries_left, cannibals_left, _ = state
    missionaries_right = 3 - missionaries_left
    cannibals_right = 3 - cannibals_left
    
    # Check both sides of river to ensure no group has more cannibals than missionaries.
    if (not 0 <= missionaries_left <= 3 or not 0 <= cannibals_left <= 3 or
        (missionaries_left and missionaries_left < cannibals_left) or 
        (missionaries_right and missionaries_right < cannibals_right)):
        return False
        
    return True


initial_state = State(missionaries=3, cannibals=3, boat='left')
goal_state = State(missionaries=0, cannibals=0, boat='right')

print(f"Initial State: {initial_state}")
print(f"Goal State: {goal_state}")

if is_valid(initial_state) and is_valid(goal_state):
    print("Both initial and goal states are valid.")
else:
    print("One or both states are invalid.")

此代码片段定义了一个简单的 `is_valid` 函数用于判断给定状态下是否存在任何一个岸边的野人数目超过了传教士数目的情况，并创建了初始状态和目标状态的对象实例以便后续处理[^2]。