4.3 与或搜索树（and-or-search) --- 实现代码附详细注释（待完善）_and or search

书上好像使用的状态的映射写的， 这样在List上更加直观
但是感觉普适性较低，所以本人用多个参量记录状态
但是在输出表结构上出现了问题
主要的点是不太明白为什么在循环中遇到了一个出现过的节点便直接退出，那不会忽略它后继节点的状态嘛？
并且由于刚上手Python几日， 对List还是不太熟， 所以对输出有点困难，基本程序结构是正确的， 可以调试来进行阅读
与或搜索树只适用于连续空间离散化的一个时间片进行处理，从而得到一个解序列的算法
目的是通过该解序列，计算启发式函数，得出启发值，整体可以通过每个时间片得出的启发值，使用模拟退火进行求解
有大佬看到，求指正，感谢！

Python代码：

class State:
    def __init__(self, cleaner_state, left_dust, right_dust):
        self.cleaner_state = cleaner_state
        self.left_dust = left_dust
        self.right_dust = right_dust


class Problem:
    def __init__(self, init_state, goal_state):
        self.init_state = init_state
        self.goal_state = goal_state

    def action(self, state):
        if state.cleaner_state == "Left":
            return ["Suck", "Right", ]
        elif state.cleaner_state == "Right":
            return ["Left", "Suck", ]

    def result(self, state, action):
        if action == "Suck":
            if state.cleaner_state == "Left" and state.left_dust == 1:
                if state.right_dust == 1:
                    return [State("Left", 0, 0), State("Left", 0, 1), ]
                else:
                    return [State("Left", 0, 0), ]
            elif state.cleaner_state == "Left" and state.left_dust == 0:
                return [state, State("Left", 1, state.right_dust), ]
            elif state.cleaner_state == "Right" and state.right_dust == 1:
                if state.left_dust == 1:
                    return [State("Right", 0, 0), State("Right", 1, 0), ]
                else:
                    return [State("Right", 0, 0), ]
            elif state.cleaner_state == "Right" and state.right_dust == 0:
                return [state, State("Right", state.left_dust, 1), ]
        elif action == "Right":
            return [State("Right", state.left_dust, state.right_dust), ]
        elif action == "Left":
            return [State("Left", state.left_dust, state.right_dust), ]

        return []

    def goal_test(self, state):
        for s in self.goal_state:
            if s.cleaner_state == state.cleaner_state and s.left_dust == state.left_dust \
                    and s.right_dust == state.right_dust:
                return True
        return False


###########################################################
def or_search(state, problem, path):
    if problem.goal_test(state):
        return []
    for s in path:
        if s.cleaner_state == state.cleaner_state and s.left_dust == state.left_dust \
                and s.right_dust == state.right_dust:
            return None
    for action in problem.action(state):
        plan = and_search(problem.result(state, action), problem, path + [state, ])
        if plan is not None:
            return [action, plan]


def and_search(states, problem, path):
    plan = {}
    for s in states:
        '''
        初步想法是用0 1 2 4四位数的不同加和保存八种状态 来记录状态
        对Python List的了解还是不够透彻， 今后继续完善
        n = 0
        if s.cleaner_state == "Right":
            n += 1
        if s.left_dust == 1:
            n += 2
        if s.right_dust == 1:
            n += 4
        '''
        plan[s] = or_search(s, problem, path)
        # 不太懂这里为什么要退出
        if plan[s] is None:
            return None
    return plan


###########################################################

def and_or_graph_search(problem):
    return or_search(problem.init_state, problem, [])


def main():

    '''
    init_state = State(" ", -1, -1)
    '''

    init_state = State("Left", 1, 1)

    '''
    init_state.cleaner_state = input('Please input cleaner state (Right/Left): \n')
    init_state.left_dust = input('Please input whether have dust on the left (0/1): \n')
    init_state.right_dust = input('Please input whether have dust on the right (0/1): \n')
    n = int(input('Please input the number of goal state: \n'))
    '''

    goal_state = [State("Left", 0, 0), State("Right", 0, 0)]

    '''
    for i in range(n):
        state = State(" ", -1, -1)
        state.cleaner_state = input('Please input cleaner state (Right/Left): \n')
        state.left_dust = input('Please input whether have dust on the left (0/1): \n')
        state.right_dust = input('Please input whether have dust on the right (0/1): \n')
        goal_state = goal_state + [state, ]
    '''
    problem = Problem(init_state, goal_state)
    ans = and_or_graph_search(problem)
    print(ans)


if __name__ == '__main__':
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124