1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
初始化open表和close表，path表
A_star(start) 传入初始状态
    将起点加入open_set中，并设置优先级为0（优先级最高）
    if open不为空，选open表中fn最小的节点cur_node:
        if cur_node的状态与目标状态一样：
            从终点开始逐步追踪parent节点，一直达到起点
            return path 返回找到的结果路径，算法结束
        if cur_node 不是目标状态：
            将节点cur_node从open表中删除，并加入close表中；
            for cur_node所有的邻近节点：
                if 邻近节点m在close表中：
                    continute 跳过，选取下一个邻近节点
                if 邻近节点m也不在open表中：
                    设置节点m的parent为节点cur_node
                    计算节点m的fn
                    将节点m加入open表中

1
 if not hash_value in close.keys() or close[hash_value] > new_gn:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
IDA_star(strat)
    bound = h(strat)
    while true
        t = search(strat, 0, bound)
        if t == FOUND then return FOUND
        if t == ∞ then return NOT_FOUND
        bound = t

search(cur_state, g, bound)
    f = g + h(cur_state)
    if f > bound then return f
    if node is goal then return FOUND
    min = ∞
    for child in expand(cur_state) do
        t = search(child, g + cost(cur_state, child), bound)
        if t == FOUND then return FOUND
        if t < min then min = t
    end for
    return min

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
def Manhattan(state):
    manhattan_dist = 0
    for i in range(4):
        for j in range(4):
            if state[i][j] == 0 or state[i][j] == final_state[i][j]:
                continue
            else:
                aim_x = (state[i][j] - 1) // 4  
                aim_y = (state[i][j] - 1) % 4
                manhattan_dist += (abs(aim_x - i) + abs(aim_y - j))
    return manhattan_dist*man_parameter  #1.125

def Misplaced(state):
    sum = 0
    for i in range(4):
        for j in range(4):
            if state[i][j] == 0:
                continue
            if state[i][j] != final_state[i][j]:
                sum += 1
    return sum

def LinearConflict(state):
    linear_conflict_count = 0
    # 计算每行和每列的冲突数
    for i in range(4):
        row_conflicts = 0
        col_conflicts = 0
        for j in range(4):
            if state[i][j] == 0:
                continue
            aim_x = (state[i][j] - 1) // 4  
            aim_y = (state[i][j] - 1) % 4
            if aim_x == i: #当前
                for k in range(j+1, 4):
                    if state[i][k] == 0:
                        continue
                    if aim_x == i and state[i][j] > state[i][k]:
                        row_conflicts += 1
            if aim_y == j:
                for k in range(i+1, 4):
                    if state[k][j] == 0:
                        continue
                    if aim_y==j and state[i][j] > state[k][j]:
                        col_conflicts += 1
        linear_conflict_count += row_conflicts + col_conflicts
    # 返回曼哈顿距离和冲突数的和
    return Manhattan(state) + 2 * linear_conflict_count

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
def A_star(start):
    root = Node(0, 0, start, None) # gn, hn, state, parent
    open.append(root)
    hash_value=hash(str(start))
    close.add(hash_value)
    node_num=0
    while len(open) != 0:
        cur_node = heapq.heappop(open)
        node_num += 1
        if cur_node.state == final_state:
            return add_path(cur_node),node_num
        for i in range(4):
            for j in range(4):
                if cur_node.state[i][j] != 0:
                    continue
                for d in range(4):
                    new_x = i + dir_x[d]
                    new_y = j + dir_y[d]
                    if 0 <= new_x <= 3 and 0 <= new_y <= 3:
                        state = copy.deepcopy(cur_node.state)
                        temp=state[i][j]
                        state[i][j] = state[new_x][new_y]
                        state[new_x][new_y] = temp
                        hash_value = hash(str(state))
                        if hash_value in close:
                            continue
                        close.add(hash_value)
                        hn=Manhattan(state)
                        # hn=Misplaced(state)
                        # hn=LinearConflict(state)
                        # hn=BFS(state)
                        # hn=InversionDistance(state)
                        new_node = Node(cur_node.gn+1, hn, state, cur_node)
                        heapq.heappush(open, new_node)
    return [],0

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
def A_star(start):
    root = Node(0, 0, start, None) # gn, hn, state, parent
    open.append(root)
    hash_value=hash(str(start))
    # close.add(hash_value)
    close[hash]=0 
    node_num=0
    while len(open) != 0:
        cur_node = heapq.heappop(open)
        node_num += 1
        if cur_node.state == final_state:
            return add_path(cur_node),node_num
        for i in range(4):
            for j in range(4):
                if cur_node.state[i][j] != 0:
                    continue
                for d in range(4):
                    new_x = i + dir_x[d]
                    new_y = j + dir_y[d]
                    if 0 <= new_x <= 3 and 0 <= new_y <= 3:
                        state = copy.deepcopy(cur_node.state)
                        state[i][j] = state[new_x][new_y]
                        state[new_x][new_y] = 0
                        hash_value = hash(str(state))
                        new_gn=cur_node.gn+1

                        if not hash_value in close.keys() or close[hash_value] > new_gn:
                            # close.add(hash_value)
                            close[hash_value] = new_gn
                            # hn=Manhattan(state)
                            # hn=Misplaced(state)
                            # hn=LinearConflict(state)
                            hn=h_fun(state)
                            # hn=InversionDistance(state)
                            new_node = Node(cur_node.gn+1, hn, state, cur_node)
                            heapq.heappush(open, new_node)
    return [],0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def IDA_star(start):
    # 估价函数用于计算当前状态和目标状态之间的距离
    # bound = Manhattan(start)
    # bound = Misplaced(start)
    bound = LinearConflict(start)
    path=[]
    path.append(start)
    while True:
        # t = search(path[-1], 0, bound, path) #与下面一个等价
        t = search(start, 0, bound, path) #要是回到这里，说明深度设定太浅，当前深度下没有找到解决方案，要增加深度限制（即增加bound），直到找到解决方案为止
        if t == -1:      #找到目标状态
            return path  # 返回路径
        if t == float("inf"):
            return None  # 没有解决方案
        bound = t #t是上一个迭代中找到的路径的最小成本，用它代表下一个迭代的新边界

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
def search(cur_state, g, bound, path): #DFS，每次记录最小深度
        f = g + Manhattan(cur_state)
        #递归结束条件
        if f > bound:
            return f
        if cur_state == final_state:
            return -1  # 找到目标状态
        min_bound = float("inf")
        for neighbor in get_neighbors(cur_state):
            if neighbor not in path:
                path.append(neighbor)#加入到路径中避免重复访问
                t = search(neighbor, g + 1, bound, path)
                if t == -1:
                    return -1
                if t < min_bound:
                    min_bound = t
                path.pop()#删掉本次走过节点,因为能到这说明t!=-1,即本次向下探索超过了bound还没有找到目标状态
        return min_bound

def get_neighbors(cur_state): #用于返回当前状态的所有相邻状态
    neighbors = []
    for i in range(4):
        for j in range(4):
            if cur_state[i][j] != 0:
                continue
            for d in range(4):
                new_x = i + dir_x[d]
                new_y = j + dir_y[d]
                if 0 <= new_x <= 3 and 0 <= new_y <= 3:
                    new_state = copy.deepcopy(cur_state)
                    temp=new_state[i][j]
                    new_state[i][j] = new_state[new_x][new_y]
                    new_state[new_x][new_y] = temp
                    neighbors.append(new_state)
            return neighbors