Я не теоретик информатики, но думаю, что проблема реального мира здесь.

Проблема

У моей компании есть несколько подразделений по всей стране.

Мы предложили сотрудникам возможность работать на другом блоке. Но есть условие: общее количество работников на единицу не может измениться.

Это означает: мы позволим сотруднику покинуть свое подразделение, если кто-то захочет его занять.

Пример (вымышленный) запроса данных:

Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

Выше, построено: Визуализация вышеуказанных данных

Посмотрите, как мы должны выбирать между красным, синим или черным вариантами?

Реальная проблема немного сложнее, потому что у нас есть 27 единиц и 751 запрос. Пожалуйста, посмотрите на визуализацию

Цель

Собрав все запросы, как удовлетворить большинство из них?

Теория (?) Приложения

Имея граф , пусть каждая единица будет вершиной а запрос - направленным ребром , успешный обмен примет форму направленного cyle. $G(V, E)$ $V$ $E$

Каждый цикл должен использовать только один раз ( работник не может покинуть свое подразделение дважды ), но может посещать несколько раз ( в подразделении может быть много работников, желающих уйти ). $E$ $V$

Вопрос

Если эта проблема выражается как

«Как найти циклы, которые вместе содержат наибольшее количество не общих ребер в ориентированном графе»?

Удовлетворим ли мы большинство заказчиков?

Что правда, есть алгоритм, чтобы найти этот оптимальный набор циклов?

Этот подход Гредди решит проблему?

Найдите самый большой направленный цикл на ; $G$
Удалить его края от ; $G$
Повторяйте 1, пока не будет направленного цикла на ; $G$

Можете ли вы мне помочь?

Знаете ли вы другой способ описать исходную проблему (осчастливить большинство заказчиков)?

Изменить : изменил отдел на единицу, чтобы лучше описать проблему.

ds.algorithms graph-algorithms application-of-theory motobói
источник

3

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

Цуёси Ито

3

@TsuyoshiIto: Как я понимаю из описания, условие состоит в том, что в каждой вершине степень должна быть равна степени. Итак, вершина-дизъюнктность не нужна.

Ёсио Окамото

7

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

Ёсио Окамото

3

В этом посте обсуждается обобщение вашей проблемы okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html (представьте, что у каждого человека есть один предмет для торговли, а именно его место работы).

Раду GRIGore

4

Удивительный вопрос, заставляет нас чувствовать, что то, что мы делаем, действительно может быть использовано в реальной жизни :).

Гопи

9

Хорошо, я прочитал код TradeMaximizer и считаю, что он решает следующую, более общую проблему.

ПРОБЛЕМА: Данный ориентированный граф, чьи дуги имеют стоимость. Найдите набор циклов с непересекающимися вершинами, который максимизирует количество покрытых вершин в первую очередь и сводит к минимуму общую стоимость вторых.

Чтобы решить вопрос, заданный здесь, сделайте вершины сотрудниками и нарисуйте дугу удельной стоимости, когда хотел бы работу . Обратите внимание, что сотрудники теперь являются вершинами, а не ребрами. Приятно то, что сотрудник может сказать: «Я действительно хочу работу , но работа у тоже подойдет». $x\to y$ $x$ $y$ $y$ $z$

Решение:

Постройте двудольный граф следующим образом: Для каждой вершины в исходном графе левую вершину , правую вершину и дугу от , стоимость которой огромна (больше, чем сумма затрат в исходном графе). Для каждой дуги в исходном графе дугу в двудольном графе. $x$ $x_L$ $x_R$ $x_L\to x_R$ $x\to y$ $x_L\to y_R$
Найти минимальную стоимость идеального соответствия в двудольном графе.

Существует также некоторая предварительная обработка исходного графа: Удалите дуги между SCC, затем обработайте все SCC размером как указано выше. $>1$

(Фактически, TradeMaximizer перебирает все оптимальные решения в соответствии с двумя вышеупомянутыми критериями, чтобы эвристически оптимизировать другие вещи, такие как длина самого большого цикла. Большие циклы увеличивают вероятность того, что «сделка» не состоится, потому что один человек меняет свое мнение.)

PS: автор, Крис Окасаки, подтвердил, что это то, что делает код, еще в посте в блоге .

Раду ГРИГОРЕ
источник

Мне удалось найти решение исходной проблемы с помощью TradeMaximizer. Я опубликую пост завтра.

motobói

@ motobói, но все, что тебе нужно сделать, это то, что я написал во втором абзаце ...

Раду ГРИГОР

Я нашел это объяснение об алгоритме: boardgamegeek.com/wiki/page/TradeMaximizer

motobói

Не могли бы вы объяснить или указать на объяснение того, почему необходимо удалять дуги между компонентами с сильным соединением?

motobói

@ motobói, это оптимизация (для среднего случая). Шаги (1) и (2) должны быть достаточными.

Раду GRIGore

22

Это стандартная проблема обращения с минимальными затратами. Дайте каждому направленному ребру емкость и стоимость . Тогда допустимая циркуляция является суммой (т. Е. Объединением) непересекающихся по ребру направленных циклов, а стоимость циркуляции является отрицанием числа ребер. $1$ $-1$

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

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

Здесь стоимость цикла - это сумма затрат на его ребра. Циклы с отрицательной стоимостью можно найти, используя алгоритм кратчайшего пути Беллмана-Форда за . Каждая итерация снижает стоимость текущего тиража как минимум на 1. Начальный (пустой) тираж имеет стоимость , а финальный тираж - как минимум . Таким образом, алгоритм заканчивается после не более чем итераций, поэтому его общее время выполнения составляет не более . $O(VE)$ $0$ $-E$ $E$ $O(VE^2)$

Это не самый быстрый из известных алгоритмов.

Jeffε
источник

думаю, что это работает до тех пор, пока человек не хочет работать более чем в одной «единице», верно? используя формулировку оригинального вопроса. но если люди хотят работать в более чем одном подразделении, подозреваю, что эта абстракция разрушается. ОП сформулировал проблему с точки зрения только одной единицы, но это кажется мне довольно искусственно ограничивающим. [какой человек имеет только одно предпочтение ...?]

vzn

1

Что такое «человек» и «единица»? Это вопрос о графиках.

Джефф

Я озадачен: не является ли мой пример контр-примером для этого алгоритма? После выбора C циклы C_1 и C_2 больше не являются циклами (потому что каждый цикл имеет один обратный фронт); C не будет использоваться снова, потому что он имеет положительную стоимость после изменения его краев, и нет новых введенных циклов. Мы говорим об одной и той же проблеме? Хотелось бы иметь математическую формулировку проблемы.

Февраль

3

После выбора (и реверса) удаление ребер совместно используемых и оставляет один длинный направленный цикл . Выбор (и реверсирование) дает тот же результат, что и выбор и с самого начала. (Короче говоря, ) Также: мой ответ - математическая постановка задачи!

C

$C$

C

$C$

C_{1}

$C_1$

C_{2}

$C_2$

C^{'}

$C'$

C^{'}

$C'$

C_{1}

$C_1$

C_{2}

$C_2$

C^{'} = C_{1} + C_{2} - C

$C' = C_1 + C_2 - C$

Джефф

по-видимому, «подразделение» - это что-то вроде «отдела», и пользователи записывают запросы на переводы между отделами [не совсем конкретные должности в отделах]? Диаграмма FIB, кажется, имеет единицы в виде вершин и ребер в виде запросов empl между единицами. FiB-- "хотел бы иметь математическую формулировку проблемы" ... это действительно зависит от вас, чтобы предоставить точную формулировку .. вы, кажется, на полпути ...

vzn

4

Этот жадный подход не всегда дает лучшее решение.

Рассмотрим цикл с ребрами и двух циклов непересекающихся и каждый из которых имеет ребер и совместное использование одного ребра с . $C$ $n$ $\{(v_1, v_2),\dots,(v_n,v_1)\}$ $C_1$ $C_2$ $n-1$ $C$

Если вы сначала используете самый большой цикл , вы сможете порадовать сотрудников. Тогда циклы и каждый теряют одно ребро и больше не являются циклами. $C$ $n$ $C_1$ $C_2$

Но если вы выберете и , вы сможете порадовать сотрудников. $C_1$ $C_2$ $2(n-1)=2n-2$

В сторону: вместо добавления двух циклов в приведенном выше примере, вы можете добавить циклов, что делает жадное решение еще хуже. $\lfloor\frac{n}{2}\rfloor$

выдумка
источник

-3

Вероятно, существует способ / формулировка теории графов, чтобы решить эту проблему, но эта проблема для меня больше напоминает проблему перестановок, когда некоторые из всех перестановок отклоняются, а другие являются действительными. Перестановки - это сотрудники, а должности - это «должности» в компании. перестановка отклоняется, если она не соответствует требованиям «person [x] хочет положение [y]». различие в единицах / границах / границах организации, по-видимому, несколько избыточно для решения в этом случае.

этот тип задачи перестановки с ограничениями может быть легко преобразован в экземпляр задачи SAT (выполнимости). присваивания логических переменных представляют сотрудников, а условия ограничений представляют ограничения «person [x] want position [y]». Есть несколько классических примеров этого, один из которых обычно называют проблемой «обеденного стола», когда у вас есть сидячие места и гости, и не все гости хотят сидеть рядом друг с другом (или очень похоже, что некоторые гости хотят сидеть рядом с другими гостями).

и, конечно, существуют сложные SAT-решатели для довольно больших случаев, включающие примерно до сотни переменных и предложений, на ПК, и, если проблема не «сложная», тысячами.

см., например, [1] для профессиональной справки и [2] для классного упражнения. Существует также некоторое структурное сходство с так называемыми «проблемами с голубями», которые хорошо изучены в кругах SAT, где голуби назначены для голубей, и у вас больше или меньше отверстий, чем у голубей. однако в этом случае голуби обычно считаются взаимозаменяемыми. Другими словами, проблема с обеденным столом подобна проблеме с голубями с более жесткими ограничениями, и у гостей / голубей есть требуемые предпочтения.

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

[1] алгоритм обеденного стола, крато

[2] CS402 princeton HW SAT

[3] Проблема удовлетворенности, википедия

ВЗН
источник

Я попробовал перестановку, используя trademaximizer. Установить сотрудника в качестве пользователя , желающего торговать его блок X для блока Y . Но программное обеспечение не позволит нескольким пользователям торговать одним и тем же предметом (его единицей). Каждый предмет должен быть уникальным. Чтобы приспособиться к этому, мне бы пришлось, скажем, [(Джонс) хочет обменять Юнит-С-Джеймс на Юнит-D-Лору или Юнит-D-Серхио или Юнит-D-Мэри]

motobói

Как найти циклы, которые вместе содержат наибольшее количество не общих ребер в ориентированном графе?

Проблема

Цель

Теория (?) Приложения

Вопрос

Можете ли вы мне помочь?

Ответы: