Python AI 中的队列排序

Question

我正在尝试实施最佳优先算法作为建筑疏散项目的解决方案。

该建筑有 4 层，屋顶和 0 层。 我们在每次重复中使用 go_to_roof 等函数来移动电梯，直到达到目标。

目标是让电梯留在屋顶，并让所有居民撤离。

主要是这样的

def main():

initial_state = [0, 9, 4, 12, 7, 0]
goal = [5, 0, 0, 0, 0, 0]


""" ----------------------------------------------------------------------------
**** starting search
**** έναρξη αναζήτησης
"""

print('____BEGIN__SEARCHING____')
method = input("Enter the search method (BFS / DFS / BEFS): ").upper()
if method not in ['BFS', 'DFS', 'BEFS']:
    print("Error: Invalid method.")
    return

find_solution(make_front(initial_state), make_queue(initial_state), [], goal, method)

所以基本上，使用 BFS、DFS 和 Best First，我应该遍历每一种生成的所有情况。当我运行 BFS 时，我得到： 找到目标 [5,0,0,0,0,0] [[0, 9, 4, 12, 7, 0], [4, 9, 4, 12, 0, 7], [1, 8, 4, 12, 0, 8], [5, 8, 4, 12, 0, 0], [3, 8, 4, 4, 0, 8], [5, 8, 4, 4, 0, 0], [3, 8, 4, 0, 0, 4], [ 2, 8, 0, 0, 0, 8], [5, 8, 0, 0, 0, 0], [1, 0, 0, 0, 0, 8], [5, 0, 0, 0, 0, 0]]

对于“最佳第一”，我必须使用启发式标准。

首先使用 best 时，您应该将子级添加到路径的前面，即 insert(0, child)，然后根据启发式标准对它们进行排序。

作为标准，我选择了最少的状态总和[1:5] state[-1]是电梯时刻所在的楼层，state[1] - state[5]是每层楼和屋顶的居民人数。

例如，一个状态看起来像这样

def go_to_floor1(state):
    if state[-1]<8 and state[1]>0:
        if state[1]>8-state[-1]:
            new_state = [1] + [state[1] + state[-1] - 8] + [state[2]] + [state[3]] + [state[4]] + [8]
        else:
            new_state = [1] + [0] + [state[2]] + [state[3]] + [state[4]] + [state[1] + state[-1]]
        return new_state

因此，启发式标准是这样的：

def sum_state(state):
        return sum(state[1:5])

对于前面，我将在此处包含 BFS 和 DFS 的内容，以便您可以理解我的目的

def expand_front(front, method):  
    if method=='DFS':        
        if front:
            print("Front:")
            print(front)
            node=front.pop(0)
            for child in find_children(node):     
                front.insert(0,child)
                
    elif method=='BFS':
        if front:
            print("Front:")
            print(front)
            node=front.pop(0)
            for child in find_children(node):     
                front.append(child)

    elif method == 'BEFS':
        if front:
            print("Front:")
            print(front)
            node = front.pop(0)
            for child in find_children(node):
                front.insert(0,child)
                front.sort(key=sum_state) 
                
    return front

最后，对于队列，我不知道应该在哪里进行排序

def extend_queue(queue, method):
    if method == 'DFS':
        print("Queue:")
        print(queue)
        node = queue.pop(0)
        queue_copy = copy.deepcopy(queue)
        children = find_children(node[-1])
        for child in children:
            path = copy.deepcopy(node)
            path.append(child)
            queue_copy.insert(0, path)

    elif method == 'BFS':
        print("Queue:")
        print(queue)
        node = queue.pop(0)
        queue_copy = copy.deepcopy(queue)
        children = find_children(node[-1])
        for child in children:
            path = copy.deepcopy(node)
            path.append(child)
            queue_copy.append(path)

    elif method == 'BEFS':
        print("Queue:")
        print(queue)
        node = queue.pop(0)
        queue_copy = copy.deepcopy(queue)
        children = find_children(node[-1])
        for child in children:
            path = copy.deepcopy(node)
            path.append(child)
            queue_copy.append(path)
            queue_copy.sort(key=sum_state)
    
    return queue_copy

所以，我几乎可以肯定我在扩展前端的排序实现是正确的，但我不知道如何处理队列

Answer 1

不要像这样对队列进行排序，当你不应该时，你也可以在bestfs中的队列副本上附加（re papara ti kaneis mas kaneis olous Exposure）