эффективный алгоритм угадывания

Question

Я абстрагирую проблему реального мира в следующем вопросе:

• X - пул всех возможных перестановок букв.
• Y - пул строк.
• F - это функция, которая берет кандидата x из X и возвращает логическое значение в зависимости от того, принадлежит ли x к Y.

F стоит дорого, а X огромен. Каков наиболее эффективный способ извлечь как можно больше результатов из Y? Ложные срабатывания в порядке.

Answer 1

На самом деле нет никакого способа ответить на этот вопрос хорошо, так как большинство решений этих типов проблем сильно зависит от предметной области.

Вам, вероятно, следует попробовать свой вопрос здесь: https://cstheory.stackexchange.com/

Но, чтобы дать вам пример диапазона возможностей, о которых вы говорите;проблема коммивояжера кажется похожей - и часто решается с помощью «самоорганизующейся карты»: http://www.youtube.com/watch?v=IA6eGYMyr1A

Конечно, «решения», которые люди находят в решении проблемы коммивояжера, не обязательноЛУЧШЕЕ решение, просто ХОРОШЕЕ решение ... поэтому ваш вопрос не указывает, применимо ли это к вашей ситуации или нет.

Звучит так, будто вы просите какую-то более эффективную технику грубого принуждения ... но ее просто нет.

В качестве другого примера, для взлома паролей (что похоже на ваш вопрос), люди часто сначала пробуют «часто используемые слова / пароли», прежде чем прибегнуть к полной грубой силе ... но это, опять же,доменное решение.

Answer 2

Сделайте F менее дорогим, внедрив Расчет на основе дельты . Затем используйте метаэвристику (или ответвление и границу), чтобы найти как можно больше Y (например, используйте Drools Planner ).

Answer 3

Введите другую функцию G, которая дешева, а также проверяет, принадлежит ли x к y.G должен возвращать истину всякий раз, когда F возвращает истину, и может возвращать истину, когда F возвращает ложь.Первый тест с G, тестирование с F, только если G возвращает true.

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