стабильное соответствие

Question

Я читаю книгу по алгоритмам в свое время. Вот на этот вопрос у меня есть свой ответ, но я не совсем уверен. Каково твое мнение? Спасибо!

Вопрос: Есть две телекомпании, пусть, как предполагают A и B, каждая из которых планирует расписание телевизионных программ в n временных интервалов дня. Каждый из них помещает свои n программ в эти слоты. Хотя у каждой программы есть ставки, основанные на популярности в прошлом году, и эти показатели различны между собой. Компания выигрывает слот, когда ее шоу имеют более высокий рейтинг, чем у оппонента. Существует ли совпадение расписания, в котором А составило расписание S, а В составило расписание Т, и (S, T) является стабильным, так что ни одна сеть не может в одностороннем порядке изменить свое расписание и выиграть больше временных интервалов.

Answer 1

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

Proof

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

• Поэтому станция не может достичь стабильного соответствия, улучшая свой счет.

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

• Поэтому каждая программная перестановка стабильного соответствия должна давать одинаковые оценки обеим станциям.

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

Answer 2

Решение в Haskell:

hasStable :: Ord a => [a] -> [a] -> Bool
hasStable x y =
  score x y + score y x == 0

-- score is number of slots we win minus number of slots they win
-- in our best possible response schedule
score :: Ord a => [a] -> [a] -> Integer
score others mine =
  scoreSorted (revSort others) (revSort mine)
  where
    -- revSort is sort from biggest to smallest
    revSort = reverse . sort

scoreSorted :: Ord a => [a] -> [a] -> Integer
scoreSorted (o:os) (m:ms)
  | m > o =
    -- our best show is better then theirs
    -- we use it to beat theirs and move on
    1 + score os ms
  | otherwise =
    -- their best show is better then ours
    -- we match it with our worst show
    -- so we could make use of our big guns
    -1 + score os (m : ms)
scoreSorted _ _ = 0 -- there are no shows left

> hasStable [5,3] [4,2]
False
> hasStable [5,2] [3,4]
True

Answer 3

Пусть каждый телеканал имеет 2 шоу. TV-1:

Show1 имеет рейтинг 20 баллов. show2 имеет рейтинг 40 баллов.

TV-2:

Show1 имеет рейтинг 30 баллов. Show2 имеет рейтинг 50 баллов.

Тогда это ясно показывает, что сопоставление нестабильно.

Answer 4

Мой собственный ответ не является стабильным соответствием. Предположим, есть только 2 временных интервала. А есть программа p1 (5.0), p2 (3.0); B имеет программу p3 (4.0), p4 (2.0);

График А включает в себя: S1: p1, p2 S2: p2, p1 График Б включает в себя: Т1: р3, р4 T2: p4, p3

Итак, соответствие включает: (S1, T1) (S1, T2) (S2, T1) (S2, T2)

пока результаты (S1, T1) - (p1, p3) (p2, p4) 2: 0 - не стабильно, поскольку B может изменить свое расписание на T2, и в результате получится: (S1, T2) - (p1, p4) (p2, р3) 1: 0

Наоборот и другие соответствия.