Поиск оптимального пути в ненагруженном орграфе

курсовая работа: Математика

Документы: [1]   Word-213063.doc Страницы: Назад 1 Вперед

Содержание


1. Введение

2. Теоретическая часть

а) Основные понятия теории графов

б) Понятия смежности, инцидентности, степени

в) Маршруты и пути

г) Матрицы смежности и инцедентности

3. Алгоритм поиска минимального пути из в в ориентированном орграфе (алгоритм фронта волны)

4. Листинг программы

5. Примеры выполнения программы

6. Использованная литература

Введение


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

Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии),также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.

Кратчайший путь рассматривается при помощи графов.

Цель курсовой работы:

Разработать программу поиска оптимального пути в ненагруженном ориентированном графе на любом языке программирования.

Теоретическая часть:


а) Основные понятия теории графов


Теория графов как теоретическая диiиплина может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Как прикладная диiиплина теория графов позволяет описывать и исследовать многие физические, технические, экономические, биологические, социальные и другие системы. Например, графом, изображенным на рис. 1, в котором точки тИТ вершины графа тИТ города, линии, соединяющие вершины тИТ ребра тИТ дороги, соединяющие города, описывается так называемая транспортная задача (задача нахождения кратчайшего пути из одного города- пункта в другой).


Рис. 1.


Формальное определение графа таково. Пусть задано конечное множество V, состоящее из n элементов, называемых вершинами графа, и подмножество X декартова произведения VГЧV, то есть , называемое множеством дуг, тогда ориентированным графом D называется совокупность (V,X). Неориентированным графом G называется совокупность множества V и множества ребер тИТ неупорядоченных пар элементов, каждый из которых принадлежит множеству V.

Одинаковые пары - параллельные или кратные ребра;

Кратностью ребер называют количество одинаковых пар.


Рис.2.


Например, кратность ребра {v1,v2} в графе, изображенном на рис. 2, равна двум, кратность ребра {v3,v4} тИТ трем.

Псевдограф тИТ граф, в котором есть петли и/или кратные ребра.

Мультиграф тИТ псевдограф без петель.

Граф тИТ мультиграф, в котором ни одна пара не встречается более одного раза.

Граф называется ориентированным, если пары (v,w) являются упорядоченными.

Ребра ориентированного графа называются дугами.

Итак, используемые далее обозначения:

V - множество вершин;

X - множество ребер или дуг;

v (или vi)- вершина или номер вершины;

G, G0 - неориентированный граф;

D, D0 - ориентированный;

{v,w} тИТ ребра неориентированного графа;

{v,v} - обозначение петли;

(v,w) тИТ дуги в ориентированном графе;

v,w - вершины, x,y,z - дуги и ребра;

n(G), n(D) количество вершин графа;

m(G) - количество ребер, m(D) - количество дуг.

Примеры

1) Ориентированный граф D=(V, X), V={v1, v2, v3, v4},

X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.


Рис. 3.


2) Неориентированный граф G=(V, X), V={v1, v2, v3, v4, v5},

X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.


Рис. 4.


б) Понятия смежности, инцидентности, степени

Если x={v,w} - ребро, то v и w тИТ концы ребер.

Если x=(v,w) - дуга ориентированного графа, то v тИТ начало, w - конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x ).

Вершины v, w называются смежными, если {v,w}ГОX.

Степенью вершины v графа G называется число d (v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 - висячей.

Полустепенью исхода (захода) вершины v ориентированного графа D называется число d+(v) (d-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).

в) Маршруты и пути

Последовательность v1x1v2x2v3...xkvk+1, (где kВі1, viГОV, i=1,...,k+1, xiГОX, j=1,...,k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) xj имеет вид {vj,vj+1} (для ориентированного графа (vj,vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).

Длина маршрута (пути) тИТ число ребер в маршруте (дуг в пути).

г) Матрицы смежности и инцидентности

Пусть D=(V,X) ориентированный граф, V={v1,...,vn}, X={x1,...,xm}.

Матрица смежности ориентированного графа D тИТ квадратная матрица

A(D)=[aij] порядка n, где



Матрица инцидентности тИТ матрица B(D)=[bij] порядка nВґm, где


Матрицей смежности неориентированного графа G=(V,X) называется квадратная симметричная матрица A(G)=[aij] порядка n, где


.


Матрица инцидентности графа G называется матрица B(G)=[bij] порядка nВґm, где



Алгоритм поиска минимального пути из в в ориентированном орграфе (алгоритм фронта волны)

1) Помечаем вершину индексом 0, затем помечаем вершины ГО образу вершины индексом 1. Обозначаем их FW1 (v). Полагаем k=1.

2) Если или k=n-1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается.

В противном случае продолжаем:

3) Если , то переходим к шагу 4.

В противном случае мы нашли минимальный путь из в и его длина равна k. Последовательность вершин

теория орграф матрица алгоритм

есть этот минимальный путь. Работа завершается.

4) Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем . Присваиваем k:=k+1 и переходим к 2).

Замечания

Множество называется фронтом волны kго уровня.

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

Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу минимальных расстояний R(D)между его вершинами. Это квадратная матрица размерности , элементы главной диагонали которой равны нулю (, i=1,..,n).

Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний (, если ). Далее построчно заполняем матрицу следующим образом.

Рассматриваем первую строку, в которой есть единицы. Пусть это строка тИТ i-тая и на пересечении с j-тым столбцом стоит единица (то есть ). Это значит, что из вершины можно попасть в вершину за один шаг. Рассматриваем j-тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент . Тогда из вершины в вершину можно попасть за два шага. Таким образом, можно записать . Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.

Листинг программы:


#include<stdio.h>

#include<iostream>

using namespace std;

int main()

{

int N=0,n=0,c=0,i=0,k=0;

cout<<" ----------------------------------------------"<<endl;

cout<<" |Poisk optimalnogo puti v nenagrujennom orgrafe|"<<endl;

cout<<" ----------------------------------------------"<<endl;

case1:

cout<<"Vvedite chislo vershin v orgrafe: ";

cin>>N;

if(N<=1)

{

       cout<<"Kolichestvo vershin doljno bit'>1!!!"<<endl;

       goto case1;

}

///МАТРИЦА смежности::

cout<<"Zapolnite matricu smejnosti (esli puti net,vvedite 0; esli put' est',vvedite 1):";

float** A = new float*[N];

for(i;i<N;i++)

A[i] = new float[N];

for(i=0;i<N;i++)

for(int k=0;k<N;k++)

{

cout<<"V";

printf("%d",i+1);

cout<<"->V";

        printf("%d",k+1);

        cout<<'=';

        scanf("%f", &A[i][k]);

        if((A[i][k]!=0)&&(A[i][k]!=1))

        {

                cout<<"Vvodite tol'ko 0 ili 1!"<<endl;

                return 0;

        }

        if((i==k)&(A[i][k]==1))

        {

               

                        cout<<"Na glavnoi diagonali doljni bit' nuli!"<<endl;

                        return 0;

       

        }

}

////Откуда и куда?(Начальная и конечная вершина в графе!!)

case2:

cout<<"Vvedite nachalnuiu vershinu: ";

cin>>n;

if(n>N)

{

       cout<<"Net takoi vershini!"<<endl;

       goto case2;

}

if(n==0)

{

       cout<<"Net takoi vershini!"<<endl;

       goto case2;

}

case3:

cout<<"Vvedite konechnuyu vershinu: ";

cin>>c;

if(c>N)

{

       cout<<"Net takoi vershini!"<<endl;

       goto case3;

}

if(c==0)

{

       cout<<"Net takoi vershini!"<<endl;

       goto case3;

}

///Массив,где записывается число шагов

int h=1;

float*B= new float[N];

for(i=0;i<N;i++)

{

       B[i]=0;

}

//В массиве B[N-1] ищем вершины,которые достжимы из начала пути

//т.е за один шаг

for(k=0;k<N;k++)

{

       if(A[n-1][k]==1)

               B[k]=1;

}

//Элементы фронта волны

while(h<50)

{

       for(i=0;i<N;i++)

       {

               for(k=0;k<N;k++)

               {

                       if((B[i]==h)&&(A[i][k]==1)&&(B[k]==0))

                B[k]=h+1;

               }

       }

       h++;

}

B[n-1]=0;

if(B[c-1]!=0)

{

       ///Вывод на экран таблицу

       cout<<"\nTablica stoimosti minimalnogo puti:"<<endl;

       for(i=0;i<N;i++)

       {

               printf("%f ",B[i]);

       }

       //Поиск обратного пути

       cout<<"\n\nOptimal'nii put'(v obratnom poryadke):\n"<<"V";

       printf("%d",c);

       h=c-1;

       int b=B[c-1];

       while(b>0)

       {

               for(i=0;i<N;i++)

                       if((A[i][h]==1)&&(B[i]==B[h]-1))

                       {

                               cout<<"V";

                               printf("%d",i+1);

                               h=i;        

                               b--;

                       }

       }

       cout<<"\n";

}

else

{

       cout<<"\nPuti net!\n";

}

delete A,B;return 0;

}

Примеры выполнения программы:


1.


2.

3.

Использованная литература:


  1. ВлТеория графов». Методические указания по подготовке к контрольным работам по диiиплине "Дискретная математика». Сост.: Н.И. Житникова, Г.И. Федорова, А.К. Галимов. - Уфа, 2005 -37 с.
  2. Курс лекций по дискретной математике Житникова В.П.
  3. ВлСамоучитель С++», Перевод с англ. -3 изд.. - СПб.: БХВ-Петербург, 2005 - 688 с.
  4. ВлДискретная математика для программистов», Ф.А.Новиков.
  5. "Введение в дискретную математику», Яблонский.
  6. "Курс дискретной математики», Неферов, Осипова.
  7. ВлИнформатика» Л.З.Шауцукова.

Размещено на Allbest.ru

Страницы: Назад 1 Вперед