Содержание
Содержание
Введение3
Теоретические сведения5
Формат исходных данных9
Описание алгоритма10
Тестовые примеры11
Список литературы14
Приложения15
Приложение 1. Текст программы15
Приложение 2. Тест программы18
Выдержка из текста
Введение
Многие задачи, с которыми приходится иметь дело в повседневной прак¬тике, являются многовариантными. Среди множества возможных ва¬ри¬ан¬тов в условиях рыночных отношений приходится отыскивать наилучшие, в некотором смысле при ограничениях, налагаемых на природные, эконо¬ми¬ческие и технологические возможности. В связи с этим возникла необ¬хо¬ди¬мость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику.
Как в самой математике, так и в ее приложениях широко используются графы. Теория графов даёт исключительно удобный аппарат для мо¬де¬ли¬ро¬ва¬ния структурных свойств различных систем и отношений между объектами разной природы, в том числе программных моделей.
Теория графов — раздел дискретной математики, особенностью ко¬то¬рого является геометрический подход к изучению объектов. Первые за¬да¬чи теории графов были связаны с решением математических развлека¬тель¬ных задач и головоломок (задача о Кёнингсбергских мостах, задача о рас¬ста¬нов¬ке ферзей на шахматной доске, задачи о перевозках, задача о кру¬го¬свет¬ном путешествии и др.). В общем смысле граф (сеть) G = (V, E) состоит из конечного, непустого множества m вершин ( m ≤ 1) и конечного множества n неупорядоченных пар элементов [u, v] (n ≥ 0), называемых рёбрами графа G. В строгом определении графом называется такая пара множеств G = {R, V}, где V есть подмножество любого счётного множества, а R — подмножество VxV. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооруже¬ния, кварталы и т. п. рассматриваются как вершины, а соединяющие их доро¬ги, инженерные сети, линии электропередач и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Графы могут быть представлены в ЭВМ матрицей смежности, инци¬дент¬ности или матрицей весов. Существуют такие модели задач динами¬ческого программирования: модель распределения усилий (инвестиций), модель замены оборудования, поиск кратчайшего пути на графе, задачи календарного планирования, поиск критического пути, вычисление ранних и поздних сроков наступления событий.
Цель курсовой работы – решить задачу о жадном «алгоритме», посвященной нахождению минимальной суммы длин между его вершинами методом Прима- Краскала средствами SWI-Prolog.
Список использованной литературы
Список литературы
1.Mалпас Дж. Реляционный язык Пролог и его применение. – М.: Наука. Гл.ред. физ.-мат. лит., 1990. – 464 с.
2.Братко И. Программирование на языке Пролог для искусственного интеллекта. – М.: «МИР», 1990.
3.Новиков Ф.А. Дискретная математика для программистов. – С.-Петербург: Питер, 2001. – 304 с.
4.Адаменко А., Кучуков А. Логическое программирование и Visual Prolog. – Спб.: БХВ-Петербург, 2003. – 992 с.