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

Краткая выдержка из текста работы (Аннотация)

Введение

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

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

Теория графов — раздел дискретной математики, особенностью ко¬то¬рого является геометрический подход к изучению объектов. Первые за¬да¬чи теории графов были связаны с решением математических развлека¬тель¬ных задач и головоломок (задача о Кёнингсбергских мостах, задача о рас¬ста¬нов¬ке ферзей на шахматной доске, задачи о перевозках, задача о кру¬го¬свет¬ном путешествии и др.). В общем смысле граф (сеть) 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 с.

Другие похожие работы

• Шпаргалка - Шпоры по С/С++ на экзамен
• Курсовая - Моделирование систем
• Курсовая - База данных на Delphi сведения о рабочих
• Отчет - Основные принципы архивации, классификации методов. Алгоритм Хаффмана.
• Курсовая - Вращающийся икосаэдр
• Курсовая - Программа чтения результатов лыжников и печать их в порядке неубывания времени
• Учебник - Основы алгоритмизации и программирования
• Курсовая - Технология разработки программных продуктов.
• Дипломная - Конфигуратор системных блоков персональных компьютеров
• Курсовая - Искусственный интеллект и экспертные системы