То, что вы хотите сделать, это применить «поиск состояния» .
- Начать с исходного состояния S0.
- Применить преобразование к S0 в соответствии с разрешенными правилами, предоставляя S1. Правила должны позволять создавать только непротиворечивые состояния. Например, правила могут не разрешать генерировать новые ресурсы ex nihilo .
- Проверьте, соответствует ли новое состояние S1 условию «конечного состояния» или «состояния решения», позволяющему вам объявить победу.
- Если нет, применить преобразование к S1, в соответствии с разрешенными правилами, давая S2.
- et c.
Применение преобразований может привести к вам нужно создать состояние, из которого невозможно продвижение, но которое не является «конечным состоянием». Вы застряли. В этом случае сбросьте несколько последних преобразований, вернитесь к более раннему состоянию и попробуйте другие преобразования.
Благодаря этому вы получаете дерево состояний через пространство состояний, когда вы исследуете различные возможности достижения одно из конечных состояний (или единственное конечное состояние, в зависимости от проблемы).
Нам нужно:
- Описание состояния;
- Набор разрешенных преобразований состояния (иногда называемых "операторами");
- Критерий, определяющий, заблокированы ли мы в состоянии;
- Критерий, чтобы решить, нашли ли мы окончательное состояние;
- Может быть, heuristi c, чтобы решить, в каком состоянии попробовать следующее. Если пространство состояний достаточно мало, мы можем попробовать все вслепую, иначе может пригодиться что-то вроде A *.
- Сам алгоритм исследования. Начиная с начального состояния, он применяет операторы, генерирует новые состояния, возвращает обратно в случае блокировки и завершает работу, если достигнуто конечное состояние.
Описание состояния
Состояние (в любом время t) описывается следующей соответствующей информацией:
- количество процессов
- количество ресурсов, несколько одинаковых видов
- информация о том, какие процессы какие ресурсы
- распределили информацию о том, какие процессы запросили какие ресурсы
Как и во всем остальном в информатике, нам нужна структура данных для вышеупомянутого.
Структура данных по умолчанию в Прологе - это term , дерево символов. Чрезвычайно полезный список - это всего лишь еще одно представление определенного дерева. Нужно иметь представление так, чтобы оно говорило с человеком и все еще могло легко управляться кодом Пролога. Итак, как насчет термина, подобного этому:
[process(p1),owns(r1),owns(r1),owns(r2),wants(r3)]
Это выражает тот факт, что процесс p1 владеет двумя ресурсами r1 и одним ресурсом r2 и хочет r3 затем.
Полное состояние представляет собой список, определяющий информацию о каждом процессе, например:
[[process(p1),owns(r1),owns(r1),owns(r2),wants(r3)],
[process(p2),owns(r3),wants(r1)],
[process(p3),owns(r3)]]
Описание оператора
Пролог не допускает "изменяемое состояние", поэтому оператор является преобразование из одного состояния в другое, а не исправление состояния для представления какого-либо другого состояния.
Тот факт, что состояния не были изменены на месте, конечно, очень важен, потому что мы (вероятно) хотим сохранить уже посещенные состояния, чтобы иметь возможность «вернуться» к более раннему состоянию в случае, если мы
Я предполагаю, что могут применяться следующие операторы:
В состоянии StateIn процесс P запрашивает ресурс R, который ему нужен, но не может получить.
request(StateIn, StateOut, P, R) :- .... code that builds StateOut from StateIn
В состоянии StateIn процесс P получает свободный ресурс R.
obtain(StateIn, StateOut, P, R) :- .... code that builds StateOut from StateIn
В состоянии StateIn процесс P освобождает ресурс R, который является владельцем.
free(StateIn, StateOut, P, R) :- .... code that builds StateOut from StateIn
Код был бы написан так, что если бы StateIn были
[[process(p1),owns(r1),owns(r1),owns(r2),wants(r3)],
[process(p2),owns(r3),wants(r1)],
[process(p3),owns(r3)]]
, то free(StateIn, StateOut, p1, r2) создаст StateOut
[[process(p1),owns(r1),owns(r1),wants(r3)],
[process(p2),owns(r3),wants(r1)],
[process(p3),owns(r3)]]
, который становится новым текущим состоянием в поиске l oop. Et c. Et c.
Критерий для определения, заблокированы ли мы в текущем состоянии
Часто «заблокировано» означает, что ни один из операторов не применим к состоянию, поскольку ни для одного из операторов не действуют действительные предварительные условия.
В этом случае критерием представляется «состояние подразумевает тупик».
Таким образом, необходимо написать предикат check_deadlock(StateIn). Он должен проверить описание состояния для любых условий взаимоблокировки (фактически, выполняя свой собственный небольшой поиск).
Критерий, чтобы решить, нашли ли мы конечное состояние
Это не указано. Что является конечным состоянием для этой проблемы?
В любом случае должен существовать предикат check_final(StateIn), который возвращает true, если StateIn действительно является конечным состоянием.
Обратите внимание, что критерий окончательности также может касаться всего пути от начального состояния до текущего состояния. В этом случае: check_path([StartState,NextState,...,CurrentState]).
Алгоритм исследования
Это может быть относительно коротким в Prolog, так как вы получаете бесплатный поиск глубины и обратный трекинг бесплатно, если вы не используете конкретизированный c эвристика и все примитивно.
Все готово!