Слайд 2Гипотеза
Теория графов подходит для решения транспортных задач
Ее использование позволяет найти оптимальный, с
![Гипотеза Теория графов подходит для решения транспортных задач Ее использование позволяет найти](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-1.jpg)
точки зрения длины или стоимости, маршрут
Слайд 3Теория графов
Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В общем
![Теория графов Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-2.jpg)
смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.
Слайд 4Задача коммивояжера
Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по
![Задача коммивояжера Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-3.jpg)
разу в неизвестном порядке города 2,3,...n, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
Слайд 5Главная функция и инициализация глобальных переменных
int Pmin[N], // лучшая перестановка
P[N], // текущая
![Главная функция и инициализация глобальных переменных int Pmin[N], // лучшая перестановка P[N],](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-4.jpg)
перестановка
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]);
}
Слайд 6Метод «грубой силы»
void Commi( int q ) // q – число уже
![Метод «грубой силы» void Commi( int q ) // q – число](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-5.jpg)
поставленных вершин
{
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]
}
}
Слайд 7Метод ветвей и границ
void Commi( int q ) // q – число
![Метод ветвей и границ void Commi( int q ) // q –](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-6.jpg)
уже поставленных вершин
{
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;
}
}
Слайд 8Метод случайных перестановок
Используют метод случайных перестановок. В алгоритме повторяются следующие шаги:
1. Выбрать
![Метод случайных перестановок Используют метод случайных перестановок. В алгоритме повторяются следующие шаги:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-7.jpg)
случайным образом номера вершин i и j в перестановке.
2. Если при перестановке вершин с номерами i и j длина пути уменьшилась, такая перестановка принимается.
Слайд 9Использование теории графов в других сферах
В химии;
В информатике и программировании
В коммуникационных
![Использование теории графов в других сферах В химии; В информатике и программировании](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-8.jpg)
и транспортных системах
В экономике
В логистике
В схемотехнике
Слайд 10Дополнительные материалы
Графы как waypoints: AVIГрафы как waypoints: AVI MPG
![Дополнительные материалы Графы как waypoints: AVIГрафы как waypoints: AVI MPG](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-9.jpg)
Слайд 11Заключение
Графы находят широкое применение в различных сферах жизни;
Они позволяют решать задачи оптимизации,
![Заключение Графы находят широкое применение в различных сферах жизни; Они позволяют решать](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-10.jpg)
конструирование и нахождения оптимального маршрута.
Слайд 12Промо – ролик
Avi version.
Mpg version.
![Промо – ролик Avi version. Mpg version.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/441606/slide-11.jpg)