Алгоритм Форд-Беллмана на Prolog

@w_mark_w · Регистрация: 14.01.2019

Студворк — интернет-сервис помощи студентам

Написать программу, реализующую алгоритм Беллмана-Форда. Стало интересно как реализовать его на языке SWI-Prolog. Заранее спасибо!

@arlat · 09.12.2020, 15:50

Сообщение от w_mark_w

Стало интересно

Понятно. А где попытки? И собственно, каков начальный уровень знания Пролога?
Все очень зависит. Просто перебор используя механизм Пролога, так это рекурсия с сохранением по ходу пройденных путей, чтобы не бегать безконечно

Если же речь идет о приличных размерах графа и требуется оптимизация, то там уже надо подумать...
Вы начните хоть с простейшего варианта, википедить и додумывать ограничения... тут по Прологу форум

Нарисуйте, опишите словами, что по Вашему должно происходить, в Прологе так и делается, - "что вижу,то пою"

@w_mark_w · 11.12.2020, 08:52 **[ТС]**

Я просто даже не знаю как подступиться к выполнению на Prolog

Я делал простейшую задачу на прологе по поиску внуков, племянников и прочей родни в семейном древе. Но само древо создаётся внутри кода ручками:

Prolog
1
2
родитель(петя, стёпа).
родитель(мария, степа).

Ну и смотря на то, как Prolog здорово работает с графами, мне стала интересна реализация алгоритма Форд-Беллмана

Добавлено через 8 минут
Ну и смотря на то, как Prolog здорово работает с графами, мне стала интересна реализация алгоритма Форд-Беллмана

Насчёт "что вижу, то и пою":

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

Prolog
1
:-dynamic graph/3.

@arlat · 11.12.2020, 09:38

Сообщение от w_mark_w

-dynamic graph/3.

Зачем динамический факт?
Просто как и по родителям запишите факты для направленного графа.
Вот взял отсюда Алгоритм Беллмана-Форда

@arlat · 11.12.2020, 09:52

Prolog
1
2
3
4
graph(a, b, -1).
graph(a, c, 4).
graph(b, c, 3).
graph(b, e, 2).

ну и т.д.
Пользуйтель прямо в онлайн swi-prolog

Добавлено через 8 минут
поищите по форуму
Поиск пути в подземной галерее
да много можно нарыть при желании, немного разберетесь, тогда уже в плотную к вашей задаче

Добавлено через 1 минуту
ну вот же. на самом видном месте
Поиск в пространстве состояний (поиск по графам тоже сюда!)

@w_mark_w · 11.12.2020, 11:46 **[ТС]**

Спасибо, теперь понял!

Новые блоги и статьи Все статьи Все блоги /
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .

@w_mark_w 14 / 3 / 1 Регистрация: 14.01.2019 Сообщений: 52

	Алгоритм Форд-Беллмана на Prolog 09.12.2020, 12:16. Показов 1928. Ответов 5 Метки prolog, алгоритм, алгоритм поиска, графы (Все метки) Написать программу, реализующую алгоритм Беллмана-Форда. Стало интересно как реализовать его на языке SWI-Prolog. Заранее спасибо! 0

@w_mark_w 14 / 3 / 1 Регистрация: 14.01.2019 Сообщений: 52
	11.12.2020, 11:46 [ТС]
	Спасибо, теперь понял! 0

Алгоритм Форд-Беллмана на Prolog

Решение