폭 먼저 무한 루프로 검색

내가 만드는 8 개의 퍼즐 AI 게임에서 bfs 그리고 그것은 항상에서 끝나는 무한 루프로, 내가 사용하는 큐를 저장하는 탐험(아직 많이 방문한 노드)목록을 저장하는 탐구와 많이 방문한 노드를 방문하지 않는 동일한 상태로 여러 번,또한 사용 getNextStates()함수는 모든 가능한 다국의 위치에 따라"0"스위치()는 책임을 만들기 위한 다음 상태,내 코드:

goalState=[0, 1, 2, 3, 4, 5, 6, 7, 8]
def switch(list,index1,index2):
    newList=[]
    for i in range(len(list)):
        newList.append(list[i])

    temp=newList[index1]
    newList[index1]=newList[index2]
    newList[index2]=temp
    return newList

def getNextStates(state):
    nextStates=[]
    length=len(state)
    emptyTile=0
    for i in range(length):
        if state[i]==0:
            emptyTile=i
            #    1
            # 0  3
    print('empty tile in position : ' , emptyTile)
    if emptyTile==0:
        nextStates.append(switch(state,0,1))
        nextStates.append(switch(state, 0, 3))
    elif emptyTile==1:
        nextStates.append(switch(state, 1, 0))
        nextStates.append(switch(state, 1, 4))
        nextStates.append(switch(state, 1, 2))
    elif emptyTile==2:
        nextStates.append(switch(state, 2, 1))
        nextStates.append(switch(state, 2, 5))
    elif emptyTile==3:
        nextStates.append(switch(state, 3, 0))
        nextStates.append(switch(state, 3, 4))
        nextStates.append(switch(state, 3, 6))
    elif emptyTile==4:
        nextStates.append(switch(state, 4, 3))
        nextStates.append(switch(state, 4, 1))
        nextStates.append(switch(state, 4, 5))
        nextStates.append(switch(state, 4, 7))
    elif emptyTile==5:
        nextStates.append(switch(state, 5, 2))
        nextStates.append(switch(state, 5, 4))
        nextStates.append(switch(state, 5, 8))
    elif emptyTile==6:
        nextStates.append(switch(state, 6, 3))
        nextStates.append(switch(state, 6, 7))
    elif emptyTile==7:
        nextStates.append(switch(state, 7, 6))
        nextStates.append(switch(state, 7, 4))
        nextStates.append(switch(state, 7, 8))
    else:
        nextStates.append(switch(state, 8, 7))
        nextStates.append(switch(state, 8, 5))

    return nextStates


def breadthFirst(initialState,goal):
    global exploredCount , visitedCount
    exploredCount = 1
    visitedCount = 0
    frontier = []
    frontier.append(initialState)
    explored=[]
    print("Staring Dequing....")
    while len(frontier) > 0:
        print(len(frontier))
        state=frontier.pop(0)
        print("dequed : " , state)
        explored.append(state)
        print("appended in explored and visitedCount incremented")
        visitedCount += 1
        if state==goal:
            print("State Is Accomplished")
            return state
        nextStates=getNextStates(state)
        print("possible Next States : " , nextStates)
        for i in range(len(nextStates)):
            print('Checking Child states , current : ' , nextStates[i])
            if  not nextStates[i] in explored:
                if not nextStates[i] in frontier:
                    print("not in visited or explored , enqueue")
                    frontier.append(nextStates[i])
                    exploredCount += 1
 
    return initialState