Этот проект требует знания линейное программирование алгоритмы комбинаторной оптимизации, включая Branch & Bound.
«Нам надоело смотреть, как актеры вызывают у нас фальшивые эмоции. Мы устали от пиротехники и спецэффектов. Хотя мир, в котором он живет, в некотором смысле фальшивый, в самом Трумэне нет ничего фальшивого. Никаких сценариев, никаких подсказок. Это не всегда Шекспир, но это настоящее. Это жизнь».
Начало проекта
Реалити-шоу приносят миллиарды долларов в год. Но чтобы изменить ситуацию, вы всегда должны осмелиться на большее. Будучи молодым выпускником знаменитой кино- и аудиовизуальной школы Herr Guerard's Blinded Academy, вы должны пробиться в профессию, причем как можно быстрее.
Вот так у вас появилась идея воплотить «Шоу Трумана» в реальность. В городах-призраках нет недостатка, но ваш бюджет ограничен, и вам нужно наскрести деньги, где вы можете. Чтобы не потерять ни капли своего реалити-шоу, вам предстоит колесить по городу с камерами. Их конструкция сильно варьируется от одной точки к другой. Но, к счастью, вы помните лекции выдающегося профессора Герара о линейных целочисленных задачах (ЦЛП).
"А вершинное покрытие Где поперечный одного график г это набор ПРОТИВ вершин таким образом, что каждое ребро г = (В, Е) инцидентна хотя бы одной вершине ПРОТИВv ∈ S {\ Displaystyle v \ в S} »
Конкретно это сводится к следующему примеру: необходимо контролировать 6 полос движения и необходимо разместить минимальное количество камер с обзором 360°, чтобы каждую полосу видела хотя бы одна камера. Минимальное количество равно 2, и две камеры формируют вершинное покрытие.
Проблема написана так:
С продолжить) стоимость установки камеры вверху в. Иксв стоит 1, если мы построим камеру на вершине в, иначе 0. Для каждого ребра (н,в), мы устанавливаем следующее ограничение Икса+хв меньше 1.
Пересечения и прямые углы — вершины, дорога между двумя вершинами — ребро. Круговой перекресток считается одной вершиной. Только дороги обочины (не парковки, не улицы с односторонним движением и немаркированные дороги). Стоимость камер равна количеству штрихов линий разграничения соседних дорог (до следующих вершин).
Рейтинг
- Построить соответствующий граф (2 балла)
- Сделать НПИ (3 балла)
- Найти основное решение (5 точек)
- Развертывание алгоритма Branch&Bound (10 точек)
Вам разрешено использовать любой симплекс для решения LP.
RU 
FR 
EN 
ES