Перестановка / Алгоритм для решения головоломки условного заполнения

Question

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

Данная структура реестра организована следующим образом: C, 1B, 2B, 3B, SS, 2B / SS (либо или), 1B / 3B, OF, OF, OF, OF, UT (может быть в любом положении)

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

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

Предполагается, что данные для запуска цикла: 1. Список позиций, которые может оценить игрок, которого он оценивает (тот, который проверяется, может ли он соответствовать) 2. Список игроков, которые в настоящее время включены в список, и позиции, на которые имеет право каждая из них (в настоящее время я храню список списков и использую индекс списка в качестве уникального идентификатора игрока). 3. Список позиций, открытых на данный момент в списке

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

Спасибо за любую помощь, которую может оказать любой. Из-за ограничений я не могу публиковать части кода (некоторые из них унаследованы). Однако он переводится в .NET (на данный момент C #). Если потребуется дополнительная информация, я постараюсь переписать некоторые короткие фрагменты функции для публикации.

Джозеф Г.

РЕД. 07/24/2010 Большое спасибо за ответы. Я действительно изучал использование генетического алгоритма, но в конечном итоге отказался от него, потому что объем работы, который потребовался для определения порядковых результатов, был излишним. Конечная цель теста - определить, существует ли на самом деле сценарий, который дает положительный результат. Нет необходимости определять относительную выгоду каждого рабочего решения.

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

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

((2), (2), (3), (4), (5), (6), (4, 6), (3, 5), (7), (7), (7) ), (7), (7), (2, 3, 4, 5, 6, 7))

Кроме того, существует неупорядоченный массив списков (я буду называть «работниками»), который может занимать только один из слотов, если его массив имеет общий элемент с упорядоченным списком, которому он будет назначен. , После того, как начальные назначения сделаны, если появляется дополнительный сотрудник, мне нужно определить, может ли он заполнить одну из открытых вакансий, и если нет, могут ли текущие сотрудники быть реорганизованы, чтобы разрешить одну из должностей, которую сотрудник МОЖЕТ заполнить быть доступным.

Грубая сила - это то, чего я хотел бы избежать, потому что при этом порядка 40-50 объектов (и скоро будет расти), отдельные определения будут очень дорогими для расчета во время выполнения.

Answer 1

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

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

Например, предположим, что игрок А может играть позиции 1 или 2

A--1
 \
  \
   2

Мы временно назначаем А для 2. ТеперьB отображается и может играть только 2. Направьте график:

A->1
 <
  \
B->2

Мы находим путь B->2->A->1, что означает «назначить B на 2, сместив A на 1».

Существует множество симпатичных теорий для работы с гипотетическими сопоставлениями.Генетические алгоритмы не должны применяться.

---

РЕДАКТИРОВАТЬ: Я должен добавить, что из-за использования BFS он вычисляет наименее разрушительную последовательность переназначений.

Answer 2

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

Рассматривали ли вы использование Генетические алгоритмы для решения этой проблемы?Они очень хороши в решении сложных задач NP и работают на удивление хорошо и для задач с ротацией и графиком.

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

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

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

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

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

Он масштабируется и хорошо работает.