Домино - Конкурс

Question

http://ecoocs.org/contests/ecoo_2007.pdf

Я готовлюсь к предстоящим регионалам ecoo для моей области, и я озадачен этим одним вопросом. Я действительно понятия не имею, с чего начать.

Это в «региональном» «западном и центральном» разделе «проблема 3 - цепочки домино».

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

Answer 1

Похоже, что эта проблема требует рекурсивного подхода к возврату. Сохраняйте симметричную матрицу 7 на 7, показывающую, какие числа к каким привязаны. Например, для данных плиток 00 12 63 51 у вас будет следующая матрица:

  0 1 2 3 4 5 6 
  -------------
0|1 0 0 0 0 0 0
1|0 0 1 0 0 1 0
2|1 0 0 0 0 0 0
3|0 0 0 0 0 0 1
4|0 0 0 0 0 0 0
5|0 1 0 0 0 0 0
6|0 0 0 1 0 0 0

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

  0 1 2 3 4 5 6 
  -------------
0|1 0 0 0 0 0 0
1|0 0 0 0 0 0 0
2|0 0 0 0 0 0 0
3|0 0 0 0 0 0 1
4|0 0 0 0 0 0 0
5|0 0 0 0 0 0 0
6|0 0 0 1 0 0 0

Учитывая, что цепочка в настоящее время заканчивается на 2, вы будете искать в строке 2 любые числа, к которым можно подключиться. Не найдя ничего, вы бы отметили 51 12 как потенциально самую длинную цепочку, а затем вернулись к состоянию, в котором цепочка содержала только 51.

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

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

Answer 2

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

Итак, если у нас есть эти кусочки:

45 36 46 56

Что самая длинная цепь из 4 костей ?Очевидно, самая длинная цепь, которая может быть сделана из 3 костей и еще 1 кости.

Что такое самая длинная цепь, которая может быть сделана из 3 костей ?Очевидно, самая длинная цепь, которая может быть сделана из 2 костей и еще 1 кости.

Что такое самая длинная цепь, которая может быть сделана из 2 костей ?Очевидно, самая длинная цепь, которая может быть сделана из 1 кости и еще 1 кости.

Что такое самая длинная цепь, которая может быть сделана из 1 кости ?Очевидно, что 1 кость - самая длинная из возможных цепей.

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

Так что если у нас есть:

45 36 46 56

Предположим, у нас есть функция longest_chain(set_of_pieces).Затем нам нужно проверить:

longest_chain({36 46 56}) (+ 1 if we can append 45 or 54 else discard this chain)
longest_chain({45 46 56}) (+ 1 if we can append 36 or 63 else discard this chain)
longest_chain({45 36 56}) (+ 1 if we can append 46 or 64 else discard this chain)
longest_chain({45 36 46}) (+ 1 if we can append 56 or 65 else discard this chain)

что такое longest_chain({36 46 56})?

longest_chain({46 56}) (+ 1 if we can append 36 or 63 else discard this chain)
longest_chain({36 56}) (+ 1 if we can append 46 or 64 else discard this chain)
longest_chain({36 46}) (+ 1 if we can append 56 or 65 else discard this chain)

что такое longest_chain({46 56})?

longest_chain({46}) (+ 1 if we can append 56 or 65 else discard this chain)
longest_chain({56}) (+ 1 if we can append 46 or 64 else discard this chain)

что такое longest_chain({46})?Две возможности: {46} {64}
Можем ли мы добавить 56 или 65 к любому из них?Да, мы можем сделать эту цепочку {46, 65}, и мы отбрасываем {64}.
Сделайте то же самое с longest_chain({56}), и мы получим: {56, 64}.

Поэтому мы теперь знаем, что longest_chain({46 56}){46, 65}, {56, 64}

Продолжайте делать это, пока не получите все ответы.

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

Answer 3

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

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

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

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

Answer 4

Вот как я бы начал.

Обозначьте n домино D1..Dn.

Пусть Cm будет набором цепочек, образованных с использованием подмножества доминов D1..Dm(и C0 = {}).

Cm+1 формируется путем попытки вставить Dm + 1 во все возможные места в цепях в Cm, плюс использование Dm+1, где это возможно, для объединения пар непересекающихся цепей изCm, плюс одиночная цепочка, состоящая из Dm+1 сама по себе.

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