Пролог: Kth Самый большой элемент списка [дубликат]

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

Я нашел статью в Википедии о алгоритме выбора очень полезно для понимания большей картины алгоритмов «быстрого» (наихудшего линейного времени) этого типа.

Но то, что вы задали в конце вашего Вопроса, несколько проще дело. Вы написали «Как мне это сделать? Я могу выбрать элемент из списка, но я не знаю, как получить наибольшую пользу, используя описанную выше процедуру». (выделено мной мной)

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

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

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

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

maxOfList(H,[H|T]) :-  upperBound(H,T), !.
maxOfList(X,[_|T]) :-  maxOfList(X,T).

upperBound(X,[ ]).
upperBound(X,[H|T]) :-
    X >= H,
    upperBound(X,T).

Идея должна быть понятной. Мы смотрим на главу списка и спрашиваем, является ли эта запись верхней границей для остальной части списка. Если это так, это должно быть максимальное значение, и мы закончили (разрез делает его детерминированным). Если нет, то максимальное значение должно появиться позже в списке, поэтому мы отбрасываем голову и продолжаем рекурсивно искать запись, которая является верхней границей всех последующих элементов. Сокращение важно здесь, потому что мы должны остановиться на первой такой записи, чтобы знать, что это максимум исходного списка.

Мы использовали вспомогательный предикат upperBound / 2, что не является чем-то необычным , но общая сложность этой реализации в худшем случае квадратична по длине списка. Таким образом, есть место для улучшения!

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

Добавлено:

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

Вместо этого Пролог делает это, чтобы ввести дополнительный аргумент и определите предикат maxOfList / 2 вызовом вспомогательного предиката с тремя аргументами:

maxOfList(X,[H|T]) :- maxOfListAux(X,H,T).

Дополнительный аргумент в maxOfListAux / 3 затем можно использовать для отслеживания наибольшего значения «до сих пор» следующим образом:

maxOfListAux(X,X,[ ]).
maxOfListAux(Z,X,[H|T]) :-
    ( X >= H  -> Y = X ; Y = H ),
    maxOfListAux(Z,Y,T).

Здесь первый аргумент maxOfListAux представляет собой окончательный ответ на самый большой элемент списка, но мы не знаем этого ответа, пока не опустеем список. Таким образом, первое предложение здесь «завершает» ответ, когда это происходит, объединяя первый аргумент со вторым аргументом (наибольшее значение «до сих пор»), только когда конец списка достиг конца.

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

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

maxOfList(X,[X]) :- !.
maxOfList(X,[H1,H2|T]) :-
    ( H1 >= H2  -> Y = H1 ; Y = H2 ),
    maxOfList(X,[Y|T]).