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

После ввода данных, выводится матрица инцедентности. Которая указывается в массиве.

После указания начальной точки пути и конечной, начинается выполнения цикла на поиск минимального расстояния от начального  до конечного графа. И затем выводит сумму пути.

 

 

3.7. Обоснование выбора средств разработки

 

Для разработки программы будет использоваться язык С#.

С# или «си шарп» - это язык программирования, который является объектно-ориентированным и применяется для разработки модулей и компонентов для Windows NET платформы.

На  данный момент язык программирования C# набирает очень большой темп, и нет столь простого и многофункционального языка, как Си шарп. В нем собраны все достоинства разных языков. Быстродействие выполнения приближается к языку Assembler.

Язык  Си шарп имеет 300 000 библиотек разных функций, которые работают с максимальным быстродействием.

C# относится к семье языков с  C-подобным синтаксисом, из них  его синтаксис наиболее близок к C++ и Java. Язык имеет статическую типизацию, поддерживает полиморфизм, перегрузку операторов (в том числе операторов явного и неявного приведения типа), делегаты, атрибуты, события, свойства, обобщённые типы и методы, итераторы, анонимные функции с поддержкой замыканий, LINQ, исключения, комментарии в формате XML.

Переняв многое от своих предшественников —  языков C++, Java, Delphi, Модула и Smalltalk — С#, опираясь на практику их использования, исключает некоторые модели, зарекомендовавшие себя как проблематичные при разработке программных систем, например, C# не поддерживает множественное наследование классов (в отличие от C++).

C# разрабатывался как язык программирования  прикладного уровня для CLR и,  как таковой, зависит, прежде  всего, от возможностей самой  CLR. Это касается, прежде всего, системы типов C#, которая отражает BCL. Присутствие или отсутствие тех или иных выразительных особенностей языка диктуется тем, может ли конкретная языковая особенность быть транслирована в соответствующие конструкции CLR. Так, с развитием CLR от версии 1.1 к 2.0 значительно обогатился и сам C#; подобного взаимодействия следует ожидать и в дальнейшем. (Однако эта закономерность была нарушена с выходом C# 3.0, представляющим собой расширения языка, не опирающиеся на расширения платформы .NET.) CLR предоставляет C#, как и всем другим .NET-ориентированным языкам, многие возможности, которых лишены «классические» языки программирования. Например, сборка мусора не реализована в самом C#, а производится CLR для программ, написанных на C# точно так же, как это делается для программ на VB.NET, J# и др.

3.8. Описание программных модулей.

Программа решения задачи написанная на  языке программирования C++ содержит в себе 3 вида переменных, цикл для строк и столбцов, команды для вывода результатов на экран.

Int – тип переменной, которая может принимать только целые значения.

Типы данных word и char

For -  этот цикл действует различным образом в разных частях кода. Изначально инициализируя часть цикла. Программа вычисляет условие. Заданное условием if. Если это значение истинно, программа выполняет тело цикла. Высчитывает и выводит ответ.

 

3.9. Тестирование  программы.

Для тестирования программы была использована задача из 3.2. Результаты программного решения  совпали с результатами самостоятельного решения, значит программа корректна. Скриншоты решения тестовой задачи отображены в Приложении В.

 

10. Инструкция пользователю.

Данный программный продукт является способом решения задач линейного программирования симплекс – метода.  Программа не предполагает установки и работает при запуске .exe файла. Программа работает в операционной системе Windows, для запуска требуется двойной клик по исполняемому файлу. Откроется окно командной строки, в котором осуществляется диалог с программой. Ввод данных, происходит по средствам клавиатуры.

                                       Заключение

В данном курсовом проекте была рассмотрена проблема решения задач методом динамического программирования,нахождения кратчайшего пути. Существует три алгоритма решения такого типа задач: алгоритм Дейкстры, алгорит Флойда, переборные алгоритмы.

 Более подробно рассмотрен первый и написан программный продукт на его основе. В качестве языка программирования был выбран С++. Перед написанием программы была самостоятельно решена  тестовая задача. Программа была разработана и протестирована.

  Данная программа прекрасно войдет в учебный процесс, преподаватели посредством ее смогут проверять решенные задачи учеников, сокращая временные рамки работы. Она может использоваться и в обратно пропорциональном плане, учениками, для проверки соответствия решений.

Таким образом, поставленные задачи выполнены и цель курсового проекта достигнута.

Список  литературы

1.Агальцов В.П., Валдайская И.В. Математические методы в программировании: Учебник. – М.: ИД «ФОРУМ»: ИНФРА-М, 2006. – 224 с.: ил. – (Профессиональное образование).

2.Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования: Учебное пособие. - М.: Форум: Инфра-М, 2004

3.Орлов В.В. Технологии разработки программных продуктов. - СПб.: Питер, 2003. - 437 с.

4.Партыка Т.Л., Попов И.И. Математические методы: Учебник. – М.: ФОРУМ: ИНФРА-М, 2005. – 464с.: ил. – ( Профессиональное образование)

 

 

 

 

Приложение А

 

Глоссарий понятий

 

 

 

Приложение Б

 

Текст программы

 

#include "stdafx.h"

#include<iostream>

#include<string.h>

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define word unsigned int

using namespace std;

 

int i, j, n, p, xn, xk;

int flag[11];

word c[11][11], l[11];

char s[80], path[80][11];

 

int min(int n)

{

    int i, result;

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

        if(!(flag[i])) result=i;

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

        if((l[result]>l[i])&&(!flag[i])) result=i;

    return result;

}

 

word minim(word x, word y)

{

    if(x<y) return x;

    return y;

}

 

void main()

{

    cout<<"Napishite chislo tochek:";

    cin>>n;

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

        for(j=0;j<n;j++) c[i][j]=0;

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

        for(j=i+1;j<n;j++)

        {

            cout<<"  Zadaite dlinu reber: x"<<i+1<<" do x"<<j+1<<": ";

            cin>>c[i][j];

        }

    cout<<"   ";

    for(i=0;i<n;i++) cout<<"    X"<<i+1;

    cout<<endl<<endl;

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

    {

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

        for(j=0;j<n;j++)

        {

            printf("%6d",c[i][j]);

            c[j][i]=c[i][j];

        }

        printf("\n\n");

    }

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

        for(j=0;j<n;j++)

            if(c[i][j]==0) c[i][j]=65535; //nekonecno

    cout<<"  Zadaite nachalnuy tochku: ";

    cin>>xn;

    cout<<" Zadaite konechnuy tochku: ";

    cin>>xk;

    xk--;

    xn--;

    if(xn==xk)

    {

        cout<<"Nachalnaya & Konechnaya tochki sovpadaut"<<endl;

        getch();

        return;

    }

 

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

    {

        flag[i]=0;

        l[i]=65535;

    }

    l[xn]=0;

    flag[xn]=1;

    p=xn;

    itoa(xn+1,s,10);

        for(i=1;i<=n;i++)

        {

            strcpy(path[i],"X");

            strcat(path[i],s);

        }

        do

        {

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

                if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))

                {

                    if(l[i]>l[p]+c[p][i])

                    {

                        itoa(i+1,s,10);

                        strcpy(path[i+1],path[p+1]);

                        strcat(path[i+1],"-X");

                        strcat(path[i+1],s);

                    }

                    l[i]=minim(l[i],l[p]+c[p][i]);

                }

            p=min(n);

            flag[p]=1;

        }

        while(p!=xk);

    if(l[p]!=65535)

    {

        cout<<"Put: "<<path[p+1]<<endl;

        cout<<"Dlina puti: "<<l[p]<<endl;

    }

    else

        cout<<"Puti net!"<<endl;

    getch();

}

 

Приложение В

 

Видовые экраны работы программы

 

 

Рис. В1- начало работы программы.

 

Рис.В2- Ввод данных.

Рис.В3.- Получение матрицы.

Рис. В4-  Результат решения.

 

Приложение Г

 

Алгоритм  решения задачи