Муравьиный алгоритм размещения вершин графа в линейке
ВВЕДЕНИЕ
Целью курсового проекта является разработка программной реализации решения задачи размещения графа в линейке муравьиным алгоритмом.
В соответствии с поставленной целью необходимо решить следующие задачи: изучить научную, образовательную и справочную литературу по теме исследования, систематизировать и обработать цифровой и теоретический материал по муравьиному алгоритму, определить содержательную и математическую постановку задачи, разработать программный продукт, проанализировать результаты, сделать выводы о проделанной работе.
Курсовая работа представляет собой применение муравьиного алгоритма с целью решения задачи о размещении графа в линейке, которая заключается в поиске оптимального расположения вершин графа в линейке, при котором сумма длины соединений всех вершин будет наименьшей.
В процессе выполнения курсовой работы были использованы: учебная, справочная, научно-производственная литература, онлайн-ресурсы, системы автоматизированного проектирования, использующиеся в разработке программных продуктов.
СОДЕРЖАНИЕ
Введение…………………………………………………………………………… 5
1 Содержательная постановка задачи………………………………………….......................................................... 6
2 Математическая постановка задачи……………………………………………… 8
3 Описание алгоритма решения задачи……………………………………………. 10
4 Решение задачи на контрольном примере……………………………………….. 12
5 Программная реализация алгоритма решения задачи и ее описание………….. 17
6 Примеры решения задачи…………………………………………………………. 18
Заключение……….……………………………………………………………… 22
Список литературы………………………………………………………………….. 23
Приложение А. Листинг программы……………………………………………….. 24
Приложение Б. Экранные формы программы….………………………………….. 32
СПИСОК ЛИТЕРАТУРЫ
1. Зыков А.Г., Поляков В.И. Алгоритмы конструкторского проектирования ЭВМ. СПб: Университет ИТМО, 2014.
2. Макконелл Дж. Основы современных алгоритмов. М.: Техносфера, 2004
3. Б.Н. Деньдобренко, А.С. Малика. Автоматизация конструирования РЭА: Учебник для вузов
4. Интуит. Транспортная задача.
5. Боборыкин В.А. Математические методы решения транспортных задач. СПб.: СЗПИ, 2014. - 170 с.
Исходными данными транспортной задачи является взвешенный ориентированный граф. Граф может быть представлен в различных формах: в виде матрице смежности или идентичности, так и в графической форме. Если граф представлен в виде графической форме или матрицы идентичности, необходимо преобразовать его в матрицу смежности. Результирующими данными транспортной задачи является опорный план, который приводит минимальные затраты при транспортировке товаров
Транспортная задача применяется для достижения следующих целей:
- Поиск наилучшего расположения полупроводниковых элементов на электросхемах с целью наименьшего расхода времени, материала, а также с целью уменьшения длины контактов.
- Оптимальное размещение оборудования. Задача решается уменьшением расстояний между оборудованием, укорачивая длину электрокабелей, и установка наиболее компактного оборудования с теми же или схожими характеристиками.
- Создания экономичного плана перевозок однородного груза из пункта производства в пункты потребления, чтобы снизить расходы на топливо и время нахождения в дороге.