Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Программа Nakra для нахождения кратчайших расстояний между пунктами сети - файл HELP.txt


Программа Nakra для нахождения кратчайших расстояний между пунктами сети
скачать (227.9 kb.)

Доступные файлы (7):

15
16
HELP.txt21kb.24.04.2003 19:38скачать
igor2
nakra.exe
otvet.doc7kb.30.03.2003 22:01скачать
tigor

HELP.txt



Bведение

1 Методы нахождения кратчайших расстояний

1.1 Табличный метод

1.2 Сетевой метод или метод потенциалов

2 Основные элементы интерфейса программы

3 Пример работы с программой

Заключение

Литература

Приложение А - Исходный текст программы на языке Паскаль для табличного метода

Приложение Б - Исходный текст программы на языке Паскаль для сетевого метода

Приложение В - Пример выполненной с помощью программы задачи


Введение

     Затраты на перевозку грузов находятся в прямопропорциональной зависимости
от  расстояния  перевозки.  Поэтому  перед  нами  (перед  Вами)  стоит  задача
минимизации пробега. План оптимальный по пробегу будет оптимален и по затратам
времени,  производительности  автомобиля,  стоимости и себестоимости перевозки
1 т груза (если на всех участках дороги будут одинаковые условия движения).

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

     Модель  транспортной сети должна быть компактной, но достаточно полной. В
эту  модель  должны  входить  пункты погрузки и выгрузки (т.е. мы считаем, что
изначально  ставится  задача  найти оптимальные маршруты для развоза груза или
пассажиров).

     При   составлении   модели   следует   учитывать  наличие  перекрёстков с
запрежёнными поворотами, а также участки с одностороним движением.

     После  составления  модели  транспортной  сети  замеряют расстояния мужду
смежными вершинами.

     Для  определения  кратчайшего  расстояния  используется  ряд  методов. Мы
рассмотрим два из них (т.е. те методы, которыми владеет данная программа):

     1. табличный;
     2. сетевой (метод потенциалов).

     Для   осуществления   расчётов   необходимо   выполнить  некоторое  число
иттераций,  что  занимает  очень  много  времени при большом количестве пуктов
сети.  Таким  образом, рационально использовать ЭВМ, которая увеличит скорость
обработки данных. Мною была написана программа, которая не только осуществляет
определение  кратчайших  путей,  но и выводит промежуточные расчёты, иммитируя
"ручной" метод решения задачи.


1 Методы нахождения кратчайших расстояний


1.1 Сетевой метод или метод потенциалов

     Кратчайшее расстояние определяется по алгоритму, состоящему из 2-х шагов:

1-й шаг - начальному пункту, от которого определяется кратчайшее расстояние,
          присваивается потенциал равный нулю,

2-й шаг - просматриваются все звенья, начальные пункты которых имеют
          потенциалы, и определяются потенциалы по формуле:
          v(i,j)=v(i)+l(i,j),
          из всех расчитанных потенциалов выбираетеся потенциал, имеющий
          наименьшее значение и он присваивается конечному пункту.

     Второй  шаг  повторяется до тех пор, пока всем пунктам не будет присвоены
потенциалы.   Причём,   при   каждом   повторении   второго   шага   потенциал
присваивается одному пункту. Звено же помечается на рисунке стрелкой.



1.2 Табличный метод нахождения кратчайших расстояний

     Рассмотрим   табличный   метод   решения  задачи  определения  кратчайших
расстояний  точки  (пункта).  В  таблицу размерности n x n, где n - количество
вершин  графа (точек, пунктов), заносятся расстояния l(i,j) от каждой точки до
всех точек (из i-ой в j-ую точку).

     Каждой  точке  P(j)  соответствует  некоторое  число l(j) характеризующее
расстояние от пункта P(1) до пункта P(j).

     При заполнении таблицы руководствуются следующим правилами:

     1. точке P(1), от которой измеряется расстояние соответствует

             l(j)=0, т.е. j=1 и l(1)=0 ;

Соответственно в верхней строке в 1-м столбце ставим 0.

     2. затем, начиная с i=1 рассматриваются клетки i-го столбца с заполненными
расстояниями l(i,j), и если для некоторой клетки l(i) уже определено, а l(i) -
нет, то полагается, что

             l(j)=l(i)+l(i,j)

и   вносится  в  клетки  с  номером  j-го  левого  столбца  и  верхней  строки
таблицы.

     3. если в j-ой строке имеется несколько l(i,j) и при этом соответствующие
l(i) уже найдены, то определяем l(j) как наименьшая сумма значений:

             l(j)=min(l(i)+l(i,j))

     4.  далее  рассматривается  заполненные  клетки таблицы, наиная со строки
Р(1)  до  P(n)  сравнивается  для  них разности l(i) и l(j) с соответствующими
значениями l(i,j); возможна два варианта:

                если l(i)-l(j)<=l(i,j)     (1)
                если l(i)-l(j)>l(i,j)      (2)

     5.  для  тех клеток, где соблюдается условие (1) l(i) и l(j) остаются без
изменения,  а  в  клетках,  где  соблюдается  условие  (2)  записывается новое
значение l'(j), которое равно

               l'(j)=l(i)+l(i,j).

     Этот  процесс  (4-й  и  5-й  пункт) повторяется до тех пор, пока для всех
клеток,  где  l(i)  известно,  не будет выполняться условие (1). В этом случае
l(i)  и  l(j) будут определять кратчайшее расстояние от Р(1) до всех остальных
пунктов.


2 Основные элементы интерфейса программы

     При  загрузке  программы  "NaKRa.exe" открывается её главное окно. На нём
условно можно выделить 5 области:

     1. Панель для настройки ввода данных, расположена сверху окна,

     2. Вертикальный ряд кнопок управления программой, находятся слева,

     3. Логотип (эмблема) программа, в верхнем правом углу,

     4. Полоска  прогресса,  показывающая  процент сделанной работы, размещена
        внизу окна,

     5. Основная  часть  со страницами данных, занимает большую часть рабочего
        окна.

     Панель  для  настройки  ввода  данных  содержит:

     - кнопку,  которая  вызывает  второе  окно  программы для ввода названий
       пунктов,

     - строку для ввода количества пунктов в сети,

     - строку   для  задания  количества  знаков  после  запятой  в  таблице
       результатов,

     - кнопку-переключатель,  с помощью которого программе сообщается есть ли
       пункты с одностороним движением.

     Кнопки управления программой:

     - "Расчёт"  -  кнопка,  которая  нажимается после ввода всех необходимых
       данных, после её нажатия осуществляется поиск кратчайших расстояний,

     - "Печать" - осуществляет вызов окна подготовки к печати,

     - "Запись"  и  "Чтение"  - осуществляют соответственно запись и чтение с
       компьютера исходных данных (матрицы расстояний),

     - "Очистить"   -   стирает   из  таблицы  ввода  все  расстояния,  т.е.
       подготавливает таблицу к следующей задаче,

     - "Помощь" - вызов подсказки по работе с программой,

     - "Выход" - закрытие главного окна и всей программы.

     Полоса прогресса показывают сколько процентов расчёта сделано программой,
активизируется после нажатия кнопки "Расчёт".

Оснавная часть окна состоит из 5 страниц:

     1.  "Ввод  данных" - страница содержит таблицу для ввода расстояний между
пунктами, также две кнопки "х 10" и ": 10", которые соответственно увеличивают
или понижают все числа в таблице на порядок, т.е. перемножают(делят) всё на 10
(эти кнопки сделаны для правки, если человек ошибётся при вводе в размерности,
например, ввел занчения в метрах, а надо в километрах и т.д.);

     2. "Ответ" - страница содержит вычисленные кратчайшие расстояния, которые
появляются  там  после  того, как были введены данные на предыдущей странице и
нажата кнопка "Расчёт";

     3.  "Сетевой  метод"  -  страница  на  которой  автоматически при расчёте
выводится  подробный  расчёт  по  сетевому  методу  для заданого пункта, пункт
задаётся тут же в специальной строке ввода;

     4."Табличный  метод"  -  аналогичная  предыдущей страница, но на на ней -
подробной расчет по табличному методу.

     5."Рейсы"  -  на  странице  представлен текст, в котором в виде маршрутов
записываются   последовательно   пункты   кратчайших   расстояний,   а   также
соответствующие   расстояния;   тут  же  есть  строка  ввода  размерности  для
расстояний (по умолчанию - "км").

     Соответственно 3-я, 4-я, 5-я страницы могут быть скопированы (например, с
помощью "мыши"), в любой редактор под Windows (например, Word), где могут быть
вставлены в какой-либо документ или распечатаны.

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

     -  2 окна для чтения и записи введённых данных, соответствуют стандартным
диалоговым окнам для чтения/записи файлов (т.е. как в Word, MathCAD и др.);

     -  окно  для изменения названий пунктов, содержит таблицу из двух строк -
1-я  строка  номера  пунктов  по  порядку, 2-я - названия пунктов(по умолчанию
эти строки идентичны, т.е. названия изначально обозначаются цифрами), при этом
2-я  строка  таблицы  может  редактироваться,  после  её  изменения  требуется
нажать  на  этом  окне  клавишу  "Принять  изменения", в результате на главной
странице  в таблицах изменятся ячейки с названиями пунктов; также присутствует
кнопка для закрытия этого окна;

     -  окно просмотра данных перед печатью; содержит текст, который выводится
на печать (таблица расстояний между пунктами и таблица кратчайших расстояний с
промежуточными   пунктами),   кнопка   для   настройки  принтеров  (вызывается
стандартное диалоговое окно для выбора принтера в сети), кнопка печати, кнопка
закрытия этого окна;

     - окна сообщения об ошибках, например, если недостаточно данных в таблице
ввода, не найден принтер, не прочитан файл и др.

3 Пример работы с программой

     Допустим,  что нам дана задача подсчитать кратчайшие расстояния. Исходные
данные  -  матрица  расстояний  между  пунктами. Рассмотрим по пунктам порядок
действий для решения задачи этой программой.

     В  примере  у  нас  в  сети 7 пунктов: A,B,C,D,E,F,G. Имеется 10 звеньев,
длина которых приведена в таблице 3.1.


Таблица 3.1 - Длина звеньев сети

   N   Звено     Длина, км
   1   A-B       1.34
   2   A-C       2.32
   3   B-C       2.04
   4   B-D       3.55
   5   B-E       4.55
   6   C-E       2.45
   7   C-F       4.23
   8   D-F       6.1
   9   D-G       5.6
   10  E-G       3.4

     1) В каталоге программы находим и запускаем файл "NaKRa.exe". Открывается
главное окно программы.

     2)  Задаём  в  нужной  строке количество пунктов в сети (т.е. размерность
матрицы).   В  нашем  примере  7  пунктов.  Вводим  в  соответствующей  строке
количество знаков после запятой. Например, у нас числа вводимые имеют точность
до  сотых,  значит  и  для  вывода нам нужна такая точность, вводим число "2".
Допустим,  у  нас  нет  звеньев  сети  с  одностороним движением - переключаем
соответствующую  кнопку  на значок "Нет", тут же в таблице ввода данных должны
заполниться ячейки над главной диагональю (верхняя правая половина таблицы).

     3)  В  нашем  примере  -  номера  пунктов  заданы буквами, а изначально в
таблице  -  в  виде  цифр  от  1 до 7. Чтобы это исправить, нажимаем на кнопку
изменения  названий пунктов (на главном окне - сверху слева), открывается окно
с  таблицей  названий,  редактируем  его  таким  образом,  чтобы  пунктам 1..7
соответствовали  буквы A,B,C,D,E,F,G. Нажимаем на кнопку "Принять изменения" и
закрываем  это  окно,  в результате на главном окне, на странице "Ввод данных"
должны быть эти измененые названия.

     4) На странице "Ввод данных" вводим расстояния между пунктами, т.к. дорог
с  одностороним  движением  у  нас  в  примере  нет  то  заполняем  только под
диагональю(остальные  клетки  над  и  на  диагонали  должны содержать прочерки
"-----"  ). Если между звеньями нет дороги, то в соответствующей ячейке ничего
не  ставиться.  Для  разделения дробной и целой части числа можно использовать
только точку, а не запятую (например: 3.23).

     5)  Условимся,  что  также кроме кратчайших расстояний нам нужно получить
подоробный  расчёт  сетевым  и  табличным  методами соответственно для пунктов
2-го  и  3-го  (В  и  С). Открываем эти страницы ("Сетевой метод" и "Табличный
метод")  и  в  специальной  строке устанавливаем номера пунктов для подробного
расчёта (2 и 3).

     6)  Нажимаем  кнопку  "Расчёт". Если программа выполнила расчёт, тогда на
плоске прогресса внизу окна появиться "100%".

     7) Открыв страницу "Ответ" , мы увидим таблицу кратчайших расстояний с
промежуточными пунктами в скобках. Подробные расчёты - на соответствующих
страницах ("Сетевой метод" и "Табличный метод"), также на странице "Рейсы" -
кратчайшие расстояния с промежуточными пунктами.

     8)  Для  распечатки или сохранения в файл результатов можно скопировать в
любой   Windows   редактор   текст  со  страниц  "Сетевой  метод",  "Табличный
метод","Рейсы",  и  с  окна  "Подготовка к печати" (это окно открывается после
нажатия  на  главном  окне  кнопки  "Печать").  Все  эти результаты показаны в
приложении В.

     9)  Для  дальнейшей  работы  можно сохранить введённые данные (расстояния
между  пунктами,  т.е.  длины  звеньев)  нажав  на клавишу "Запись". Откроется
диалоговое  окно,  в  котором  надо ввести имя файла. Чтобы открыть этот файл,
существует кнопка "Чтение".

     10) Завершить работу с программой - кнопка "Выход".

Заключение
     Программа  позволяет  найти  кратчайшие расстояния для транспортной сети,
При  этом  значительно  экономиться  время,  по  сравнению с "ручным" решением
задачи.  Также  она выдаёт подробные расчёты для двух методов решения задачи -
сетевого и матричного.

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



Приложение С - Пример выполненой задачи с помощью программы


Таблица 4.1 - Длина звеньев сети (вводимые данные)

   N   Звено     Длина, км
   1   A-B       1.34
   2   A-C       2.32
   3   B-C       2.04
   4   B-D       3.55
   5   B-E       4.55
   6   C-E       2.45
   7   C-F       4.23
   8   D-F       6.1
   9   D-G       5.6
   10  E-G       3.4


Пример исполнения программой сетевого метода


Определим кратчайшие расстояния до пункта "B"

V[B,A] = 1.34; V[B,C] = 2.04; V[B,D] = 3.55; V[B,E] = 4.55;
Минимальный потенциал 1.34 в пунте "A"
Ставим стрелку "B" ---> "A"

V[A,C] = 3.66;
Минимальный потенциал 2.04 в пунте "C"
Ставим стрелку "B" ---> "C"

V[C,E] = 4.49; V[C,F] = 6.27;
Минимальный потенциал 3.55 в пунте "D"
Ставим стрелку "B" ---> "D"

V[D,F] = 9.65; V[D,G] = 9.15;
Минимальный потенциал 4.49 в пунте "E"
Ставим стрелку "C" ---> "E"

V[E,G] = 7.89;
Минимальный потенциал 6.27 в пунте "F"
Ставим стрелку "C" ---> "F"

Минимальный потенциал 7.89 в пунте "G"
Ставим стрелку "E" ---> "G"



Пример исполнения программой матричного метода


Расчитаем расстояния до пункта "C"
Присваеваем  l(i) = l(j) = 0  при i = j = C

По условию l(j) = l(i) + l(ij)

l(A) = l(C) + l(C,A) = 0.00 + 2.32 = 2.32
l(E) = l(C) + l(C,E) = 0.00 + 2.45 = 2.45
l(F) = l(C) + l(C,F) = 0.00 + 4.23 = 4.23
l(G) = l(E) + l(E,G) = 2.45 + 3.40 = 5.85


По условию l(j) = min ( l(i) + l(ij) )

l(A) + l(A,B) = 2.32 + 1.34 = 3.66
l(C) + l(C,B) = 0.00 + 2.04 = 2.04
l(E) + l(E,B) = 2.45 + 4.55 = 7.00
l(B) = min = 2.04
l(B) + l(B,D) = 2.04 + 3.55 = 5.59
l(F) + l(F,D) = 4.23 + 6.10 = 10.33
l(G) + l(G,D) = 5.85 + 5.60 = 11.45
l(D) = min = 5.59


Начальные зачения l(i) и l(j)

l(A)=2.32   l(B)=2.04   l(C)=0.00   l(D)=5.59   l(E)=2.45   l(F)=4.23
l(G)=5.85

По условию l(j) - l(i) <= l(ij)

l(A) - l(B) <= l(B,A)     2.32 - 2.04 = 0.28 <= 1.34
l(A) - l(C) <= l(C,A)     2.32 - 0.00 = 2.32 <= 2.32
l(B) - l(A) <= l(A,B)     2.04 - 2.32 = -0.28 <= 1.34
l(B) - l(C) <= l(C,B)     2.04 - 0.00 = 2.04 <= 2.04
l(B) - l(D) <= l(D,B)     2.04 - 5.59 = -3.55 <= 3.55
l(B) - l(E) <= l(E,B)     2.04 - 2.45 = -0.41 <= 4.55
l(C) - l(A) <= l(A,C)     0.00 - 2.32 = -2.32 <= 2.32
l(C) - l(B) <= l(B,C)     0.00 - 2.04 = -2.04 <= 2.04
l(C) - l(E) <= l(E,C)     0.00 - 2.45 = -2.45 <= 2.45
l(C) - l(F) <= l(F,C)     0.00 - 4.23 = -4.23 <= 4.23

l(D)-l(B)>l(B,D)    5.59-2.04=3.55>3.55    l(D)`=l(B)+l(B,D)=2.04+3.55=5.59
l(D) - l(F) <= l(F,D)     5.59 - 4.23 = 1.36 <= 6.10
l(D) - l(G) <= l(G,D)     5.59 - 5.85 = -0.26 <= 5.60
l(E) - l(B) <= l(B,E)     2.45 - 2.04 = 0.41 <= 4.55
l(E) - l(C) <= l(C,E)     2.45 - 0.00 = 2.45 <= 2.45
l(E) - l(G) <= l(G,E)     2.45 - 5.85 = -3.40 <= 3.40
l(F) - l(C) <= l(C,F)     4.23 - 0.00 = 4.23 <= 4.23
l(F) - l(D) <= l(D,F)     4.23 - 5.59 = -1.36 <= 6.10
l(G) - l(D) <= l(D,G)     5.85 - 5.59 = 0.26 <= 5.60

l(G)-l(E)>l(E,G)    5.85-2.45=3.40>3.40    l(G)`=l(E)+l(E,G)=2.45+3.40=5.85
l(D)-l(B)>l(B,D)    5.59-2.04=3.55>3.55    l(D)`=l(B)+l(B,D)=2.04+3.55=5.59

Кратчайшие расстояния до пункта "C"

l(A)=2.32
l(B)=2.04
l(C)=0.00
l(D)=5.59
l(E)=2.45
l(F)=4.23
l(G)=5.85

 i\j                A    B    C    D    E    F    G
 p[i]\p[j]         2     2     0     6     2     4     6

A      2.32     ----     1.34     2.32    ----    ----    ----    ----
B      2.04      1.34    ----     2.04     3.55     4.55    ----    ----
C      0.00      2.32     2.04    ----    ----     2.45     4.23    ----
D      5.59     ----     3.55    ----    ----    ----     6.10     5.60
E      2.45     ----     4.55     2.45    ----    ----    ----     3.40
F      4.23     ----    ----     4.23     6.10    ----    ----    ----
G      5.85     ----    ----    ----     5.60     3.40    ----    ----



Маршруты, образованные программой из кратчайших  расстояний

M (B,A) = B - A ;        L = 1.34 км
M (C,A) = C - A ;        L = 2.32 км
M (D,A) = D - B - A ;        L = 4.89 км
M (E,A) = E - C - A ;        L = 4.77 км
M (F,A) = F - C - A ;        L = 6.55 км
M (G,A) = G - E - C - A ;        L = 8.17 км
M (A,B) = A - B ;        L = 1.34 км
M (C,B) = C - B ;        L = 2.04 км
M (D,B) = D - B ;        L = 3.55 км
M (E,B) = E - C - B ;        L = 4.49 км
M (F,B) = F - C - B ;        L = 6.27 км
M (G,B) = G - E - C - B ;        L = 7.89 км
M (A,C) = A - C ;        L = 2.32 км
M (B,C) = B - C ;        L = 2.04 км
M (D,C) = D - B - C ;        L = 5.59 км
M (E,C) = E - C ;        L = 2.45 км
M (F,C) = F - C ;        L = 4.23 км
M (G,C) = G - E - C ;        L = 5.85 км
M (A,D) = A - B - D ;        L = 4.89 км
M (B,D) = B - D ;        L = 3.55 км
M (C,D) = C - B - D ;        L = 5.59 км
M (E,D) = E - C - B - D ;        L = 8.04 км
M (F,D) = F - D ;        L = 6.10 км
M (G,D) = G - D ;        L = 5.60 км
M (A,E) = A - C - E ;        L = 4.77 км
M (B,E) = B - C - E ;        L = 4.49 км
M (C,E) = C - E ;        L = 2.45 км
M (D,E) = D - B - C - E ;        L = 8.04 км
M (F,E) = F - C - E ;        L = 6.68 км
M (G,E) = G - E ;        L = 3.40 км
M (A,F) = A - C - F ;        L = 6.55 км
M (B,F) = B - C - F ;        L = 6.27 км
M (C,F) = C - F ;        L = 4.23 км
M (D,F) = D - F ;        L = 6.10 км
M (E,F) = E - C - F ;        L = 6.68 км
M (G,F) = G - E - C - F ;        L = 10.08 км
M (A,G) = A - C - E - G ;        L = 8.17 км
M (B,G) = B - C - E - G ;        L = 7.89 км
M (C,G) = C - E - G ;        L = 5.85 км
M (D,G) = D - G ;        L = 5.60 км
M (E,G) = E - G ;        L = 3.40 км
M (F,G) = F - C - E - G ;        L = 10.08 км



Данные, выводимые программой для печати


      Расстояния между пунктами

    из/в        A        B        C        D        E        F        G
       A     ----     1.34     2.32     ----     ----     ----     ----
       B     1.34     ----     2.04     3.55     4.55     ----     ----
       C     2.32     2.04     ----     ----     2.45     4.23     ----
       D     ----     3.55     ----     ----     ----      6.1      5.6
       E     ----     4.55     2.45     ----     ----     ----      3.4
       F     ----     ----     4.23      6.1     ----     ----     ----
       G     ----     ----     ----      5.6      3.4     ----     ----


      Кратчайшие расстояния

    из/в        A        B        C        D        E        F        G

       A     ----     1.34     2.32    4.89     4.77     6.55     8.17

       B     1.34     ----     2.04     3.55    4.49     6.27     7.89

       C     2.32     2.04     ----    5.59      2.45     4.23    5.85

       D    4.89      3.55    5.59      ----    8.04      6.10     5.60

       E    4.77     4.49      2.45    8.04      ----    6.68      3.40

       F    6.55     6.27      4.23     6.10    6.68      ----   10.08

       G    8.17     7.89     5.85      5.60     3.40   10.08      ----

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации