Теория графов проекта: Звездный десант включает в себя различные задачи теории графов, такие как Найти путь, задача о максимальном потоке, задание.

ETC: 15 часов (срок – 5 занятий)

3-4 ученика в команде

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

Доцент и доценты не будут отвечать на вопросы о проекте.

Шкала: 50 баллов

  1. 10 точек
  2. 15 точек
  3. 10 точек
  4. 15 точек

проект теория графов транспорт максимальный поток ступенька

Теория графа проекта: Теория графа проекта Starship Troopers

«Насилие, неприкрытая сила решили больше вопросов в истории, чем любой другой фактор».

Задача 1: Переместить производство

Теория графа проекта: Теория графа проекта Starship Troopers

В 23 веке Земля стала космической цивилизацией. При колонизации новых планет люди столкнулись с инсектоидным видом, известным как паукообразные, родиной которых является далекий мир Клендату. Жуки кажутся не более чем дикими, безжалостными машинами для убийства, хотя есть предположения, что они были спровоцированы вторжением людей в их среду обитания.

У богатого коммивояжера вам не нужно нести нашу военную службу за Федерацию. Наше богатство происходит от различных фабрик, которые производят предметы первой необходимости и вещи для армий. С тех пор как Клендату пал, война усилилась и распространилась на всю галактику. Наши заводы не оптимизированы; они производят всевозможные вещи, когда доставка материала на разные промышленные планеты стоит дорого. Вы должны переосмыслить, как производить в зависимости от материальных затрат и материалов, необходимых для создания вещей (используйте только материалы, основанные на планете).

Извлечь стоимость материалов по планетам:

Планета | материал

дилитий

Дюраниум

ElementZero

тритан

Гиеди Прайм

1

1

1

0.1

Бетельгейзе

0.5

0.9

1.2

0.3

Уоллах IX

0.9

0.7

1.1

0.3

Лампады

1.2

0.1

1

0.2

Икс

0.7

2

0.3

0.1

 

Затраты в Мг каждого материала на постройку:

вещи | материал

дилитий

Дюраниум

ElementZero

тритан

Дройдека

1

0.6

0.8

1.2

Стервятник Истребитель

0.9

1

0.1

1.3

Т-дроид

0.7

1.3

1

0.5

град дроид

0.5

0.3

0.1

1

MagnaGuards

0.9

0.9

0.9

1.1

 

  1. Найдите цену каждого товара для каждой планеты (1 балл)
  2. Нарисуйте таблицу к задаче (5 балловс)
  3. Решать проблему (3 баллас)
  4. Нарисуйте задачу в виде графика (5 балловс)
  5. Решите проблему с помощью excel (3 баллас)

Задача 2: Переместить наши войска

Теория графа проекта: Теория графа проекта Starship Troopers

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

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

Стоимость в килограммах Unobtainium ваших реакторов Holtzmann варьируется в зависимости от расстояния и гравитации планет.

Стоимость взлета

Гиеди Прайм (1)

Бетельгейзе (2)

Уоллах IX (3)

Торшеры (4)

х (5)

3.5e2

1.25e2

1.75e2

2.12e2

0.8e2

Стоимость посадки

Карак (6)

Клендату (7)

М6-117 (8)

Талларн (9)

Дайсон (10)

Гайя (11)

Оникс (12)

Плоский мир (13)

Хтраэ (14)

254

89

211

370

50

78

23

89

147

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

Теория графа проекта: Теория графа проекта Starship Troopers

Пошаговые расходы на топливо

Карак (6)

Клендату (7)

М6-117 (8)

Талларн (9)

Дайсон (10)

Гайя (11)

Оникс (12)

Плоский мир (13)

Хтраэ (14)

 

200

100

240

500

200

80

70

20

140

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

К | из

1

2

3

4

5

6

7

8

9

10

11

12

13

14

6

58

67

80

24

31

102

7

41

21

50

24

45

10

110

90

90

8

90

50

10

45

100

70

9

31

10

46

35

15

28

10

102

110

46

24

17

11

90

35

24

7

12

100

15

17

7

36

13

28

10

14

90

70

36

10

Например, случай (i,j) означает, что вы уезжаете с планеты i на планету j. Стоимость проезда из j в i одинакова.

  1. График без дозаправки
    1. Нарисуйте график, на котором затраты равны израсходованному топливу (1 балл)
    2. Найдите все кратчайшие пути (5 балловс)
    3. Нарисуйте дерево кратчайших путей (1 балл)
  2. График с заправкой
    1. Нарисуйте график, на котором затраты равны израсходованному топливу (2 баллас)
    2. Найдите все кратчайшие пути (5 балловс)
    3. Нарисуйте дерево кратчайших путей (1 балл)

Задача 3: Массовая атака

Теория графа проекта: Теория графа проекта Starship Troopers

Ваши армии готовы начать последний штурм. Генеральный штаб Федерации обнаружил последние бастионы паукообразных. Вы должны тщательно подготовить свои войска, прежде чем начать атаку одновременно на нескольких фронтах (с лунных баз).

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

 

Лунный 1

Лунный 2

Лунный 3

Лунный 4

Лунный 5

Лунный 6

Лунный 7

Лунный 8

Лунный 9

10

5

7

11

10

12

6

4

5

13

8

14

4

9

Лунный 1

2

7

8

Лунный 2

1

8

7

Лунный 3

4

3

5

5

2

Лунный 4

5

3

7

3

Лунный 5

4

1

10

Случай (i,j) означает, что вы путешествуете из i в j.

Запаситесь максимальным количеством войск с Луны 5 до Луны 9 (5, 6, 7, 8, 9). Ваши армии готовы! Пойдем!

Теория графа проекта: Теория графа проекта Starship Troopers
  1. Покажите эту задачу как задачу потока (1 балл)
  2. Решать проблему (5 баллов)
  3. Покажите решение графиком (5 балловс)
  4. Найдите минимальное сечение (5 балловс)
  5. Какой край разреза может увеличить не более чем глобальный поток? (5 балловс)

Задача 4: Никогда не сдавайся!

Теория графа проекта: Теория графа проекта Starship Troopers

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

Ваши постановки по ряду войск (без различия) следующие:

Гиеди Прайм

Бетельгейзе

Уоллах IX

Лампады

Икс

600

400

500

450

350

А запросы на подкрепление следующие:

Фронт 1

Лоб 2

Лоб 3

Лоб 4

Фронт 5

Лоб 6

Лоб 7

500

300

400

250

250

600

300

В финансовом отношении вы находитесь на краю пропасти. Для того, чтобы иметь возможность удерживать фронт на месте как можно дольше, вы должны отправить доступное подкрепление, потратив наименьшее количество средств (часть транспорта финансируется Федерацией, остатки — из вашего кармана).

К | Из

Гиеди Прайм

Бетельгейзе

Уоллах IX

Лампады

Икс

Фронт 1

1

3

5

4

5

Лоб 2

4

6

2

6

1

Лоб 3

5

1

5

3

2

Лоб 4

2

6

3

4

7

Фронт 5

3

4

1

6

7

Лоб 6

5

2

6

5

1

Лоб 7

3

5

4

2

3

Это не так просто. Конечно, вы не можете посылать бесконечные войска из любого места на любой фронт. Маршруты также определяются ограниченным потоком, как показано в следующей таблице:

К | Из

Гиеди Прайм

Бетельгейзе

Уоллах IX

Лампады

Икс

Фронт 1

200

105

135

95

65

Лоб 2

100

200

30

55

80

Лоб 3

125

25

50

75

90

Лоб 4

400

25

80

90

105

Фронт 5

95

120

70

50

110

Лоб 6

60

75

65

140

40

Лоб 7

80

55

140

100

200

  1. Решить транспортную проблему
    1. Представьте задачу в виде двудольного графа с затратами и потоком (5 баллов)
    2. Найдите массив (2 баллас)
    3. Решить проблему с Ступенька метод (5 балловс)
  2. Решить проблему с потоком
    1. Найдите алгоритм решения задачи (поток минимальных затрат), объясните его и покажите блок-схему (4.5).точкас)
    2. Подскажите решение(5 балловс)
Делиться
ru_RURU