Проблем за достижимостта
Проблемът за достижимостта (на английски: reachability problem) е фундаментален проблем в компютърните науки, който се появява в контекста на конкурентните системи с краен и с безкраен брой състояния, изчислителните модели като клетъчни автомати и мрежи на Петри, в анализа на програми, дискретни и продължителни системи, критични по отношение на времето системи, хибридни системи, вероятностни и параметрични системи и отворени системи моделирани като игри.[1]
Като цяло проблемът за достижимостта може да бъде формулиран както следва:
| „ | Ако е дадена изчислителна система (с потенциално безкраен брой възможни състояния) с множество от валидни правила за трансформация, да се определи дали конкретно състояние на системата е достижимо от дадено начално състояние на същата система. | “ |
Варианти на проблема за достижимостта могат да се появят в зависимост от:
- допълнителни ограничения над началното или крайното състояния,
- специфични изисквания за пътищата на развитие на системата, както и
- ако се зададе като задача анализ на печелившите стратегии при безкрайно продължаващи игри или неизбежното наличие на определена динамика.
Типично за една фиксирана система, описана във вида на някакви редукционни правила, системи от уравнения, логически формули и други, проблемът за достижимостта се състои в проверката дали даден набор от целеви състояния може да бъде достигнат от даден набор от начални състояния на системата. Множеството от целевите състояния може да бъде представено експлицитно или чрез някакво имплицитно представяне (например, система от уравнения, множество от минимални елементи по отношение някаква наредба на състоянията). Усложнено представени количествени и качествени свойства на системата могат често да бъдат опростени за нуждите на базовия въпрос за достижимостта. В този контекст сред важните въпроси са граничните случаи на изчислителната сложност и способността за вземане на решения на системата, употребата на ефикасни евристики, алгоритмични решения и други. Алгоритмичните решения често се базират на различни комбинации от стратегии за изследване на пространството на решенията, символна обработка на множествата от състояния, декомпозиция или свеждане до известни задачи от линейното програмиране, и често печелят от използването на апроксимационни, екстраполационни и други евристики. Ad hoc решенията, както и решенията, генерирани от инструменти за удовлетворяване на ограниченията и вземане на дедуктивни решения, често се комбинират с цел да се постигне баланс между ефикасност и гъвкавост.[1]
Вижте също
[редактиране | редактиране на кода]Източници
[редактиране | редактиране на кода]- ↑ а б Giorgio Delzanno, Igor Potapov (Eds.): Reachability Problems – 5th International Workshop, RP 2011, Genoa, Italy, September 28–30, 2011. Proceedings. Lecture Notes in Computer Science 6945, Springer 2011, ISBN 978-3-642-24287-8
 
|
Тази страница частично или изцяло представлява превод на страницата Reachability problem в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.
ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни. |