프롤로그의 퍼스트 - 퍼스트

Question

프롤로그에서 기본 깊이 우선 검색 구성보다 너비 우선을 사용하는 일반적인 개념은 무엇입니까?

무한 가지를 복용하지 않습니까?

Prolog에서 너비 우선을 사용하는 일반적인 방법이 있습니까? 나는 인터넷 검색을하고 있었고 초보자에게 유용한 정보를 찾지 못했습니다.

Answer 1

너비의 장점은 모든 솔루션을 찾을 수 있다는 것입니다. 깊이 우선 - 당신은 무한한 지점에 갇힐 수 있습니다.

단점은 너비 우선 메모리가 많은 메모리를 사용하므로 일반적으로 실행에 사용되지 않는다는 것입니다.

사용하려면 특정 종류의 큐를 사용하여 명시 적으로 구현해야합니다.

편집 : 당신은 당신이 반복 심화를 사용할 수 많은 메모리를 사용하지 않고 폭 우선 검색의 장점을 갖고 싶어. 깊이 - 경계가있는 깊이 우선 검색으로, 연속적으로 증가시킵니다. 이로 인해 중복 계산이 발생하지만 검색 공간에 분기가없는 긴 선형 확장이없는 경우이 복제는 작습니다.

Answer 2

"의제 검색"으로 알고있는 것이 있습니다. 나무 (데이터, 관계, 규칙, ...)를 탐색하는 동안 다음에 수행 할 작업의 "일정"(목록)을 유지 관리합니다. 노드에 들어가면 자녀를 의제에 올려 놓은 다음 의제의 첫 번째 요소로 계속 진행합니다. 이런 식으로, 당신이 의제 끝에 새로운 항목을 넣으면, 당신은 폭 넓은 것을 얻습니다. 당신이 그것들을 의제 앞에 놓는다면, 당신은 먼저 깊이가납니다.

Prolog로 구현하기 쉽습니다.

편집 : 여기에 구현 힌트를 제공 할 수도 있습니다. 이것은 의제 검색 알고리즘의 매우 기본적인 구현입니다.

그것은 당신이 각 노드에 수행 할 작업을 의미합니다 외부 조건 doWithNode에 의존

agenda_search([N|T],Mode):- 
    doWithNode(N),   % do whatever you do the searching for 
    getNodeChildren(N,C), 
    (Mode=bf ->    % bf or df (depth-first) 
     append(T,C,A); 
     append(C,T,A)), 
    agenda_search(A,Mode). 

(예컨대, ASF를 검색어로 노드 데이터를 비교 노드의 컨텐츠를 직렬화.). 그리고 주어진 노드의 자식들의리스트를 C으로 바인딩 할 getNodeChildren (즉,이 술어는 실제로 트리 구조와 자식 노드를 찾는 방법을 알고 있습니다). 물론 doWithNode 술어는 작업을 수행하기 위해 추가 매개 변수가 필요할 수도 있으며, 이는 인수 목록 agenda_search에도 표시됩니다.

이처럼 호출 할 수

agenda_search([RootNode], bf) % for breadth-first search 

및

agenda_search([RootNode], df) % for depth-first search 

는 또한 의제 검색 on this web page의 약간의 설명을 발견했습니다. 의제 검색의 좋은 점은 df와 bf의 두 변형을 쉽게 전환 할 수 있고 결과와 함께 플레이 할 수 있다는 것입니다. 이 알고리즘은 여전히 ​​잘 동작하며, 탐색 할 노드 인 아젠다는 언제든지 트리에서 노드의 작은 부분 만 캡처합니다 (소위 프린지 (fringe)).

Answer 3

agenda_search 코드가 정상적으로 작동해야합니다. 효율성을 위해 다른 데이터 구조를 사용하는 것이 좋습니다. 참으로, 폭 우선 모드에서 노드 (T)의 전체 목록은 추가 (T, C, A)에 의해 트래버스됩니다. 예를 들어 SICStus의 라이브러리 (대기열) 모듈을 사용할 수 있습니다. 우선 검색은 다음과 같이 나타납니다 (술어 시작/1, 후행 술어 s/2 및 목표 술어 목표/1에 의해 매개 변수화 됨). 루프 검사를 추가했습니다.

 
bfs(Res) :- start(Start), empty_queue(EQ), 
    queue_append(EQ,[e(Start,[])],Q1), 
    bfs1(Q1,Res). 

bfs1(Queue,Res) :- queue_cons(e(Next,Path),NQ,Queue), 
    bfs2(Next,Path,NQ,Res). 

bfs2(H,Path,_NQ,Res) :- goal(H), reverse([H|Path],Res). 
bfs2(H,Path,NQ,Res) :- 
       findall(e(Succ,[H|Path]), 
         (s(H,Succ),\+ member(Succ,Path)),AllSuccs), 
       queue_append(NQ,AllSuccs,NewQueue), 
       bfs1(NewQueue,Res). 

(. 또한 시도하고 대체/더 나은 자료 구조에 의해 경로 구성 요소를 보완 할 수있는, 예를 들어, AVL-나무) 해결하기 예제 문제는 다음과 같습니다

 
start(env(0,0)). 
s(env(X,Y),env(X1,Y)) :- X1 is X+1. 
s(env(X,Y),env(X,Y1)) :- Y1 is Y+1. 
goal(env(3,3)). 

당신은 또한 수 대기열을 우선 순위 대기열로 교체하고 경험적 방법을 사용하여 우선 순위를 계산합니다. 그런 다음 A * 검색을 얻습니다.이 검색은 깊이 우선, 폭 우선, 최상 우선 등을 에뮬레이트 할 수 있습니다. Bratko의 책 (인공 지능을위한 논리 프로그래밍)은이 자료를 읽을 좋은 자료 여야합니다.