Проблема достижимости
Достижимость — это фундаментальная проблема, возникающая в нескольких различных контекстах: параллельные системы с конечным и бесконечным числом состояний , вычислительные модели , такие как клеточные автоматы и сети Петри , программный анализ , дискретные и непрерывные системы , критичные ко времени системы, гибридные системы , системы перезаписи , вероятностные и параметрические системы и открытые системы, моделируемые как игры . [1]
В общем случае проблему достижимости можно сформулировать следующим образом: для заданной вычислительной системы (потенциально бесконечное состояние) с набором разрешенных правил или преобразований решить, достижимо ли определенное состояние системы из заданного начального состояния системы.
Варианты проблемы достижимости могут быть результатом дополнительных ограничений на начальные или конечные состояния, конкретных требований к путям достижимости, а также итерационной достижимости или изменения вопросов в анализе выигрышных стратегий в бесконечных играх или неизбежности некоторой динамики.
Как правило, для фиксированного описания системы, заданного в той или иной форме (правила редукции, системы уравнений , логические формулы и т. д.), проблема достижимости состоит в проверке возможности достижения заданного набора целевых состояний, начиная с фиксированного набора начальных состояний. Набор целевых состояний может быть представлен явно или через какое-либо неявное представление (например, система уравнений, набор минимальных элементов относительно некоторого порядка состояний). Сложные количественные и качественные свойства часто можно свести к основным вопросам достижимости. Границы разрешимости и сложности, алгоритмические решения и эффективные эвристикивсе важные аспекты, которые следует учитывать в этом контексте. Алгоритмические решения часто основаны на различных комбинациях стратегий исследования, символических манипуляциях с наборами состояний, свойствах декомпозиции или сведении к задачам линейного программирования , и они часто выигрывают от приближений, абстракций, ускорений и эвристики экстраполяции. Специальные решения, а также решения, основанные на решателях ограничений общего назначения и механизмах дедукции, часто комбинируются, чтобы сбалансировать эффективность и гибкость.
Явно описанная проблема достижимости в ориентированном графе является NL-полной. Рейнгольд в статье 2008 года доказал, что проблема достижимости неориентированного графа находится в LOGSPACE. [2]
В планировании , точнее в классическом планировании, интересует, можно ли достичь состояния из начального состояния из описания действий. Описание действий определяет граф неявных состояний, размер которого экспоненциально зависит от размера описания.
