Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 14.06.2011, 23:54
Новичок

Отправить личное сообщение для artemio Посмотреть профиль Найти все сообщения от artemio
 
Регистрация: 29.11.2009
Сообщений: 1

Цепь Маркова. Классы состояний
Добрый вечер. Имеется матрица смежности A для цепи Маркова. Требуется найти классы существенных состояний цепи (если они есть).
(* Существенное состояние — это такое состояние цепи Маркова, покинув которое, она всегда может в него вернуться *).
Помогите пожалуйста с алгоритмом нахождения существенных состояний. Мне нужно анализировать матрицу переходов за один шаг (т.е. исходную) или же за 2, 3 и т.д шагов (т.е. A^2, A^3 ...)?
  #2  
Старый 15.06.2011, 15:17
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Насколько я понял насчет существнных состояний:

Можно выделить сильно связанные компоненты графа, и посмотреть, как они связаны между собой.
Компоненты со входящими дугами содержат существенные состояния (f,g на присунке http://en.wikipedia.org/wiki/Strongl...cted_component)
Компоненты с исходящими - несущественные состояния (a,b,e)
Компонент с обоими типами внешних дуг (c d h) в данном случае содержит несущественные состояния. Но всегда ли это так - навскидку не скажу.


P.S. см. понятие матрица достижимости

Последний раз редактировалось MBo, 15.06.2011 в 15:30.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Абстрактные классы в С++ for DOS >VaiMR< Реализация, исходники, языки 4 23.03.2010 12:07
Алгоритм Маркова. Помогите, пожалуйста... гость Математические алгоритмы (другое) 0 01.05.2009 02:41
Помгите плс, просто прогу перевести в Классы, на борланд С++ гость Математические алгоритмы (другое) 3 25.04.2009 04:09
эквивалентность пар состояний в дка Silver Ghost Графы 0 20.01.2007 21:50