Алгоритм Джонсона (т=2). Марковский случайный процесс

↑

⇐ ПредыдущаяСтр 25 из 28Следующая ⇒

Алгоритм Джонсона (т=2)

В матрице  выбираем минимальный элемент . Возможны три случая:

а) . Тогда работу  ставим в конце головной последовательности на выполнение;

б) . Тогда работу  ставим в начале хвостовой последовательности на выполнение;

в) . Тогда работу  можно ставить либо в конец головной, либо в начало хвостовой последовательности на выполнение (ставим в конец головной).

Затем из матрицы  исключаем столбец  и операцию повторяем.

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

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

Процесс изменения состояния объекта называется марковским, если его поведение в будущем зависит лишь в каком состоянии он находится в данный момент и не зависит от предыстории. Состояние объекта описывает набор некоторых параметров, которые называются фазовыми координатами, а процесс изменения состояния представляет из себя некоторую фазовую кривую из некоторого фазового пространства. Если количество состояний в марковском процессе счетно, то такой процесс называется марковской цепью. Вероятность перехода в практическое состояние в некоторый момент времени зависит лишь от того, в каком состоянии находится система в данный момент и как система пришла в это состояние.

 Марковская цепь называется стационарной, если различные моменты времени .

В этом случае марковская цепь характеризуется матрицей перехода

, , .                

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

Матрица переходов имеет вид

Переход системы из одного состояние в другое осуществляется в некоторые дискретные моменты времени

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США