'

Тема: Применение теории графов в программировании

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

Главная функция и инициализация глобальных переменных 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]); }


Слайд 5

Метод «грубой силы» 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] } }


Слайд 6

Метод ветвей и границ 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; } }


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

Источники Программирование на языке Си; К. Поляков, 1995-2009 http://www.mtas.ru/start/t_garf.pdf http://ru.wikipedia.org/wiki/%C7%E0%E4%E0%F7%E0_%EA%EE%EC%EC%E8%E2%EE%FF%E6%E5%F0%E0 http://www.mgopu.ru/PVU/2.1/Recurs/BacketTm/CnReturn/travel.htm http://www.ref.by/refs/49/33898/1.html


×

HTML:





Ссылка: