Теория графов проекта: Звездный десант включает в себя различные задачи теории графов, такие как Найти путь, задача о максимальном потоке, задание.
ETC: 15 часов (срок – 5 занятий) 3-4 ученика в команде Пожалуйста, не торопитесь как с качеством, так и с содержанием Доцент и доценты не будут отвечать на вопросы о проекте. |
Шкала: 50 баллов
- 10 точек
- 15 точек
- 10 точек
- 15 точек
«Насилие, неприкрытая сила решили больше вопросов в истории, чем любой другой фактор».
Задача 1: Переместить производство
В 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 балл)
- Нарисуйте таблицу к задаче (5 балловс)
- Решать проблему (3 баллас)
- Нарисуйте задачу в виде графика (5 балловс)
- Решите проблему с помощью excel (3 баллас)
Задача 2: Переместить наши войска
Ваши заводы работают на полной скорости. Совершенно новое снаряжение позволит получить господство над Арахнидами.
У вас неограниченный запас по сравнению с военными нуждами. Если им нужно больше, они предоставят вам больше средств. Чтобы максимально ограничить ваши расходы на топливо, ваши транспортные суда будут брать только самый минимум для совершения путешествия.
Стоимость в килограммах 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 для промежуточных остановок в возможных пунктах назначения.
Пошаговые расходы на топливо | Карак (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 балл)
- Найдите все кратчайшие пути (5 балловс)
- Нарисуйте дерево кратчайших путей (1 балл)
- График с заправкой
- Нарисуйте график, на котором затраты равны израсходованному топливу (2 баллас)
- Найдите все кратчайшие пути (5 балловс)
- Нарисуйте дерево кратчайших путей (1 балл)
Задача 3: Массовая атака
Ваши армии готовы начать последний штурм. Генеральный штаб Федерации обнаружил последние бастионы паукообразных. Вы должны тщательно подготовить свои войска, прежде чем начать атаку одновременно на нескольких фронтах (с лунных баз).
Реакторы Хольцмана оставляют небольшое возмущение в пространстве-времени во время путешествия. После умелых расчетов вы определили максимальное количество судов, которые могут пройти по каждому межзвездному маршруту до ближайших лунных баз.
| Лунный 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). Ваши армии готовы! Пойдем!
- Покажите эту задачу как задачу потока (1 балл)
- Решать проблему (5 баллов)
- Покажите решение графиком (5 балловс)
- Найдите минимальное сечение (5 балловс)
- Какой край разреза может увеличить не более чем глобальный поток? (5 балловс)
Задача 4: Никогда не сдавайся!
Боевые действия идут не так хорошо, как ожидалось. Сопротивление пауков яростно, и потери Федерации исчисляются миллионами солдат и триллионами землян. Ваше производство изо всех сил пытается покрыть убытки, и вам приходится перераспределять свои заказы, чтобы не ставить в невыгодное положение фронт.
Ваши постановки по ряду войск (без различия) следующие:
Гиеди Прайм | Бетельгейзе | Уоллах 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 |
- Решить транспортную проблему
- Представьте задачу в виде двудольного графа с затратами и потоком (5 баллов)
- Найдите массив (2 баллас)
- Решить проблему с Ступенька метод (5 балловс)
- Решить проблему с потоком
- Найдите алгоритм решения задачи (поток минимальных затрат), объясните его и покажите блок-схему (4.5).точкас)
- Подскажите решение(5 балловс)
RU 
FR 
EN 
ES