Задача Прима-Каскала .

Введение Многие задачи, с которыми приходится иметь дело в повседневной прак¬тике, являются многовариантными. Среди множества возможных ва¬ри¬ан¬тов в условиях рыночных отношений приходится отыскивать наилучшие, в некотором смысле при ограничениях, налагаемых на природные, эконо¬ми¬ческие и технологические возможности. В связи с этим возникла необ¬хо¬ди¬мость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Как в самой математике, так и в ее приложениях широко используются графы. Теория графов даёт исключительно удобный аппарат для мо¬де¬ли¬ро¬ва¬ния структурных свойств различных систем и отношений между объектами разной природы, в том числе программных моделей. Теория графов — раздел дискретной математики, особенностью ко¬то¬рого является геометрический подход к изучению объектов. Первые за¬да¬чи теории графов были связаны с решением математических развлека¬тель¬ных задач и головоломок (задача о Кёнингсбергских мостах, задача о рас¬ста¬нов¬ке ферзей на шахматной доске, задачи о перевозках, задача о кру¬го¬свет¬ном путешествии и др.). В общем смысле граф (сеть) G = (V, E) состоит из конечного, непустого множества m вершин ( m ≤ 1) и конечного множества n неупорядоченных пар элементов [u, v] (n ≥ 0), называемых рёбрами графа G. В строгом определении графом называется такая пара множеств G = {R, V}, где V есть подмножество любого счётного множества, а R — подмножество VxV. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооруже¬ния, кварталы и т. п. рассматриваются как вершины, а соединяющие их доро¬ги, инженерные сети, линии электропередач и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут. Графы могут быть представлены в ЭВМ матрицей смежности, инци¬дент¬ности или матрицей весов. Существуют такие модели задач динами¬ческого программирования: модель распределения усилий (инвестиций), модель замены оборудования, поиск кратчайшего пути на графе, задачи календарного планирования, поиск критического пути, вычисление ранних и поздних сроков наступления событий. Цель курсовой работы – решить задачу о жадном «алгоритме», посвященной нахождению минимальной суммы длин между его вершинами методом Прима- Краскала средствами SWI-Prolog.

Содержание Введение 3 Теоретические сведения 5 Формат исходных данных 9 Описание алгоритма 10 Тестовые примеры 11 Список литературы 14 Приложения 15 Приложение 1. Текст программы 15 Приложение 2. Тест программы 18

Список литературы 1. Mалпас Дж. Реляционный язык Пролог и его применение. – М.: Наука. Гл.ред. физ.-мат. лит., 1990. – 464 с. 2. Братко И. Программирование на языке Пролог для искусственного интеллекта. – М.: "МИР", 1990. 3. Новиков Ф.А. Дискретная математика для программистов. – С.-Петербург: Питер, 2001. – 304 с. 4. Адаменко А., Кучуков А. Логическое программирование и Visual Prolog. – Спб.: БХВ-Петербург, 2003. – 992 с.