Присвоение людей зданиям при соблюдении предпочтений?

17

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

Проблема: Предполагая, что у меня есть N люди, мне нужно назначить их в зданиях M , каждое здание может содержать людей K . Не все люди готовы жить друг с другом, поэтому у меня есть матрица N * N клеток и 1, которая знаменует людей, которые хотят жить друг с другом. Если ячейка содержит 1, это означает, что I и J могут жить вместе. Очевидно, что матрица симметрична вокруг главной диагонали.

Мое решение следующее (псевдокод):

int[] Match(int[] people, int[][] pairs, int numBuildings, int buildingsSize)
{
    int[] freePeople = findFreePeople(people);
    if(freePeople) = 0 
    {
        return people;
    }

    foreach(int person in freePeople)
    {
        for(int buildingIndex=0 to numBuildings)
        {
            if( CheckIfPersonFitsInBuilding(...) )
            {
                int[] tempPeople = people.Copy();
                tempPeople[person] = buildingIndex;
                int[] result = Match(tempPeople,pairs,numBuildings,buildingsSize);
                if(result != null)
                {
                    return result;
                }
            }
        }
    }
    return null;
}

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

  1. Существует ли формальная хорошо известная проблема, подобная этому?
  2. Есть ли лучший алгоритм?

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

задан AK_ 23.06.2012 в 22:32
источник
  • Я не думаю, что здесь действует проблема стабильного брака; это связано с проблемой двудольного сопоставления, и эта проблема не является совпадением. –  templatetypedef 23.06.2012 в 22:50
  • @templatetypedef вы можете объяснить мне, что случилось с именем? это достойная «проблема» - это название учебника ... –  AK_ 23.06.2012 в 22:51
  • Слово «проблема» часто используется в таких названиях, как «Проблема с C ++» или «Проблема с HTML», которые на самом деле не описывают проблему. Я согласен с вами в том, что немного странно запрещать имя, поскольку оно может привести к ложным срабатываниям, подобным этому. –  templatetypedef 23.06.2012 в 22:52
  • ой хорошо ........ –  AK_ 23.06.2012 в 22:52

3 ответа

25

Эта проблема, как известно, NP-жесткая путем сокращения от NP-полной проблемы декомпозиции графа в cliques (проблема с кликой ).

Во-первых, некоторая терминология и обсуждение. A клика на графике представляет собой набор из k различных узлов, так что каждый узел соединен с другим узлом в клике. независимый набор на графике представляет собой набор из k различных узлов, так что ни один из двух узлов не подключен к одному другой. Если вы берете какой-либо граф G, а затем вводите ребра всякий раз, когда ребро отсутствует, и удаляйте все ранее существовавшие ребра, вы получаете граф дополнений исходного графа. Это означает, что проблема нахождения клики в начальном графе эквивалентна нахождению независимого множества в графе дополнений.

Причина, по которой это интересно, заключается в том, что в задаче, которую вы описываете, вам дается график людей, где каждый край указывает, что «эти два человека не могут быть размещены вместе». Следовательно, вы можете думать о проблеме, которую описываете, пытаясь найти способ разбить график на k подграфов, каждый из которых является независимым множеством. Если вы построите дополнение к этому графу, вы получите график всех людей, которые могут быть помещены вместе. В этом случае вы хотите разбить группу на группы k, все клики.

Известно, что следующая задача NP-полная:

  

Учитывая граф и число k, можете ли вы разбить узлы в графе отдельно на k cliques?

Мы можем уменьшить эту проблему до вашей проблемы за полиномиальное время, показывая, что ваша проблема NP-hard. Конструкция проста - с учетом начального графа G и числа k сначала построим дополнение G. Это означает, что если вы можете разбить дополнение на k независимых множеств, то исходный граф G можно разбить на k cliques (потому что дуальности между кликами и независимыми множествами). Теперь возьмите этот новый график и преобразуйте его в набор людей, по одному на узел, где два человека не могут быть помещены в одну комнату друг с другом, если их узлы были связаны в исходном графе. Теперь есть способ распространить этих людей на k домов, если дополнение G можно разбить на k независимых множеств, если G можно разбить на k cliques. Следовательно, известная NP-полная проблема обложки клики может быть сведена к вашей проблеме в полиномиальное время, поэтому ваша проблема NP-hard. Чтобы гарантировать, что любой независимый набор может быть помещен в дом, просто установите максимальную емкость каждой комнаты в n, количество узлов на графике. Это позволяет размещать любой независимый набор в любой комнате.

Поскольку ваша проблема NP-жесткая, не может быть ее решения с полиномиальным временем, если P = NP. Следовательно, как ни лучше, никому не известно, для него нет полиномиального алгоритма времени, и наилучшая рекурсия обратной трассировки может быть оптимальным решением.

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

    
ответ дан templatetypedef 23.06.2012 в 22:45
13

templatetypedef дал очень хорошее доказательство , почему проблема NP-hard и не имеет (известного) решения полиномиального времени .

Однако, как и во многих проблемах NP-hard, это не означает, что вы не можете эффективно решить эту проблему на практике или что вы не можете улучшить решение грубой силы.

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

В книге AIMA есть очень хорошая глава о том, как решить эти типы проблем. Я предлагаю вам прочитать об этом, поскольку там есть много хорошей информации, и это очень доступно, поскольку книга была разработана для уровня бакалавриата. Я дам вам некоторые из больших идей здесь:

Основные вопросы:

  • Какой студент должен быть назначен следующим в вашей рекурсии?
  • В каком порядке следует рассматривать здания для этого ученика?

Вот два эвристики для этого:

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

Для MRV-эвристики разрывайте связи, выбирая ученика, который имеет наибольшие ограничения для других учеников. Идея этих эвристик заключается в том, что вы хотите выбрать пути поиска, которые, скорее всего, будут успешными (LCV). Но, учитывая определенный путь поиска, вы хотите как можно быстрее свернуть количество времени, затрачиваемого на этот путь (MRV).

Кроме того, вместо наивной рекурсии с базовой проверкой вперед вам следует использовать более продвинутый алгоритм поиска, например AC- 3 , который выглядит дальше.

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

    
ответ дан tskuzzy 27.06.2012 в 22:25
4

Хорошим способом решения этих проблем является использование решателя ограничений для конечных доменов.

Например, используя GNU-Prolog:

solve(Out):-
    People = [Jon, Mary, Alice, Smith, Dick, George, Betty, Lucy],
    fd_domain(People, 0, 3),    % people lives in buildings 0 to 3.
    fd_atmost(4, People, 0),    % at most, 4 people may live in building 0
    fd_atmost(3, People, 1),    % at most, 3 people may live in building 1
    fd_atmost(2, People, 2),    % etc.
    fd_atmost(1, People, 3),
    Jon   #\= Mary,             % Jon hates Mary
    Alice #\= Smith,            % etc.
    Betty #\= Lucy,
    Jon   #\= Alice,
    Dick  #\= George,
    fd_labeling(People),        % iterate until an acceptable combination is found.
    People = Out.

:- solve(O), write(O), nl.

С точки зрения сложности это продолжает оставаться NP-полным. Но решатель ограничений может изменить порядок выполнения заданий на шаге маркировки, так что мертвые точки будут найдены раньше, что приведет к меньшему дереву поиска.

    
ответ дан salva 24.06.2012 в 02:41