Алгоритм сокращения серии действий?

Question

Прошло некоторое время с тех пор, как мой класс алгоритмов в школе, так что простите меня, если моя терминология не точна.

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

Моя цель - найти кратчайшую последовательность шагов, которые все еще создают желаемое состояние. Любой данный шаг может оказаться ненужным, поэтому я стараюсь как можно более эффективно удалить их.

Я хочу сохранить порядок шагов (так что я могу удалить шаги, но не переупорядочить их).

Наивный подход, который я беру, - взять всю серию и попробовать удалить каждое действие. Если я успешно удалю одно действие (без изменения конечного состояния), я начну с начала серии. Это должно быть O (n^2) в худшем случае.

Я начинаю играть с такими способами, чтобы сделать это более эффективным, но я уверен, что это проблема. К сожалению, я точно не знаю, что для Google - серия на самом деле не «путь», поэтому я не могу использовать алгоритмы сокращения пути. Любая помощь - даже просто предоставление мне некоторых условий для поиска - была бы полезна.

Обновление: несколько человек указали, что даже мой наивный алгоритм не найдет кратчайшего решения. Это хороший момент, поэтому позвольте мне немного пересмотреть свой вопрос: какие-либо идеи о приближенных алгоритмах для одной и той же проблемы? Я предпочел бы иметь короткое решение, которое будет почти кратчайшим решением быстро, чем занять очень много времени, чтобы гарантировать абсолютную кратчайшую серию. Благодаря!

Answer 1

Ваш наивный подход n^2 не совсем правильный; в худшем случае вам, возможно, придется посмотреть на все подмножества (ну, на самом деле, более точная вещь заключается в том, что эта проблема может быть NP-hard, что не означает, что «возможно, придется смотреть на все подмножества», но в любом случае .. .)

Например, предположим, что в данный момент вы выполняете шаги 12345, и вы начинаете пытаться удалить каждый из них по отдельности. Тогда вы можете обнаружить, что вы не можете удалить 1, вы можете удалить 2 (так что вы его удалите), тогда вы посмотрите на 1345 и обнаружите, что каждый из них необходим - ни один не может быть удален. Но может получиться, что на самом деле, если вы держите 2, то достаточно «125».

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

Answer 2

Самое очевидное, что приходит на ум - это двоичное поисковое рекурсивное разделение на половинки, где вы поочередно оставляете каждую половину. Если оставить половину на любом этапе рекурсии, все еще воспроизводит конечное состояние, то оставьте это; в противном случае, положить его обратно и рекурсию на обеих половины этой половины и т.д.

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

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

Answer 3

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

Указанный двоичный метод поиска был бы достаточным, если только один шаг вызвал желаемое состояние.

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

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

Answer 4

Ваш проблемный домен может быть сопоставлен с направленным графом, в котором вы указываете как узлы и шаги как ссылки, вы хотите найти кратчайший путь в графе, для этого существует ряд известных алгоритмов, например Dijkstra's или A*

Обновлено:

Давайте думать о простом случае, у вас есть один шаг, что ведет от состояния а в состояние в это можно сделать в виде 2 узлов по проведён ссылке. Теперь у вас есть еще один шаг, который ведет от A до C и от C вы делаете шаг, что приводит к B. При этом у вас есть график с 3 узлами и 3 ссылками, стоимость достижения B от A it eather 2 (ACB) или 1 (AB). Итак, вы можете видеть, что функция стоимости очень проста, вы добавляете 1 за каждый шаг, который вы делаете, чтобы достичь цели.

Answer 5

Delta Debugging, метод сведения к минимуму набора ошибок, вызывающих отказ, может быть хорошим.
Раньше я использовал Delta (сводит к минимуму «интересные» файлы на основе теста на интересность), чтобы уменьшить файл размером 1000 строк до 10 строк для отчета об ошибке.