파이썬에서 광범위한 첫 번째 검색 구현

Question

파이썬에서 BFS를 구현하려고하는데 알고리즘 작동 방식을 이해하지만 프로그래밍 경험이별로 없습니다. 모든 것을 표현할 수있는 최선의 방법과 가능한 한 효율적으로 일하는 방법을 생각하면서 몇 시간을 보냈습니다. 나는 시작 노드에서 목표 노드로가는 길을 알아낼 수 없었다.

나는 인터넷 검색을하면서 다른 사람들의 알고리즘 구현을 보았지만 약간의 차이가 있었고 이로 인해 혼란 스럽다. 사람들이 BFS를 구현할 때 (BFS에 대한 위키피디아 기사와 마찬가지로) 그래프가 주어 졌다고 가정합니다. 내 문제는 초기 상태와 내가 도달하고자하는 목표 상태이지만 그래프 나 트리가 없으므로 내가가는대로 노드를 생성합니다. 예를 들어

가 : 뭔가에 문제가 있기 때문에

def BFS(initial, goal): 

    q = [initial] 
    visited = [] 

    while q: 
     n = q.pop() 
     states = generate_states(n) 

     for state in states: 
      if state == goal: 
       pass #placeholder 
      q.append(state) 
      visited.append(state) 

제대로 구체화 아니에요, 나는 그것이 구체적으로 무엇인지 확실하지 않다 중 ... 초기 및 목표 노드가 있고, 나는 경우 구조체 형식 클래스를 내 코드의 다른 곳에 작성하십시오.

class node: 
    state = None 
    parent = None 

이 방법은 노드를 나타내는 데 적합합니다. 따라서 노드 객체를 대기열에서 팝하면 generate_states 함수에 의해 초기화 될 정보가 있습니다. 그런 다음 for 루프는 이러한 새로운 노드를 대기열에 추가하고 방문한 대기열에 생성 된 노드 중 하나에서 반복됩니다. 그러면 목표 상태와 일치하는 상태가됩니다.

목표 노드를 찾았으므로 방문한 노드 목록이 있습니다. 그러나 경로를 목표 노드에서 거꾸로 추적하면 알고리즘 속도가 느려지지 않습니까? 일단 목표가 발견되면 나는 그 부모를 보았고, 방문 목록에서 그 부모를 찾은 다음, 부모 = 부모의 부모를 보았다. 내가 경로 = [노드 객체, 노드 객체, ...]를 가질 때까지 ]를 초기 노드에서 목표 노드로 이동시킨다.

이것은 노드 객체를 만들 때 while 루프의 한 번의 반복에만 지속되는 또 다른 문제를 안겨줍니다. 배열에 객체를 저장하는 방법은 각각 고유 한 이름이 필요하며이를 수행하는 분명한 방법이 없습니다. 이것은 이전에 내가 확실히 알지 못했던 문제였습니다. 그래서 노드를 만들었지 만 큐에 node.state를 저장하는 것 같습니다. node.parent에 액세스하기 위해 노드 객체가 필요하기 때문에 무의미합니다 ...

왜 이렇게 어려운지, 명백한 무언가를 놓치고 있거나 이것을 너무 복잡하게 만들고 있습니까?

읽어 주셔서 감사합니다.

Answer 1

내가하는 일을 완전히 이해하지 못하기 때문에이 부분에 대해서는 언급 할 수 없습니다. 일반적으로 BFS는 이미 그래프를 가지고있을 것이므로 어떻게해야할지 모르겠습니다. 당신은 당신이가는 동안 그것을 건설 할 것을 제안하고 있습니다. 하지만이 비트에 회신해야 내가 배열에 객체를 저장하기위한 것입니다 방법

, 그들은 각각 고유 한 이름을

가 필요합니다 확실히 거짓입니다. 목록에 저장하려는 경우 이름을 지정하지 않아도됩니다. 추가 만하면됩니다. 나중에 찾을 수 있을지 걱정된다면 그래프와 관련된 일반적인 작업은 정의 할 때마다 증가하는 단일 카운터를 통해 각 노드에 숫자를 제공하는 것입니다. 다시 말하지만, 노드를 목록에 저장하는 경우에는 목록에서 노드의 고유 한 번호를 자동으로 가져옵니다.

Answer 2

당신의 접근 방식이 나에게 잘 들립니다.

검색 경로를 얻으려면 각 노드의 부모를 추적 할 수 있습니다 (예 : 그것을 발견 한 노드에 설정된 속성을 부여하십시오. 그렇게하면 검색 경로를 추적하는 연결 목록이 생깁니다. 당신이 목표에 도달하면 다시 걷기 위해 당신은 당신이 목록뿐만 아니라 미국에서 발견 노드를 넣어 생성 된 노드의 트랙 (변수 N)를 유지하기위한

def get_parents(node): 
    if node.parent is None: 
     return [] 

    yield node.parent 
    get_parents(node) 

을 할 수 있습니다.

n = q.pop() 
    states = generate_states(n) 

    for state in states: 
     m = node() 
     m.state = state 
     m.parent = n 
     if state == goal: 
      pass #placeholder 
     q.append(m) 
     visited.append(m) 

Answer 3

일반적으로 갖고있는 것이 좋습니다.

그러나 내가 설명하려고하는 몇 가지 혼란이 있습니다. 먼저 상태가 아닌 대기열에 노드를 저장합니다. 노드에는 부모가 있으므로 이전 노드로 이동할 수 있으므로 잃어 버리지는 않습니다. 둘째, 부모를 통해 추적하는 것이 효율성에 대해 걱정할 필요가있는 것이 아닙니다. 성공할 때만 수행 할 수 있습니다 (이름이 필요 없지만지도를 혼란스럽게 만드는 것처럼 들릴 수도 있습니다).

코드에서 누락 된 유일한 사실은 실제로 노드를 만들지 않는다는 것입니다. 상태가되면 노드를 만들고 상태가 아닌 노드를 저장합니다. 그러면 모든 것이 잘될 것입니다.