Про перебиранні на прикладі генерації кросвордів

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

image
Цей і всі наступні малюнки взяті з вихідної статті

У цій статті я б хотів обговорити набагато більш просте рішення, яке дозволяє вирішити цю задачу.

Пропоноване рішення базується на двох основних ідеях:

  1. Правильний порядок перебору
  2. Не здійснювати одні й ті ж дії повторно
Весь код написаний на мові Scala.

Структури даних

Уявімо поле кросворду у вигляді двовимірного списку клітин (Cell):

val field: List[List[Cell]] = readField("cross.in")

При цьому кожна комірка являє небудь білок і повинна містити літеру (Letter), або чорної, і повинна залишитися порожньою (Empty):

sealed abstract class Cell
case object Empty extends Cell // Всі порожні клітини однакові
case class Letter() extends Cell // А клітини з буквами - немає

Слово — послідовність літер:

class Word(val letters: Seq[Letter])

Словник — кількість слів, згрупованих по довжинах:

val dictionary: Map[Int, Set[String]] = readWords("cross.txt", "WINDOWS-1251").groupBy(_.size)

Виділення слів

Зауважимо, що в описі поля немає відзначені слова. Будемо вважати словом вертикальний або горизонтальний набір (майбутніх) букв, обмежених порожніми клітинами, або краями дошки.
Навчимося виділяти слова в рядку:

def extractWords(row: List[Cell]): Seq[Word] = {
val rest = row.dropWhile(_ == Empty) // Пропускаємо порожні клітини
if (rest.isEmpty) Seq() // Більше клітин немає
else {
// Беремо не порожні клітини поки можемо, і складаємо з них слово
val word = new Word(rest.takeWhile(_ != Empty).map(_.asInstanceOf[Letter]))
// Вызываемся рекурсивно на залишку і додаємо складене слово
word +: extractWords(rest.dropWhile(_ != Empty))
}
}

Для виділення всіх слів, виділяємо слова з рядків, транспонируем поле і виділяємо слова з стовпців. Заодно, прибираємо однобуквені слова.

val words = (field.flatMap(extractWords) ++ field.transpose.flatMap(extractWords)).filter(_.letters.size != 1)

Для швидкого пошуку пересічних слів, будемо в (майбутніх) буквах зберігати інформацію, які слова через них проходять і номер букви в цьому слові:

case class Letter() extends Cell {
var words = Array.empty[(Word, Int)]
}
for (word <- words; (letter, index) <- word.letters.zipWithIndex) {
letter.words :+= (word, index)
}

Перебір

В процедуру перебору будемо передавати два відображення (Map): variants і призначення. В words для кожного ще не розглянутого слова, міститься список слів, які можуть стояти на цьому місці (початково — всі слова необхідної довжини), а в assignment — зафіксовані значення вже розглянутих слів (початково — порожньо):

// Сигнатура
def search(variants: Map[Word List[String]], призначення: Map[Word, String])
// Виклик
search(words.map(w => (w, random.shuffle(dictionary(w.letters.size).toList))).toMap, Map.empty)

Відмітимо, що при виклику здійснюється перемішування слів в списку, так що при різних запуски будуть вийти різні кросворди.

Тепер ми можемо написати першу версію перебору:

def search(variants: Map[Word List[String]], призначення: Map[Word, String]) {
if (variants.isEmpty) {
// Всі слова вибрані виводимо розстановку
dump(assignment)
} else {
// Беремо перше-ліпше слово і відповідні варіанти
val (word, vars) = variants.head
// Перебираємо всі варіанти
for (variant <- vars) {
// Видаляємо слово і вже розглянутих
var newVariants = variants - word
// Перебираємо літери слова, знаходимо інше слово, що проходить через кожну букву 
for ((letter, char) <- word.letters.zip(variant); (other, index) <- letter.words; if newVariants.contains(other)) {
// Залишаємо тільки ті варіанти, в яких на необхідному місці (index) будує правильна літера
newVariants = newVariants.updated(other, variants(other).filter(var => var(index) == char))
}
// Вызываемся рекурсивно
search(newVariants, assignment.updated(word, variant))
}
}
}

На жаль, за розумний час, цей перебір не здатний знайти рішення навіть для найпростішої з сіток (9x9), згаданих у вихідній
статті:

image

Правильний порядок перебору

На щастя, цю проблему легко виправити. Для цього досить вибрати правильний порядок розгляду. Зараз в пошуку береться перше-ліпше слово.

Чи є більш ефективні стратегії? Є, і одна з них була запропонована ще в 1965 році в статті S. W. Golomb, L. D. Baumert Backtrack Programming // Journal of the ACM Volume 12 Issue 4, 1965. На жаль, мені не вдалося знайти цю статтю у відкритому доступі, але сама ідея дуже проста: треба перебирати те, для чого залишилося найменше варіантів.

В нашому випадку, це означає, що ми повинні брати не довільно слово, а той, у якого залишилося найменше підходящих варіантів:

val (word, vars) = variants.minBy(_._2.size)

Зауважимо, що при цьому ми безкоштовно отримуємо два приємних бонусу. По-перше, якщо для якогось слова залишилося варіантів, то воно буде відразу обрано і ця гілка буде відсічена без подальшого перебору. По-друге, якщо для слова залишився тільки один варіант, то його відразу поставлять, що дозволить скоротити перебір в майбутньому.

Ця оптимізація дозволяє миттєво знаходити рішення для сітки 9x9 і більш ніж в 50% випадків знаходити рішення для «простий» сітки 15x15:

image

Однак сітка 11x11 і «складна» сітка 15x15 все ще вимагають занадто багато часу.

Не здійснювати одні й ті ж дії повторно

Як і в більшості програм, і в нашому перебір більшу частину часу займає самий внутрішній цикл, в якому ми видаляємо «невідповідні» слова:

newVariants = newVariants.updated(other, variants(other).filter(_(index) == char))

На перший погляд, у цьому рядку циклу немає, але насправді він причаївся в реалізації методу filter. Як ми можемо заощадити тут час? А давайте кешувати результати цього циклу!

Зауважимо, що тут обчислюються списки слів, у яких частина букв зафіксовано а частина не відома. Будемо представляти таке «часткове» слово, у вигляді маски формату "
?ол??про
", тобто вказуючи знаки питання замість невідомих літер.

Тепер в переборі будемо оперувати не списками «підходящих» слів, а масками + кешувати результати обчислення списків:

def search(masks: Map[Word, String], assignment: Map[Word, String]) {
if (masks.isEmpty) {
// Всі слова вибрані виводимо розстановку
dump(assignment)
} else {
// Беремо слово з мінімальним числом варіантів
val (word, mask) = masks.minBy(w => cache(w._2).size)
// Перебираємо варіанти
for (variant <- cache(mask)) {
var newVariants = masks - word
// Перебираємо "перехресні" слова
for ((letter, char) <- word.letters.zip(variant); (other, index) <- letter.words; if newVariants.contains(other)) {
val oldMask = masks(other)
val newMask = oldMask.updated(index, char)
// При необхідності, додаємо значення у кеш
cache.getOrElseUpdate(newMask, cache(oldMask).filter(_(index) == char))
newVariants = newVariants.updated(other, newMask)
}
search(newVariants, assignment.updated(word, variant))
}
}
}

Перед використанням нової функції пошуку, потрібно заповнити кеш словами зі словника і згенерувати вихідні маски для всіх слів:

for ((length, variants) <- dictionary) {
cache.getOrElseUpdate("?" * length, random.shuffle(variants.toList).toArray)
}
search(words.map(w => (w, "?" * w.letters.length)).toMap, Map.empty)

Додавання кешування дозволяє перебору знаходити рішення навіть для самої складної сітки:

image

Кросворд, згенерований за 30 секунд (насправді в цьому випадку пощастило з random-омом, кросворд швидко генерується десь в одному з 20 випадків):

акаст ахум ахум
лагер алоа лара
анами рокк єрма
радіопередавач
мланзи труть
аарне флоема
маар кетч актор
антидепресанти
атасу аапа йаук
картлі цілому
инси хмари
присовокупление
раху алла ананд
убір лоїк кінді
торт ганна аедие

Висновки

Застосування пари простих оптимізацій дозволило легко реалізувати рішення, краще ніж евристичне рішення, засноване на глибокому знанні предметної області. Вибирайте правильний порядок перебору і не здійснюйте одні і ті ж підрахунки повторно!


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.