위키 피 디아 관련 기사 사이의 최단 경로 찾기

Question

위키피디아 기사 사이의 경로를 찾기 위해 파이썬 웹 크롤러를 작성하고 있습니다.

저는 시작 문서와 목표 문서가 있으며 그 사이에 짧은 경로를 찾으려고합니다.

지금 당장은 기본적으로 처음부터 목표와 같은 몇 가지 코드로 폭 넓은 검색을하고 있습니다.

for link in to_crawl: 
    links = get_all_links(source(link), crawled) 
    if goal in links: 
     return path+[link]+[goal] 
    crawled.append(link) 
    to_crawl.append(links) 

그들은 단지 몇도이 떨어져있는 경우가 다른 하나 개의 기사에서지고,하지만 난했다 경로를 추적 할 수있는 방법이 필요하다.

Answer 1

그냥 추적하십시오. 링크 목록이없는 대신 link, path 쌍의 목록이 있어야합니다. 이런 식으로 뭔가 :

to_crawl = [(start_page, [])] 
for link, path in to_crawl: 
    links = get_all_links(source(link), crawled) 
    if goal in links: 
     return path+[link]+[goal] 
    crawled.append(link) 
    to_crawl.extend((new_link, path + [new_link]) for new_link in links) 

또한 기존 코드에 심각한 문제를 가지고 있습니다 : 분명히 별도로 그 목록의 각 링크를 추가하고 싶었 때 단일 링크 인 것처럼 to_crawl.append(links) 링크의 목록을 추가를, . 나는 extend을 사용하여 그것을 고쳤습니다.

부수적으로, path+[link]+[goal]은 돌아 오는 것이 이상한 것입니다. 예를 들어 페이지 A에서 페이지 D로 경로 A-B-C-D를 통해 이동 한 경우 반환 값으로 B, C, D, C, D로 끝날 것입니다. 마지막 링크와 목표가 경로와 별도로 필요한 경우 패스에 포장하는 대신 return path, link, goal을 사용하지 않는 이유는 무엇입니까?