Задача Прима-Краскала на языке Пролог

[neuotq]

Ох…
А в Универе Пролог был моим любимым языком.
Из-за этого подсознательно немного в штыки воспринимал Лисп.

[Yagami]

Пролог интересен. Но после C++ и Паскаля очень непривычно. Лисп тоже проходил (бегло).

[Maccimo]

Меня в своё время больше всего в Прологе удивили переменные с однократной записью.

[spiff]

Пролог… Как много в этом слове. После курса логического программирования и решения задач типа «Маша любит Васю, Женя живет в крайнем доме. Кто из них учитель?» остался только один вопрос. Ну как там работает отсечение? Ну как??!!! Помню с потока никто не мог объяснить как оно работает, но кажды знал, что если поставить вослицательный знак в «этот» предикат все сразу решится.

[vics001]

Отсечение лучше не использовать никогда :) Начинающим программистам, лучше избегать отсечений в середине и даже не думать о том, что бывают группы отсечений как a :- b, !, c, !, d (это не 2 отсечения!).

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

a :- b,!..
a :- c,…

Отсечение в конце означает, что если 1-й предикат выполнится, то альтернатив не будет. То есть выполнится хотя бы один раз b, c никогда вызываться не будет и b больше вызываться не будет, хотя b может давать например несколько ответов!

a :- !, b.
a :- c,…

Отсечение в начале c никогда не вызывается, а b вызывается столько раз, сколько альтернатив ответов в b.

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

[karlicos]

Вы бы хоть объяснили алгоритм с точки зрения логического программирования. Не думаю, что тут много людей с этим знакомы, да и с синтаксисом Prolog. Я один, например, не понимаю, зачем предикат(или тут так любая функция называется?) вставляет что-то или ищет минимум?

[vics001]

Хотел немного помочь с форматированием, но как-то чересчур увлекся и получился аналогичный вариант решения, хотя идея та же.

% Вначале текущее множество рёбер устанавливается пустым. 
% Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых 
%   к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса 
%   и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. 

% Пример запроса (картинка http://www.youtube.com/watch?v=vm_9-vnV7PE)
example(Res) :- city([edge(1,3,13), edge(1,4,19),edge(3,2,20),edge(4,2,4), edge(2,5,15),   edge(4,7,17),edge(5,7,8),edge(5,6,22),edge(7,6,10)], Res).

city(DistanceCities, ResultConfiguration) :- city(DistanceCities, [], ResultConfiguration).

% city(DistanceCities, ExistingConfiguration, ResultConfiguration)
% ищем минимальное ребро : если найдено, то 1) продолжаем выделять ребра, 
% добавив найденное к существующим ,если  не найдено - 2) алгоритм завершен
city(Distances, Existing, ResultConfiguration) :- 
    (pick_minimum_edge_wo_cycle(Distances, Existing, Edge) -> 
      city(Distances, [Edge | Existing], Result), ResultConfiguration = [Edge | Result]  ;
       ResultConfiguration = [] ) .

% Выбирает минимальное ребро не образующее цикла,
% Нисходящая рекурсия сравнивает уже выбранное допустимое минимальное ребро
% на предыдущих шагах (1-й выбор []) с текущим ребром, проверяя допустимость
% Восходящая рекурсия возвращает результат и проверяет, что не [].
pick_minimum_edge_wo_cycle(Distances, Existing, Edge) :- 
		pick_minimum_edge_wo_cycle(Distances, Existing, [], Edge), not(Edge = []).

pick_minimum_edge_wo_cycle([], _, ToCompare, ToCompare).
pick_minimum_edge_wo_cycle([Edge|L], Existing, ToCompare, Result) :-  (
	(less_edge(Edge, ToCompare), no_cycle(Edge, Existing) )      -> 
		pick_minimum_edge_wo_cycle(L, Existing, Edge, Result)      ;
		pick_minimum_edge_wo_cycle(L, Existing, ToCompare, Result) ).

% Сравнение ребер - возвращает true если 1-е меньше 2-го
less_edge(edge(_X1, _Y1, Z1), edge(_X2, _Y2, Z2)) :- Z1 < Z2.
less_edge(edge(_X1, _Y1, _Z1), []).

% Проверка что нет цикла
no_cycle(edge(X, Y, _), Existing) :- not(search(X, Y, Existing, [])).

% реализует поиск пути от вершины Х к вершине Y
% алгоритм поиска - поиск в глубину.
search(X, Y, Edges,_):- member(edge(X,Y,_), Edges).
search(X, Y, Edges,_):- member(edge(Y,X,_), Edges).
search(X, Y, Edges, PassedVertices):- member(edge(X,Z, _),Edges), 
		not(member(Z, PassedVertices)), search(Z,Y,Edges,[Z|PassedVertices]).
search(X, Y, Edges, PassedVertices):- member(edge(Z,X, _),Edges), 
		not(member(Z, PassedVertices)), search(Z,Y,Edges,[Z|PassedVertices]).

[tranquil]

Уникальная ситуация с прологом. Исторически сложилось так, что на всех компьютерных специальностях его преподают. Вместе с тем, нигде он не используется на практике. Студентам показывают невероятные возможности языка, а потом они уходят в недоумении: «Зачем оно нужно?».

[knekrasov]

Задавался тем же вопросом. 60-70-е годы — ладно, тот же Буран управлялся программой на Прологе.
Но вот сейчас он где-нибудь используется?

[graninas]

Уникальная ситуация, поскольку и язык уникальный. А где его толком применишь? Только разве что для упорядочивания мышления.

А создателям Бурана это делает честь… Жаль, что он не взлетел.

[Maccimo]

Упоминания о том, что ПО Бурана писалось на ЯП под названием «Пролог» я встречал. Но ни где не видел ни подтверждения, ни опровержения того, что «тот» пролог и «этот» — одно и то же.

Что вообще можно почитать про ПО Бурана?
Желательно не обзор на пол-странички, а более детально.

[knekrasov]

К сожалению видел только обзоры

[Finom]

Я уже забыл особенности программирования на прологе (а они забываются быстро), но запомнил мысль, мелькающую у меня в голове во время изучения: на базе пролога можно создать мощнейшую СУБД. Может и бред… К сожалению, нет времени восполнить знания.

[tranquil]

www.vldb.org/journal/VLDBJ3/P245.pdf

Почему этот проект не взлетел, неизвестно. Больше упоминаний о нём я не видел. Надо будет написать вопрос кому-нибудь из Мельбурнского университета, поинтересоваться. Сейчас там делают язык программирования Mercury — какой-то статически типизированный пролог.

Я тоже всегда считал что для общих задач программирования пролог подходит очень слабо. А вот как база данных и язык запросов он может дать большую фору SQL.

На нём в несколько символов записываются join'ы, в один запрос можно запросить информацию рекурсивно без хранимых процедур. Да и задание запросов сложными предикатами более гармонично чем хранимые процедуры SQL.

stackoverflow.com/questions/2117651/difference-between-sql-and-prolog

Есть ещё подмножество пролога под называнием Datalog. Этот язык ориентирован исключительно на базы данных, без всяких процедурных функций. Но, практических реализаций я не нашёл. Только прототипы и программы для обучения.

У меня тоже зреет мысль разработать субд на базе пролога. И хотя WAM реализуется достаточно быстро, на минимально готовый продукт уйдёт несколько человеколет. Да и рынок такая субд взорвёт не сразу. Поэтому придётся отложить реализацию до времён, когда появятся такие свободные ресурсы.

[Maccimo]

Введение в Пролог было в советских учебниках по ОИВТ. С русскоязычными именами предикатов.
Но увы, нам ничего, кроме бейсика на уроках информатики не давали.