Пролог получить элементы в разных списках с BFS - PullRequest
Новая
       21

Пролог получить элементы в разных списках с BFS

2 голосов
/ 06 января 2011

Я новичок в прологе, и чтобы улучшить свои навыки, я пытаюсь сделать какое-то упражнение.На данный момент я застрял с BFS, давайте предположим, что дерево выглядит примерно так: 

[tree(tree(tree(nil,b,nil),a,tree(tree(nil,d,nil),c,tree(nil,e,nil)))]

после моего запроса у меня что-то вроде 

X=a;

X=b;

X=c;

X=d;

X=e;

или, по крайней мере,: 

X=a,b,c,d,e;

Меня интересует, как получить результаты, упорядоченные по уровням глубины в качестве вывода, что-то вроде: 

X=[a];

X=[b,c];

X=[d,e];

или, в лучшем случае, что-то вроде: 

X=[ [a] , [b,c] , [d,e] ];

Помогите!

Ответы [ 2 ]

1 голос
/ 06 января 2011

У меня есть решение, но оно не особенно эффективно. Я реализовал дерево в виде набора из трех списков элементов, таких как [Элемент, Левый, Правый], но оно должно работать так же. 

% returns a list of nodes at the given level of the tree
level( [], _, [] ).
level( [Element, _, _], 0, [Element] ) :- !.
level( [_, Left, Right], N, Result ) :-
    NewN is N - 1,
    level( Left, NewN, LeftResult ),
    level( Right, NewN, RightResult ),
    append( LeftResult, RightResult, Result ).

% does a bfs, returning a list of lists, where each inner list
% is the nodes at a given level
bfs( Tree, Result ) :-
    level( Tree, 0, FirstLevel ), !,
    bfs( Tree, 1, FirstLevel, [], BFSReverse ),
    reverse( BFSReverse, Result ).
bfs( _, _, [], Accum, Accum ) :- !.
bfs( Tree, Num, LastLevel, Accum, Result ) :-
    level( Tree, Num, CurrentLevel ), !,
    NewNum is Num + 1,
    bfs( Tree, NewNum, CurrentLevel, [LastLevel|Accum], Result ).

Должно быть возможно сделать это в O (n), но это O (n ^ 2). Я начал работать над другим решением, которое возвращает уровень каждого элемента в O (n), но я не уверен, как преобразовать этот список в формат решения в O (n), не прибегая к assert / retract.

0 голосов
/ 06 января 2011

Лучшее решение, на этот раз O (n). Это все еще немного уродливо, потому что я отделил фактическую BFS от обработки решения, но это должно сработать. 

bfs2( Tree, Result ) :-
    bfs_queue( [[Tree, 0]], Queue ),
    queue_to_result( Queue, Result ).
bfs_queue( [], [] ) :- !.
bfs_queue( [[[],_]|Rest], RestResult ) :-
    !, bfs_queue( Rest, RestResult ).
bfs_queue( [[[Element, Left, Right], Level]|Rest], [[Element,Level]|RestResult] ) :-
    NextLevel is Level + 1,
    append( Rest, [[Left, NextLevel], [Right, NextLevel]], NewQueue ), !,
    bfs_queue( NewQueue, RestResult ).

process_level( [[Item, Level]|Rest], Level, [Item|RestResult], OutOfLevel ) :-
    !, process_level( Rest, Level, RestResult, OutOfLevel ).
process_level( OutOfLevel, _, [], OutOfLevel ) :- !.
queue_to_result( Queue, Result ) :-
    !, queue_to_result( Queue, 0, Result ).
queue_to_result( [], _, [] ) :- !.
queue_to_result( Queue, Level, [Current|Result] ) :-
    !, process_level( Queue, Level, Current, NewQueue ),
    NewLevel is Level + 1,
    queue_to_result( NewQueue, NewLevel, Result ).

Опять же, я представлял деревья в виде трехэлементных списков.

...