Главная > Искусственный интеллект. Методы поиска решений
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

2.4. ЗАПИСЬ В ВИДЕ ГРАФА

В гл. 1 мы использовали граф с целью иллюстрации пространства состояний для игры в пятнадцать. До сих пор наше рассмотрение графов носило интуитивный характер, а в настоящем разделе будут введены некоторые полезные формальные понятия, относящиеся к графам.

Граф состоит из множества (не обязательно конечного) вершин. Некоторые пары вершин соединены с помощью дуг, и эти дуги направлены от одного члена этой пары к другому. Такие графы носят название направленных графов. Если некоторая дуга направлена от вершины к вершине то говорят, что вершина является дочерней вершиной для вершины я», а вершина является родительской вершиной для Может оказаться, что некие две вершины будут дочерними друг для друга; в этом случае пара направленных дуг называется иногда ребром графа. В случае когда граф используется для

представления пространства состояний, с его вершинами связывают описания состояний, а с его дугами — операторы.

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

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

В задачах простейшего типа нам необходимо найти путь (возможно, имеющий минимальную стоимость) между заданной вершиной (представляющей начальное состояние) и другой заданной вершиной (представляющей целевое состояние). Два очевидных усложнения этой простейшей задачи следующие:

Найти путь между вершиной и любым элементом множества вершин

Найти путь между любым элементом множества и любым элементом множества

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

Граф может быть задан как явным образом, так и неявным. При явном задании его вершины и дуги (с соответствующими стоимостями) должны быть перечислены явным образом, скажем, в виде некоторой таблицы. Эта таблица может содержать перечень всех вершин графа, их дочерних вершин и стоимостей всех связанных с ними дуг. Очевидно, что явное задание оказывается практически неприемлемым для больших графов, а для графов, имеющих бесконечное число вершин, оно невозможно.

При неявном способе задания определяется некоторое конечное множество вершин, являющихся начальными вершинами. Кроме того, определяется оператор Г, который, будучи примененным к любой вершине, дает все ее дочерние вершины и стоимости соответствующих дуг. (В нашей терминологии пространства состояний этот оператор «наследования» определяется

как множество операторов, применимых к данному описанию состояния.) Последовательное применение оператора Г к элементам множества к их дочерним элементам и так до бесконечности дает, таким образом, представление для графа, определенного неявно через Г и

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

1
Оглавление
email@scask.ru