Список прологов Поиск

Question

Я пытаюсь определить предикат, где он ищет список списков для элемента и возвращает уровень этого элемента. Например, при поиске элемента:

?- elementLevel(element,[a,b,c,[d,e],[element,f]],Level). 
Level = 2 . 

Так что для каждого списка он добавляет уровень. Я думал о счетчике, но я не знаю, как реализовать это для обхода списка.

Answer 1

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

Вам понадобится один факт и три правила.

Этот факт будет игнорировать элемент (т. Е. Использовать _), унифицировать список с пустым списком и сказать, что возвращаемый уровень равен -1 (не найден).

Первым и вторым правилом будет поиск списка «учебник», объединяющий элемент с головой списка и возвращающий уровень 1; другое правило игнорирует голову и возвращает уровень элемента в хвосте.

Окончательное правило будет унифицировать заголовок списка с вложенным списком головы и хвоста, сделать рекурсивный вызов и проверить возвращаемое значение, чтобы увидеть, больше ли оно нуля. Если это так, возвращаемое значение - это вложенный возврат плюс один; в противном случае, рекурсивно проверить хвост и вернуть результат этой проверки.

Answer 2

вы можете определить предикат, как это для реализации счетчика ..

go:- 
ListLevel=0, 
NumberTobeFound=5, 
go(List,NumberTobeFound,ItsLevel), 
write("Level",ItsLevel). 

go([Head|Tail],NumberTobeFound,ItsLevel):- 
Head>NumberTobeFound, 
NewItsLevel=ItsLevel+1, 
go(Tail,NumberTobeFound,NewItsLevel). 


go([Head|Tail],NumberTobeFound,ItsLevel):- 
Head<NumberTobeFound, 
NewItsLevel=ItsLevel+1, 
go(Tail,NumberTobeFound,NewItsLevel). 

go([Head|Tail],NumberTobeFound,ItsLevel):- 
write("Number Found.."), 
write("Its Level is : ",ItsLevel). 

Answer 3

Первое, что нужно отметить, что ваш «список списков» в корне структура дерева, и вы в основном делает глубину - первый, слева направо обход дерева.

Итак, вам нужен «общедоступный» предикат, который может искать дерево для элемента и возвращать его глубину. должен возврат возвращает все такие матчи:

tree_walk(X , Tree , Depth) :- 
    tree_walk(X , Tree , 0 , Depth) % seed the accumulator with an initial depth 
    . 

Тогда вам нужен работник предикат:

tree_walk(X , [ X | _ ] , D , D) % success! if the desired item is found 
    .         % 
tree_walk(X , [ Y | Ys ] , T , D) :- % otherwise... 
    T1 is T+1 ,       % - increment the depth 
    tree_walk(X , Y , T1 , D)   % - and recurse down on the head of the list 
    .         % 
tree_walk(X , [ _ | Ys ] , T , D) :- % if that failed, then 
    tree_walk(X , Ys , T , D)   % - recursively search the tail of the list 
    .         % 

Вот и все, что нужно сделать.

ПРИМЕЧАНИЯ

• Чтобы изменить его на поиск в ширину, все, что вам нужно сделать, я думаю, это изменить порядок последних двух положений работника предиката.

• если X несвязано или один из элементов в «списке списков» несвязан, вы, вероятно, столкнетесь с ... интересными проблемами. Для производственного кода вы хотите установить защитные меры для правильной работы с этими краевыми случаями.

Cheers!

Answer 4

Я думаю, что это большая часть пути .. он не возвращается, например. -1, если элемент не найден и будет сообщать о некорректных результатах, если элемент появляется дважды (т.е. он не останавливается при обнаружении элемента). Он просто показывает один базовый механизм.

% Base recursion/element found 
elementLevel(element, element, 0). 

% Any list with head and tail 
elementLevel(element, [H|T], NestLevel) :- 

    % Increment counter if H is a list/process possible sublists 
    (is_list(H) -> 
     elementLevel(element, H, NewLevel), 
     elementLevel(element, T, NewLevel), 
     NestLevel is NewLevel + 1 
    ; 

    % No increments, just recurse through items 
    elementLevel(element, H, NestLevel), 
    elementLevel(element, T, NestLevel) 
    ). 

% Prevent empty sublists from causing a fail 
elementLevel(element, _, _).