Алгоритм сокращения серии действий?
Прошло некоторое время с тех пор, как я учился на уроках алгоритмов в школе, так что простите меня, если моя терминология неточна.
У меня есть ряд действий, которые при запуске приводят к желаемому состоянию (в основном это набор шагов для воспроизведения ошибки, но это не имеет значения для ответа на этот вопрос).
Моя цель - найти кратчайшую серию шагов, которая все же приведет к желаемому состоянию. Любой данный шаг может быть ненужным, поэтому я пытаюсь удалить их как можно эффективнее.
Я хочу сохранить порядок шагов (чтобы можно было удалять шаги, но не менять их порядок).
Наивный подход, который я использую, - взять всю серию и попытаться удалить каждое действие. Если мне удастся удалить одно действие (без изменения конечного состояния), я начну с начала серии. В худшем случае это должно быть O (n ^ 2).
Я начинаю искать способы сделать это более эффективным, но я почти уверен, что это решенная проблема. К сожалению, я не совсем уверен, что делать с Google - серия на самом деле не является «путем», поэтому я не могу использовать алгоритмы сокращения пути. Любая помощь - даже просто предоставление мне нескольких терминов для поиска - была бы полезна.
Обновление: несколько человек отметили, что даже мой наивный алгоритм не найдет кратчайшего решения. Это хороший момент, поэтому позвольте мне немного пересмотреть свой вопрос: есть ли идеи о приблизительных алгоритмах для той же проблемы? Я бы предпочел быстро получить короткое решение, близкое к самому короткому, чем требовать очень много времени, чтобы гарантировать абсолютную кратчайшую серию. Спасибо!
Я не понимаю, почему вы говорите, что это не имеет значения, это для отладки: если это так, то Delta Debugging поможет вам автоматически минимизировать набор отказов, вызывающих ввод ИЛИ изменений исходного кода, чтобы изолировать ошибку и т. д. как отмечает Хастуркун. Просьба уточнить.
Ответы 5
Самое очевидное, что приходит в голову, - это рекурсивное деление на половинки, основанное на бинарном поиске, где вы поочередно опускаете каждую половину. Если исключение половины на любом этапе рекурсии по-прежнему воспроизводит конечное состояние, то оставьте его; в противном случае вставьте его обратно и выполните рекурсию на и то и другое половинах этой половины и т. д.
Рекурсия на обеих половинах означает, что он пытается удалить большие куски, прежде чем сдаться и попробовать меньшие куски этих кусков. В худшем случае время выполнения будет O (n log (n)), но если у вас большое n с высокой вероятностью множества не относящихся к делу шагов, он должен выиграть перед подходом O (n) с попыткой исключения каждый шаг по одному (но без перезапуска).
Этот алгоритм найдет только некоторые минимальные пути, однако он не может найти пути меньшего размера, которые могут существовать из-за комбинаторных межшаговых эффектов (если шаги действительно такого характера). Однако их обнаружение приведет к комбинаторному взрыву, если у вас не будет дополнительной информации о шагах, с помощью которых можно рассуждать (например, о зависимостях).
Если вы не делаете строго никаких предположений о влиянии каждого действия и хотите точно найти наименьшее подмножество, тогда вам нужно будет попробовать все возможные подмножества действий, чтобы найти кратчайшее следствие.
Заявленный метод двоичного поиска будет достаточен только в том случае, если один шаг вызвал желаемое состояние.
В более общем случае даже удаление одного действия за раз не обязательно даст вам последовательность самый короткий. Это тот случай, если вы рассматриваете патологические примеры, когда действия могут вместе не вызывать проблем, но индивидуально запускать желаемое состояние.
Кажется, ваша проблема сводится к более общей проблеме поиска, и чем больше предположений вы можете создать, тем меньше станет ваше пространство поиска.
Нет, ты не читал мой ответ. Это был бинарный поиск вдохновленный; он каждый раз нет отбрасывает половину пространства поиска, поскольку я прямо говорю, что ваша рекурсия на и то и другое делится вдвое.
Приношу свои извинения, без обид, я говорил с той точки зрения, что, сохраняя обе половинки, вы теряете преимущество перед методом сканирования.
Ваш наивный подход n ^ 2 не совсем правильный; в худшем случае вам, возможно, придется смотреть на все подмножества (ну, на самом деле, точнее сказать, что эта проблема может быть NP-сложной, что не означает, что «возможно, придется смотреть на все подмножества», но в любом случае ... .)
Например, предположим, что вы в настоящее время выполняете шаги 12345 и начинаете пытаться удалить каждый из них по отдельности. Затем вы можете обнаружить, что не можете удалить 1, вы можете удалить 2 (поэтому вы удалите его), затем вы посмотрите на 1345 и обнаружите, что каждый из них важен - ни один из них не может быть удален. Но может оказаться, что на самом деле, если оставить 2, то достаточно 125.
Если ваше семейство наборов, которые производят данный результат, не является монотонным (т.е. если оно не обладает свойством, что если определенный набор действий работает, то будет работать и любой надмножество), то вы можете доказать, что нет способа найти кратчайшая последовательность без просмотра всех подмножеств.
Очень хороший момент. Хорошо, есть идеи по поводу алгоритмов приближения для той же проблемы? Мне не обязательно нужна самая короткая серия: лучше быстро найти очень короткую серию, чем медленно найти абсолютную самую короткую серию в моем приложении. Спасибо!
Ваша проблемная область может быть отображена на направленный граф, где у вас есть состояния как узлы и шаги как ссылки, вы хотите найти кратчайший путь в графе, для этого существует ряд хорошо известных алгоритмов, например Дейкстры или А *
Обновлено:
Давайте подумаем о простом случае, у вас есть один шаг, который ведет из состояния A в состояние B, это можно изобразить как 2 узла, соединенных ссылкой. Теперь у вас есть еще один шаг, который ведет от A к C, а от C у вас есть шаг, который ведет к B. Таким образом, у вас есть график с 3 узлами и 3 связями, стоимость достижения B от A это 2 (ACB) или 1 ( AB). Итак, вы можете видеть, что функция затрат на самом деле очень проста: вы добавляете 1 за каждый шаг, который вы делаете для достижения цели.
Боюсь, что я не понимаю, как будет работать такое сопоставление - каждый шаг не имеет стоимости, как на графике. Это либо необходимо, либо нет, и то, нужно это или нет, может зависеть от других шагов.
Дельта-отладка, метод минимизации набора входных сигналов, вызывающих отказ, может быть хорошим подходом. Я ранее использовал Дельта (минимизирует "интересные" файлы на основе теста на интересность), чтобы уменьшить файл с ~ 1000 строк примерно до 10 строк для отчета об ошибке.
Подход «разделяй и властвуй», который я описал, должен работать как приближение для больших n со многими несущественными шагами, как я указываю в развернутом ответе.