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

Question

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

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

Обновлен:

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