Решение задачи 5.
Если n=1, и единственное слово начинается и заканчивается на одну и ту же букву, то цепочка построена.
Для того, чтобы можно было переупорядочить слова A1, ..., An из набора A в "цепочку", необходимо, чтобы совокупность букв, на которые заканчиваются слова, совпадала с совокупностью букв, на которые эти слова начинаются (другими словами, чтобы каждой завершающей букве слова соответствовала такая же начальная буква какого-то слова). То, что это не достаточное условие, показывает пример: AB, BC, CA, DE, ED. "Цепочку" построить нельзя.
Так как цепочка обязана пройти через каждое слово, то все равно, с какого слова набора A начинать. Возьмем слово A1. Удаляем его из множества A: A:=A\A1. Ищем в A какое-нибудь слово Ai, начинающееся с последней буквы слова A1 (такое слово всегда существует, так как мы считаем, что необходимое условие, упомянутое выше, выполняется). Удаляем Ai из A: A:=A\Ai, ищем в A какое-нибудь Aj, начинающееся с последней буквы Ai и т.д. Продолжаем до тех пор, пока либо все слова A1, ... ,An не войдут в цепочку (тогда задача решена), либо пока не окажется, что A не пусто, и в нем нет слова, начинающегося на последнюю букву x последнего слова (кстати, из необходимого условия следует, что эта буква x совпадает с первой буквой первого слова). Мы нашли какую-то подцепочку.
Пример: A=(AB,BC,CA,BD,DC,CB).
Подцепочка1: AB,BC,CA.
Цепочка существует: AB,BD,DC,CB,BC,CA.
Пусть мы нашли подцепочку 1. Берем опять какое-нибудь слово из A в качестве начального для очередной подцепочки и опять повторяем построение следующей подцепочки, и т.д.
В конце концов пусть множество A стало пустым, и весь начальный набор слов A1, ... ,An распался на k подцепочек. Начнем их склеивать:
Пусть в подцепочках i и j соответственно есть слова u и v такие, что в u и v совпадают первые буквы. Пусть цепочка i имеет вид i=BuC, а j=EvD (тут B,C,D,E - некоторые последовательности слов). Склеенная из i и j цепочка будет иметь вид
EuCBvD.
(Проверьте, что такая склейка корректна!)
Склеивая все подцепочки, получим искомую цепочку. Если на каком-то шаге окажется, что склейка никаких двух подцепочек невозможна, то задача неразрешима.
Пример 1. Для приведенного в предыдущем примере набора слов будет 2 подцепочки:
AB, BC, CA и
BD, DC, CB.
У них совпадают первые буквы в словах BC и BD. После склейки получаем
AB, BD, DC, CB, BC, CA.
Пример 2. A=(ACA, BB). Две подцепочки: ACA и BB. Слов с совпадающими первыми буквами в них нет, задача неразрешима.
Вариант #2 решения задачи.
Если при составлении цепочки оказалось, что в наборе A нет слова с первой буквой, совпадающей с последней буквой последнего слова Aj цепочки, то Aj "отщепляем" от нее и пытаемся найти другое подходящее слово. Если это не удается, то "отщепляем" очередное последнее слово цепочки и т.д. Если на каком-то шаге A пусто, то задача решена, иначе если на каком-то шаге цепочка стала пустой, то задача неразрешима.
Пусть есть набор слов A=(A1, ... ,An). Каждому слову приписан его уникальный номер, равный индексу. Слова упорядочены по возрастанию индекса.
Цепочка = A1
A=A\A1; инд=1.
Пока (A не пусто) и (цепочка не пустая) повторять
нц
Если в A есть подходящее слово с индексом > инд
то приписываем к цепочке это слово,
слово удаляем из A
инд=1
иначе "отщепляем" от цепочки последнее слово Aj
инд=j
Aj заносим в A
кц
Если A пусто, то цепочка найдена
иначе задача не имеет решения.
Этот метод называется "перебор с возвратом" ("backtracking").
|
