Методы исследования операций при принятии решений. Бодров В.И - 20 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

1
0
2
3
4
1
2
15
3
0
(2 + 15 +
+ 3 + 0)/4
= 5
5
2
2
3
4
1
5
8
1
(5 + 8 +
+ 1)/3 =
4,7
6,7
–
15
2
4
1
2
2
6
(2 + 2 +
+ 6)/13 =
3,3
18,3
3
3
2
3
1
8
3
2
(8 + 3 +
2)/3 =
= 4,3
7,3
7
4
1
2
6
(6 + 6)/2
= 4
11
10
3
1
3
2
(3 + 2)/2
=
= 2,5
12
5
11
3
1
5
1
(5 + 1)/2
= 3
14
4
6
2
1
2
6
(2 + 6)/2
= 4
10
5
8 1 1 1/1 = 1 9
–
9 – – – 9
Следующей раскрывается вершина , так как она имеет наименьшую оценку Q = 7,3. Расчет
оценок ее дочерних вершин и также приведен в табл. 1.2.
Далее раскрывается вершина , так как ее оценка Q = 10 наименьшая.
Затем раскрывается вершина , последняя вершина заканчивает путь с результатом
Q = 9. Этот результат окончательный: действительно все другие ветви имеют оценку, большую 9.
При нахождении оптимального пути потребовалось раскрыть всего 5 вершин (рассмотрено же 10
вершин). Это меньше, чем в любом из рассмотренных методов, исключая метод ветвей и границ с иде-
альной функцией прогноза ψ
*
(а
ι
).
Метод ветвей и границ находит широкое применение в самых различных задачах принятия ре-
шения и является одним из основных приемов построения алгоритмов искусственного интеллекта
(при доказательстве теорем; играх в шахматы, шашки, карты; в экспертных системах, постановке
диагноза, автоматических приемах обучения и воспитания и др.).
1.5 Поиск на графах
При поиске на графах применяются те же самые алгоритмы: перебор вширь, вглубь, метод равных
цен, метод ветвей и границ, что и при поиске на деревьях. Однако, они усложняются проверкой: не на-
ходится ли "вновь" появляющаяся вершина уже в списке "о" или "з", т.е. не появлялась ли она уже
раньше, при раскрытии предыдущих вершин.
1
142
143
14
1432
14321
14
3
12
13
14
123
124
142
143
1432
1442

Страницы