Самая длинная цепочка домино/последовательность

Question

Мне нужно найти самую длинную цепочку домино, учитывая набор из 12 случайно выбранных домино. Я уже рекурсивно генерировал все возможности домино (существует 91 возможность использования граничных значений от 0 до 12). Домино состоит из одного «кирпича» с двумя квадратами на нем: [a | b], где 0 = < a, b < = 12. Таким образом, примером домино может быть [12, 0] или [6, 3] и т. д. Домино может соединяться, если соседние половинки имеют одинаковое значение.

Домино может быть перевернуто для обеспечения соответствия. Например, данные [8, 4], [9, 4] могут быть перевернуты, чтобы сделать пару [8, 4] [4, 9]

Следующие методы (относящиеся к этому вопросу) доступны для этого класса :

void flipEnds(); // Flips the domino 
int getLeft() const; 
int getRight() const; 
bool hasBeenPlayed() const; 
void setPlayed(bool value); 

Таким образом, выборочные данные для этой задачи будет выглядеть следующим образом:

myDomino #0: [1 12 ] 
    myDomino #1: [0 5 ] 
    myDomino #2: [7 9 ] 
    myDomino #3: [2 7 ] 
    myDomino #4: [7 12 ] 
    myDomino #5: [4 8 ] 
    myDomino #6: [8 10 ] 
    myDomino #7: [3 11 ] 
    myDomino #8: [11 12 ] 
    myDomino #9: [10 11 ] 
    myDomino #10: [2 9 ] 
    myDomino #11: [2 4 ] 

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

Answer 1

Последовательность домино может быть представлена ​​как {# 3, Y}, {# 4, N}, {# 0, Y}, ... Первое число - это номер домино в вашей руке, а второй - это ли он перевернут или нет. Мы хотим проверить каждую возможную последовательность, но сначала обрезаем незаконно один.

Предположим, что у вас есть функция testSequence(sequence), которая является последовательностью в силе. Держите два списка, один из текущей последовательности currentSeq, и один из домино вы еще не выбрали unused.

рекурсии может быть как

checkAllSeq(currentSeq, unused) { 

    foreach(domino in unused) { 
     unused2 = unused - domino // remove domino from unused list 
     seq1 = currentSeq + {domino,true} // add unfliped domino to sequence to test 
     if(testSequence(seq1)) { 
      checkAllSeq(seq1,unused2)  // recurse 
     } 
     // now do it with the domino flipped 
     seq2 = currentSeq + {domino,false} 
     if(testSequence(seq2)) { 
      checkAllSeq(seq2,unused2) 
     } 
    } 
} 

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

Answer 2

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

Для любой рекурсивной проблемы вам необходимо иметь дело с тремя случаями: начальным случаем, средними случаями и терминальным корпусом. Здесь исходный случай - когда у вас нет домино (так что вы можете играть в любое домино в любой ориентации); средний случай - когда вам нужно играть в домино, которое соответствует самому последнему; терминальный регистр - это когда нет домино, которое можно добавить к последнему, или когда все домино были сыграны.

Вам необходимо отслеживать два списка домино: один для текущего наиболее известного совпадения и один для текущей попытки совпадения.

Если вам удалось сыграть все домино, вернитесь рано; в противном случае наилучший возможный ввод на самом деле займет самое длинное.

Это наивный подход, который равен NP-hard (возможность обоих концов домино с таким же числом не оказывает существенного влияния на проблему, а просто добавляет 0,5 к весу каждого края); это, вероятно, стоит использовать эвристику.

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

Answer 3

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

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

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

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

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