Проблема с перчаткой - Glove problem

В исследование операций, то проблема с перчатками^[1] (также известный как проблема с презервативом^[2]) является проблема оптимизации Используется в качестве примера, что самые дешевые капитальные затраты часто приводят к резкому увеличению рабочего времени, но что самое короткое рабочее время не обязательно должно определяться самыми дорогими капитальными затратами.^[3]

Постановка задачи

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

Данный M врачи и N пациенты, минимальное количество перчаток грамм(M, N), необходимые для всех врачей для обследования всех пациентов:

• грамм(M, N) = M + N - 2, если оба M, N ≥ 2
• грамм(M, 1) = M
• грамм(1, N) = N
• грамм(1, 1) = 1

Подробности

Наивным подходом было бы оценивать количество перчаток как просто грамм(M, N) = MN. Но это число можно значительно уменьшить, используя тот факт, что каждая перчатка имеет две стороны, и нет необходимости использовать обе стороны одновременно.

Лучшее решение можно найти, назначив каждому человеку его или ее собственную перчатку, которая будет использоваться на протяжении всей операции. Каждое попарное столкновение защищается двойным слоем. Обратите внимание, что внешняя поверхность перчаток врача встречается только с внутренней поверхностью перчаток пациента. Это дает ответ M + N перчатки, что значительно ниже, чемMN.

В сковорода с этой схемой K · Макс(M, N), куда K - продолжительность одной попарной встречи. Обратите внимание, что это точно такое же время приготовления, если бы использовались перчатки MN. Очевидно, что в этом случае увеличение капитальных затрат не привело к сокращению времени работы.

Номер грамм(M, N) можно дополнительно уточнить, допустив асимметрию в начальном распределении перчаток. Лучшую схему дают:

• Доктор №1 носит N перчатки, наложенные одна на другую. Он посещает N пациенты по очереди, оставляя каждому по крайнюю перчатку.
• Врачи №2 - (M - 1) надевайте по одной перчатке на каждую и соблюдайте двухслойный протокол при каждом взаимодействии, как описано выше.
• Врач # M не носит своего, но посещает все N пациенты, собирая свои перчатки по очереди и постепенно превращая их в многослойную перчатку. Обратите внимание, что в своей первой встрече он использует только нетронутую внутреннюю часть перчатки Пациента №1, так что это все еще безопасно.

В этой схеме используется (1 ·N) + ((M − 1 − 1) · 1) + (1 · 0) = M + N - 2 перчатки. Это число не может быть уменьшено.

Продолжительность изготовления определяется следующим образом:

• N серийные взаимодействия, чтобы посадить перчатки.
• Максимум(M − 2, N) параллельные взаимодействия для промежуточной стадии.
• N серийные взаимодействия для сбора перчаток.

Макспан: K · (2N + макс (M − 2, N)).

Ясно, что минимум грамм(M, N) значительно увеличивает время изготовления, иногда в 3 раза. Обратите внимание, что выгода от количества перчаток составляет всего 2 единицы.

Одно или другое решение может быть предпочтительным в зависимости от относительной стоимости перчатки с учетом более длительного времени эксплуатации. Теоретически промежуточное решение с (M + N - 1) также должно быть возможным решением, но для этого требуются такие узкие окна на M, N а стоимостные параметры должны быть оптимальными, что часто игнорируется.

Прочие факторы

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

Также, медицинские перчатки обратимы; поэтому существует лучшее решение, которое использует

${\displaystyle \min \left(\lceil M/2\rceil +N,M+\lceil N/2\rceil \right)}$

перчатки, где менее многочисленная группа экипирована перчаткой каждая, более многочисленная - парами. Первый из каждой пары использует чистый интерфейс, второй - перчатку наоборот.^{[оригинальное исследование? ]}

Рекомендации

1. Вайсштейн, Эрик В. "Проблема с перчатками". MathWorld.
2. Варди, И. Проблема презерватива. Гл. 10 дюйм Вычислительные развлечения в системе Mathematica. Редвуд-Сити, Калифорния: Аддисон-Уэсли, стр. 203–222, 1991. ISBN  0-201-52989-0.
3. Хайнал, А.; Ловас, Л. (1978). «Алгоритм предотвращения распространения некоторых заболеваний с минимальными затратами». В Дж. К. Ленстра; А. Х. Г. Риннуй Кан; П. ван Эмде Боас (ред.). Интерфейсы между компьютерными науками и исследованиями операций. Mathematisch Centrum.