Блог

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

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

Он находится в «региональном», «западном и центральном» разделе «проблема 3 — цепочки домино».

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

Похоже, что эта проблема требует рекурсивного подхода к возврату. Сохраняйте симметричную матрицу 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 .

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

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

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

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

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

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

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

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

 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}

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

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

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

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

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

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

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