Выбор алфавита, который охватывает большинство слов?

Ответ 1

Эта проблема NP-жесткая путем сокращения от CLIQUE (это своего рода самая плотная проблема k-sub (гипер)). Для графа назовите его вершины разными буквами и для каждого ребра произведите двухбуквенное слово. Существует k-клика тогда и только тогда, когда мы можем покрыть k, выберем 2 слова с k буквами.

Ситуация с алгоритмом даже для CLIQUE grim (время выполнения должно быть n ^ Theta (k) при правдоподобной гипотезе), поэтому я не уверен, что рекомендовать, кроме грубой силы, с примитивными битными массивами.

Ответ 2

Я еще не уверен, что это правильно, но, надеюсь, это хотя бы близко. Мы рассматриваем решение динамического программирования. Перечислите слова от 1 до N, буквы в нашем алфавите от 1 до P. Мы хотим иметь возможность решать (n, p) в терминах всех вспомогательных решений. Рассмотрим несколько случаев.

Простейшим случаем является то, что n-е слово уже находится в словаре, заданном в решении (n-1, p). Затем мы посчитаем себя удачливыми, слова, покрытые одним, и оставьте словарь неизменным (ddictionary ссылается на некоторое подмножество букв здесь).

Предположим вместо этого, что n-е слово не находится в словаре, заданном (n-1, p). Тогда либо решение словаря (n-1, p) является словарем для (n, p), либо n-е слово находится в решении. Поэтому мы ищем решения, в которых явное включение n-го слова. Итак, мы добавляем все буквы в n-ом слове в словарь, который мы рассматриваем. Теперь мы исследуем все предыдущие подмножества вида (n-1, i), где я - p-1 или меньше. Мы ищем наибольшее значение я такое, что | d (n-1, i) U d (n) | <= p. Где d (n-1, i) означает словарь, связанный с этим решением, а d (n) просто означает словарь, связанный со всеми буквами n-го слова. На простом английском языке мы используем наши подмножества, чтобы найти лучшее решение с меньшим значением p, которое позволяет нам соответствовать новому слову. Как только мы нашли это значение i, мы объединим словари, размер которых мы измеряли. Если величина этого множества все еще не равна p, повторим описанный выше процесс. Когда мы создали словарь с величиной p, который покрывает n-е слово этой техникой (или повторяется через все предыдущие решения), мы вычисляем его охват и сравниваем его с охватом, который мы получим, просто используя словарь из (n-1, р), и мы выбираем лучшее. Если theres галстук, мы выбираем оба.

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

Ответ 3

Я бы сделал это:

• Используйте входные слова для создания структуры данных, которая отображает списки букв (строк) на количество слов, которые они покрывают. Вы можете сделать это, извлекая уникальные буквы, которые составляют слово, сортируют их и используют результат как ключ карты хэша.
• Не обращайте внимания на записи, ключи которых длиннее P (не могут покрывать эти слова нашим ограниченным алфавитом).
• Для всех остальных нужно вычислить список содержащихся в них записей (алфавит "ab" содержит алфавит "b" и "a" ). Суммируйте количество слов, охватываемых этими записями.
• Найдите запись с наибольшим количеством клавиш.

Ответ 4

Как показал Дэвид выше (с отличным доказательством!), это NP-hard, поэтому вы не получите идеального ответа в любой ситуации.

Один из подходов к добавлению к другим ответам - выражать это как проблему максимального потока.

Определите источник node S, приемник node D, a node для каждого слова и node для каждой буквы.

Добавьте ребра из S в каждое слово емкости 1.

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

Добавьте ребра из каждой буквы в D емкости x (где мы определим x за один момент).

Затем решим для минимального разреза этого графа (используя алгоритм максимального потока от S до D). Край разреза на букву означает, что эта буква не включена в решение.

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

Тогда идея состоит в том, чтобы варьировать x (например, путем деления пополам), чтобы попытаться найти значение для x, где разрезают ровно k краев письма. Если вы справитесь с этим, вы определите точное решение своей проблемы.

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