Математика/ 5. Математическое моделирование

к.ф.-м.н Искакова А.С., Арсеньева Д.В.

Евразийский национальный университет имени Л.Н. Гумилева

Школа-лицей №1 города Астаны, Казахстан

Условие существования седловой точки в матрице знаний по прецедентам

Из теории игр известно следующее.

Если , то матрица знаний имеет седловую точку .

Это позволяет легко находить седловые точки матрицы.

Теорема. Если два любых значений любых ситуационных векторов не совпадают, то матрица знаний не имеет седловой точки.

Доказательство. Очевидно, что для любого ситуационного вектора , так как для любых , справедливо . И следовательно, . Таким образом, седловой точки не существует.

Теорема доказана.

Приведем примеры существования седловой точки.

Пример. Рассмотрим модель движения транспортных средств в определенном направлении со средней скоростью 60км/ч. Предложим, что в данном направлении возможны 4 остановки на «красный» сигнал светофора. То есть имеем ситуационный вектор{x₁, x₂,…, x₄}, где x_n – время «зеленого» сигнала светофора № n.

Пусть для этого класса наблюдались три прецедента d₁, d₂ и d₃, каждый из которых применялся в трех разных) случаях:

d₁- достоверное движение с остановкой при скорости движения от предыдущего светофора равного 60 км/ч,

d₂- возможно движение с остановкой при скорости движения от предыдущего светофора равного 60 км/ч,

d₃- достоверное движение без остановки при скорости движения от предыдущего светофора равного 60 км/ч.

Матрица знаний в данном случае имеет вид, представленный в таблице 1.

Таблица 1.

№	Координаты ситуационного вектора				Прецеденты
1	15	10	15	15	d1
2	15	25	40	55	d2
3	15	15	15	15	d3

Тогда, согласно алгоритмам Минимакс и Максимин выбора предпочтительного прецедента получим решения, представленные в таблицах 2-3.

Таблица 2.

№	Координаты ситуационного вектора				max	Min
1	15	10	15	15	15	15
2	15	25	40	55	55	-
3	15	15	15	15	15	15

Таблица 3.

№	Координаты ситуационного вектора				min	Max
1	15	10	15	15	10
2	15	25	40	55	15	15
3	15	15	15	15	15	15

Как видно, из таблицы 2, при использовании алгоритма Минимакс наиболее предпочтительными прецеденты является прецедент d₁ (достоверное движение с остановкой при скорости движения от предыдущего светофора равного 60 км/ч) и d₃ (достоверное движение без остановки при скорости движения от предыдущего светофора равного 60 км/ч).

Аналогично, из таблицы 3, при использовании алгоритма Максимин наиболее предпочтительными прецеденты является прецедент d₂ (возможно движение с остановкой при скорости движения от предыдущего светофора равного 60 км/ч) и d₃ (достоверное движение без остановки при скорости движения от предыдущего светофора равного 60 км/ч).

Следовательно, из условия существования седловой точки, матрица знаний, представленная в таблице 1, имеет седловую точку, при котором наиболее предпочтительным прецедентом является прецедент d₃ (достоверное движение без остановки при скорости движения от предыдущего светофора равного 60 км/ч).

Литература

1. Prokhorov M.D., Fedunov B.E., 2010. Conclusion on the precedent of knowledge bases of onboard intelligent systems, placed on board anthropocentric objects. Journal of Artificial Intelligence and Decision Making, 2010/03: 62-73.

2. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр: Учебное пособие для университетов. – М: Высшая школа, Книжный дом «Университет», 1998. -304 с.

3. Искакова А.С. Теория игр. Учебное пособие. - Астана: ЕНУ имени Л.Н.Гумилева, 2007 - 54 с.

4. Блекуэлл Д., Гиршик М.А. Теория игр и статистических решений. М.: Изд-во иностр. лит., 1958. – 371с.

5. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр. М.: Наука, 1981. 336 с.

6. Карлин С. Математические методы в теории игр, программировании, экономике.М.:Мир,1964.

7. Льюс Р.Д., Райфа Х.Игры и решения. М.: Изд-во иностр. лит, 1961. 642с.