Санкт-Петербургский колледж Информационных технологий Студенческое научное общество «Шаг в будущее» 7-я итоговая студенческая научно-практическая конференция Тема: Применение теории графов в программировании Работу выполнили: студенты группы 02 Лапин Сергей Надыршин Илья Преподаватель-консультант: Шапкина Лидия Михайловна Санкт-Петербург, май 2011

Гипотеза Теория графов подходит для решения транспортных задач Теория графов подходит для решения транспортных задач Ее использование позволяет найти оптимальный, с точки зрения длины или стоимости, маршрут Ее использование позволяет найти оптимальный, с точки зрения длины или стоимости, маршрут

Теория графов Тео́рия гра́фов раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E подмножество V×V.

Задача коммивояжера Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по разу в неизвестном порядке города 2,3,...n, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Главная функция и инициализация глобальных переменных int Pmin[N], // лучшая перестановка P[N], // текущая перестановка Lmin, // минимальная длина L, // текущая длина D[N][N]; // матрица расстояний void main() { Lmin = 32767; // большое число L = 0; P[0] = 1; // начальная вершина 1 Commi(1); // построить тур for ( int i = 0; i < N; i ++ ) // вывести результат printf("%d ", Pmin[i]); }

Метод «грубой силы» void Commi( int q ) // q – число уже поставленных вершин { int i, temp; if ( q == N ) { // перестановка получена if ( L < Lmin ) { Lmin = L; for ( i = 0; i < N; i ++ ) // запомнить новый минимальный тур Pmin[i] = P[i]; } return; } for ( i = q; i < N; i ++ ) { temp = P[q]; P[q] = P[i]; P[i] = temp; // P[q] P[i] L += D [P[q-1]] [P[q]]; // добавить ребро Commi ( q+1 ); // рекурсивный вызов L -= D [P[q-1]] [P[q]]; // убрать ребро temp = P[q]; P[q] = P[i]; P[i] = temp; // P[q] P[i] }

Метод ветвей и границ void Commi( int q ) // q – число уже поставленных вершин { int i, temp; if ( q == N ) { // перестановка получена if ( L < Lmin ) { Lmin = L; for ( i = 0; i < N; i ++ ) // запомнить новый минимальный тур Pmin[i] = P[i]; } return; } for ( i = q; i < N; i ++ ) { temp = P[q]; P[q] = P[i]; P[i] = temp; L += D [P[q-1]] [P[q]]; if ( L < Lmin ) Commi ( q+1 ); L -= D [P[q-1]] [P[q]]; temp = P[q]; P[q] = P[i]; P[i] = temp; }

Метод случайных перестановок Используют метод случайных перестановок. В алгоритме повторяются следующие шаги: 1. Выбрать случайным образом номера вершин i и j в перестановке. 2. Если при перестановке вершин с номерами i и j длина пути уменьшилась, такая перестановка принимается.

Использование теории графов в других сферах В химии; В информатике и программировании В коммуникационных и транспортных системах В экономике В логистике В схемотехнике

Дополнительные материалы Графы как waypoints:AVI MPGAVIMPG

Заключение Графы находят широкое применение в различных сферах жизни; Они позволяют решать задачи оптимизации, конструирование и нахождения оптимального маршрута.

Промо – ролик Avi version. Mpg version.

Источники Программирование на языке Си; К. Поляков, C%EC%E8%E2%EE%FF%E6%E5%F0%E0 htm