Эффективное представление изменяемого графа в прологе?

Question

Я хотел бы представить изменяемый граф в Прологе эффективным способом. Я буду искать подмножества в графе и заменять их другими подмножествами.

Мне удалось заставить что-то работать, используя базу данных в качестве моего «хранилища графиков». Например, у меня есть:

:- dynamic step/2.
% step(Type, Name).

:- dynamic sequence/2.
% sequence(Step, NextStep).

Затем я использую несколько правил для retract подмножеств, которые мне соответствуют, и заменяю их новыми шагами, используя assert. Мне действительно нравится этот метод ... с ним легко читать и иметь дело, и я позволил Прологу выполнить большую часть тяжелой работы по сопоставлению с образцом.

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

Время выполнения важно для меня, как и простота разработки для меня.

Каковы плюсы / минусы для любого подхода?

Answer 1

Как обычно: использование динамической базы данных дает вам возможность индексирования, что может ускорить процесс (при поиске) и замедлить (при подтверждении).В целом, динамическая база данных не так хороша, когда вы утверждаете чаще, чем смотрите вверх.Однако основным недостатком является то, что это также значительно усложняет тестирование и отладку, поскольку вы не можете тестировать свои предикаты изолированно и должны помнить о текущем неявном состоянии базы данных.Списки узлов и смежных соединений являются хорошим представлением во многих случаях.Мне очень нравится другое представление, особенно если вам нужно сохранить дополнительные атрибуты для узлов и ребер, - это использовать одну переменную для каждого узла и использовать переменные attribtues (get_attr / 3 и put_attr / 3 в SWI-Prolog) для хранения реберна них, например [edge_to (E1, N_1), edge_to (E2, N_2), ...] где N_i - это переменные, представляющие другие узлы (со своими собственными атрибутами), а E_j также являются переменными, к которым вы можете присоединитьатрибуты для хранения дополнительной информации (вес, емкость и т. д.) о каждом ребре, если это необходимо.

Answer 2

Рассматривали ли вы использование базы данных RDF SWI-Prolog? http://www.swi -prolog.org / pldoc / пакет / semweb.html

Answer 3

Как сказал Мат, динамические предикаты имеют дополнительную стоимость.
В случае, если вы можете построить график, и вам не нужно его менять, вы можете скомпилировать предикат, и он будет таким же быстрым, как и обычный предикат.

обычно в sw-прологе поиск предиката выполняется с использованием хеш-таблиц первого аргумента.(они изменяются в случае динамических предикатов)

другое решение - списки ассоциаций , где стоимость поиска и т. д. o (log (n))
после того, как вы поймете, как они работаютВы можете легко написать интерфейс, если это необходимо.

В конце концов, вы всегда можете использовать базу данных SQL и использовать ODBC интерфейс для отправки запросов (хотя это звучит как излишнее для приложенияВы упомянули)