Нужен простой совет для решения проблемы с графиком

Question

мой коллега предложил мне упражнение с веб-сайта онлайн-судьи, которое, в основном, решает проблему плана эвакуации в маленьком городе.

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

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

проблема заключается в следующем: http://acm.timus.ru/problem.aspx?space=1&num=1237

на тот случай, если его офлайн-код находится в кешированной версии Google: http://webcache.googleusercontent.com/search?q=cache:t2EPCzezs7AJ:acm.timus.ru/problem.aspx%3Fspace%3D1%26num%3D1237+vladimir+kotov+evacuation+problem&cd=1&hl=pt-PT&ct=clnk&gl=pt

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

Любой совет приветствуется, пожалуйста, не думайте, что я спрашиваю ответ, я просто хочу совет в правильном направлении его решения.

Заранее спасибо.

Answer 1

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

С сайта:

Стандартный сценарий, в котором транспортная проблема возникает в том, что отправки единиц продукта через сеть автомобильных дорог, которые соединяют данный набор городов. Каждый город рассматривается как «источник» в что единицы должны быть отправлены из там, или как «раковина», в этих единицах там востребованы Каждый источник имеет учитывая поставку, каждая раковина имеет данный спрос, и каждая магистраль, которая соединяет пара источник-приемник имеет заданный стоимость перевозки за единицу пересылка. Это можно визуализировать в форма сети, как показано на Рисунок TP-1 ниже.

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

Надеюсь, это поможет.

Answer 2

Это выглядит как стандартная проблема минимального расхода . Двудольный граф с ~ 200 вершинами должен легко бегать во времени.

Чтобы создать ограничение вершины (каждый узел может обрабатывать только k человек), вам просто нужно создать второй граф G_1, в который вы добавляете дополнительную вершину u_i для каждого v_i - и чтобы поток v_i в u_i был любым вашим ограничением , в этом случае, k + 1, со стоимостью 0. Таким образом, в основном, если в исходном графе G есть ребро (a, b), то в G_1 будет ребро (u_a, v_b) для каждого из этих кромки. По сути, вы создаете второй слой вершин, который ограничивает поток для каждой вершины k.