Пархоменко В.И. Транспортная логистика и транспортные средства - файл n1.doc

Пархоменко В.И. Транспортная логистика и транспортные средства
скачать (9166 kb.)
Доступные файлы (1):
n1.doc9166kb.07.11.2012 02:35скачать

n1.doc

1   2   3   4   5   6   7   8   9   ...   13

Таблица 3 – Состояние системы на 1-м этапе


Номер вершины

1

2

3

4

5

6

7

8

Кратчайшее расстояние от начальной вершины, , км

0

3

6

5

М

М

М

М

Номер предшествую-щей вершины

0

1

1

1

0

0

0

0

Группа вершин

1

2

2

2

3

3

3

3



Этап 2.

а) Из вершин 2-й группы выбираем вершину с минимальным кратчайшим расстоянием (dmin) и переводим ее в 1-ю группу. В нашем примере – это вершина 2 с d2 = dmin =3 км.

б) Находим вершины, смежные с вершиной 2. Это вершины 1, 3, 4 и 5. Вершина 1 уже переведена в 1-ю группу. Поэтому ее исключить из дальнейшего рассмотрения. Остаются вершины 3, 4 и 5.

в) Находим для этих вершин кратчайшие расстояния до начальной вершины по формуле
, км (1)
где - наименьшее кратчайшее расстояние от начальной вершины до предшествующей вершины, км;

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

Из этих вершин выбирается вершина с кратчайшим расстоянием и переводится в 1-ю группу. Остальные вершины, смежные с этой вершиной, переводятся во 2-ю группу.

Например, для приведенного на рисунке 10 графа транспортной сети

Для них на этом этапе предшествующей (i-той) вершиной будет вершина 2, имеющая наименьшее кратчайшее расстояние от начальной вершины 1 и должна быть отнесена к 1-й группе согласно определению. Последующими (- тыми) будут вершины 3, 4 и 5.

d3 = 3 + 2 = 5 км – короче, чем d3 по таблице 3. Заменяем им значение в последующей таблице 4,

d4 = 3 + 4 = 7 км – длиннее, чем соответствующее расстояние в таблице 3, не принимаем ее во внимание,

d5 = 3 + 3 = 6 км – новое значение. Внести его в последующую таблицу 4.

Согласно определению эти вершины относим ко 2-й группе.

г) Зафиксируем это состояние системы таблицей 4.

Таблица 4 – Состояние системы на 2-м этапе


Номер вершины

1

2

3

4

5

6

7

8

Кратчайшее расстояние от начальной вершины, , км

0

3

5

5

6

М

М

М

Номер предшествую-щей вершины

0

1

2

1

2

0

0

0

Группа вершин

1

1

2

2

2

3

3

3


Этап 3 и последующие этапы

Повторяем действия этапа 2 в порядке:

- из вершин 2-й группы выбираем вершину с dmin и переводим ее в 1-ю группу;

- находим вершины, смежные с вершиной, имеющей dmin;

- находим расстояние dj от этих вершин до начальной вершины;

- переводим эти вершины во 2-ю группу;

- фиксируем это состояние новой таблицей.

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

Таблица 5 – Окончательное состояние системы


Номер вершины

1

2

3

4

5

6

7

8

Кратчайшее расстояние от начальной вершины, , км

0

3

5

5

6

11

12

13

Номер предшествую-щей вершины

0

1

2

1

2

5

4

3-4

Группа вершин

1

1

1

1

1

1

1

1
1   2   3   4   5   6   7   8   9   ...   13


Учебный материал
© bib.convdocs.org
При копировании укажите ссылку.
обратиться к администрации