python 광 도 우선 검색 두 점 사이 의 최 단 경 로 를 얻 을 수 있 습 니 다.

머리말
그동안 계속 쓰 지 못 했 는데 이번 주 일요일 에 오후 내 내 알 게 되 었 습 니 다.블 로그 에 넣 는 김 에 잊 어 버 리 고 다시 보 겠 습 니 다.
그림,출발점,종점,출력 기점 과 종점 사이 의 가장 짧 은 경 로 를 입력 하 는 것 이 실현 되 어야 합 니 다.
범위 우선 검색
적용 범위:가중치 가 없 는 그림 입 니 다.깊이 우선 검색 에 비해 깊이 우선 검색 법 은 메모리 가 적 지만 속도 가 느 립 니 다.범위 우선 검색 알고리즘 은 메모리 가 많 지만 속도 가 빠 릅 니 다.
복잡 도:시간 복잡 도 는 O(V+E)이 고 V 는 정점 이 며 E 는 변수 이다.
사고의 방향
범위 우선 검색 은 층 순 으로 한 층 의 모든 노드 를 검색 한 후에 야 다음 층 으로 검색 합 니 다.
예 를 들 어 다음 그림:

0 점 에서 검색 을 시작 하면 처음에는 0,0 을 대기 열 에 넣 습 니 다.
그리고 다음 층,0 에 도착 할 수 있 는 것 은 1,2,4 입 니 다.그들 을 대열 에 넣 습 니 다.
다음은 1,1 도착 할 수 있 고 방문 되 지 않 은 것 은 결점 3 입 니 다.
순 서 는 0,1,2,4,3 입 니 다.여 기 는 밑줄 로 각 층 에서 검색 할 수 있 는 결점 을 표시 합 니 다.
매번 cur=que[head]로 헤드 포인터 가 가리 키 는 결점 을 꺼 내 고 도착 할 수 있 는 결점 을 검색 합 니 다.따라서 방문 한 노드 를 하나의 대기 열 que 로 저장 할 수 있 습 니 다.대기 열 에는 헤드 포인터 head 와 꼬리 포인터 tail 이 있 습 니 다.출발점 start 와 결점 i 가 있 고 결점 i 가 방문 되 지 않 았 으 면 이 결점 을 대기 열 에 넣 고 tail 지침 을 뒤로 이동 합 니 다.tail 이 정점 수 와 같 을 때 알고리즘 이 끝 납 니 다.
매번 while 순환 에 대해 head 는 하 나 를 추가 합 니 다.즉,오른쪽으로 이동 합 니 다.예 를 들 어 처음에 head 위 치 는 0 이 었 고 다음 층 에 있 을 때 head 위치 요 소 는 1 이 었 습 니 다.즉,검색 과 노드 1 이 끝 이 있 고 방문 되 지 않 은 노드 입 니 다.
하나의 배열 북 으로 노드 i 가 방문 되 었 는 지 표시 합 니 다.시작 점 에서 각 점 까지 의 최 단 경 로 를 사전 으로 저장 합 니 다.
코드 는 다음 과 같 습 니 다:

import numpy as np

ini_matrix = [
     [0, 1, 1, 0, 1],
     [1, 0, 0, 1, 0],
     [1, 0, 0, 0, 1],
     [0, 1, 0, 0, 0],
     [1, 0, 1, 0, 0]
     ]


def bfs(matrix_para, start_point_para, end_point_para):
  """
        
  :param matrix_para  
  :param start_point_para   
  :param end_point_para   
  :return:      
  """
  matrix = matrix_para
  start_point = start_point_para
  end_point = end_point_para

  vertex_num = len(matrix) #     

  que = np.zeros(vertex_num, dtype=np.int) #   ，           
  book = np.zeros(vertex_num, dtype=np.int) #     i       ，1    ，0     

  point_step_dict = dict() # key: ，value:        

  #      
  head = 0
  tail = 0

  #      ，       
  que[tail] = start_point #         （  ）
  tail += 1
  book[start_point] = 1 # book[i] i    

  while head<tail:
    cur = que[head]
    for i in range(vertex_num):
      #      cur   i    ，     i        
      if matrix[cur][i] == 1 and book[i] == 0:
        que[tail] = i #    i     
        tail += 1 # tail     
        book[i] = 1 #     i      
        point_step_dict[i] = head + 1 #     
      if tail == vertex_num: #            
        break
    head += 1

  for i in range(tail):
    print(que[i])

  try:
    relevancy = point_step_dict[end_point]
    return relevancy
  except KeyError: #     ，        end_point，         ，  None
    return None

result = bfs(ini_matrix, 1, 4)
print("result:", result)

잘못
학생 들 의 조 교 를 받 은 후에 저 는 이 코드 에 문제 가 있다 는 것 을 깊이 깨 달 았 습 니 다.(head 로 걸음 길 이 를 기록 할 수 없습니다)바로 고리 가 있 을 때 얻 을 수 있 는 걸음 길이(교체 횟수)가 가장 짧 은 경로 보다 더 클 것 입 니 다.
예 를 들 어 출발점 은 4 이 고 종점 은 3 이다.여기 서 매번 교체 하 는 것 은 while 순환 이다.
첫 번 째 교체,대열 4,head 지향 4,보폭 0
두 번 째 교체,대열 4,0,2,head 지향 0,보폭 1
세 번 째 교체,대열 4,0,2,1,head 지향 2,보폭 2,
네 번 째 교체,2,2 주변 을 모두 방 문 했 지만 이때 head 는+1 이 3 이 므 로 다음 걸음 길이 가 실제 걸음 보다 1 이 많 을 것 이다.
다섯 번 째 교체,3,보폭 4
바로잡다
개 선 된 사고방식:count 로 보폭 을 기록 합 니 다.flag 는 현재 검색 이 도착 할 수 있 는 쪽 을 표시 하 는 데 사 용 됩 니 다.이 결점 cur=que[head]주위 가 이미 방 문 했 는 지,False 는 없 는 지,True 는 이 결점 i 주위 가 모두 방 문 했 는 지 표시 합 니 다.즉,flag 가 False 일 때 cur 주변 에 이미 방문 했다 는 뜻 입 니 다.이때 보폭 count 는 1 을 증가 할 필요 가 없습니다.

import numpy as np

ini_matrix = [
     [0, 1, 1, 0, 1],
     [1, 0, 0, 1, 0],
     [1, 0, 0, 0, 1],
     [0, 1, 0, 0, 0],
     [1, 0, 1, 0, 0]
     ]


def bfs(matrix_para, start_point_para, end_point_para):
  """
        
  :param matrix_para  
  :param start_point_para   
  :param end_point_para   
  :return:      
  """
  matrix = matrix_para
  start_point = start_point_para
  end_point = end_point_para

  vertex_num = len(matrix) #     

  que = np.zeros(vertex_num, dtype=np.int) #   ，           
  book = np.zeros(vertex_num, dtype=np.int) #     i       ，1    ，0     

  point_step_dict = dict() # key: ，value:        

  #      
  head = 0
  tail = 0

  #     
  count = 0

  #  0     ， 0       
  que[tail] = start_point #         （  ）
  tail += 1
  book[start_point] = 1 # book[i] i    

  while head<tail:
    flag = False #  flag    i           
    cur = que[head]
    for i in range(vertex_num):
      #      cur   i    ，     i        
      if matrix[cur][i] == 1 and book[i] == 0:
        que[tail] = i #    i     
        tail += 1 # tail     
        book[i] = 1 #     i      
        point_step_dict[i] = count + 1 #     
        flag = True
      if tail == vertex_num: #            
        break
    if flag:
      count += 1
    head += 1

  for i in range(tail):
    print(que[i])

  try:
    relevancy = point_step_dict[end_point]
    return relevancy
  except KeyError:
    return None

result = bfs(ini_matrix, 3, 4)
print("result:", result)

뒤에 쓰다
정말 죄송합니다.이런 알고리즘 블 로 그 를 처음 써 봤 는데 이렇게 큰 문제 가 생 겼 습 니 다.예전 에 BUG 를 기록 한 글 이 었 습 니 다.다행히 학생 들 이 저 에 게 신속하게 말 했 습 니 다.주요 원인 은 제 가 그렇게 많은 테스트 를 하지 않 았 기 때 문 입 니 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.