[Из песочницы] О переборе на примере генерации кроссвордов

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

Этот и все последующие рисунки взяты из исходной статьи

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



Предлагаемое решение основано на двух основных идеях:

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 и assignment. В words для каждого еще не рассмотренного слова, содержится список слов, которые могут стоять на этом месте (исходно — все слова требуемой длины), а в assignment — зафиксированные значения уже рассмотренных слов (исходно — пусто):

// Сигнатура
def search(variants: Map[Word, List[String]], assignment: 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]], assignment: 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), упомянутых в исходной

статье:

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

К счастью, эту проблему легко исправить. Для этого достаточно выбрать правильный порядок рассмотрения. Сейчас в поиске берется первое попавшееся слово.

Есть ли более эффективные стратегии? Есть, и одна из них была предложена еще в 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:

Однако сетка 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)

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

Кроссворд, сгенерированный за 30 секунд (на самом деле в этом случае повезло с random-омом, кроссворд быстро генерируется где-то в одном из 20 случаев):

акаст ахум ахум 
лагер алоа лара 
анами рокк ерма 
радиопередатчик 
мланзи трут     
   аарне флоэма 
маар кетч актор 
антидепрессанты 
атасу аапа йаук 
картли целом    
    инси облака 
присовокупление 
раху алла ананд 
убор лоик кинди 
торт анна аедие  

Выводы

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

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.