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

Я новичок в прологе и улучшаю свои навыки, я пытаюсь сделать некоторые упражнения. На данный момент я застрял с BFS, пусть предположим, что дерево что-то вроде этого:Пролог получает элементы в разных списках с 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] ];

Помощь!

источник

2011-01-06 RobCos

thx to Tim Cooper для исправления моего сообщения, я довольно noob ^^ " – RobCos

Лучшее решение, на этот раз 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).

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

источник

2011-01-06 09:37:03

спасибо !! Это работает !! Я изучаю« Learn Prolog Now », но я думаю, что это слишком просто. книга для изучения от? – RobCos

Эта версия работает значительно хуже, чем bfs/2. Я тестировал ее с помощью: n_tree (0, []): -!. n_tree (N0, [N0, Left, Right]): - N1 - N0 - 1, n_tree (N1, Left), n_tree (N1, Right) и запрос:? - между (0, 20, N), n_tree (N, T), time (bfs (T, Nodes)), false с обеих версий. – mat

Константа намного выше с этим, потому что она генерирует промежуточный список списков. Кроме того, bfs/2 становится намного хуже по мере роста дерева, а на уровне обработки n он должен пересекать уровни 0 до n - 1, и он не сохраняет никаких промежуточных элементов. Следовательно, O (n^2). –

У меня есть решение, но оно не особенно эффективно. Я реализовал дерево как группу из трех списков элементов, таких как [Element, Left, Right], но он должен работать одинаково.

% 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.

источник

2011-01-06 07:28:31

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

ответ

Смежные вопросы