Главная > Системы искусственного интеллекта
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
След.
Макеты страниц

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

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

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

5.7.3. Третий способ решения

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

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

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

Восемь ферзей. Третий вариант

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

(см. скан)

(см. скан)

КОНЕЦ третьего варианта алгоритма для задачи о восьми ферзях. Последнинй вариант алгоритма позволяет улучшить качество решения настолько, что случай обычной шахматной доски может быть обработан вручную целиком всего за несколько часов. Продемонстрируем, с какой скоростью поисковое пространство может быть проверено с помощью данного метода. Во-первых, отметим, что совершенно не обязательно начинать рассмотрение с первой горизонтали и первого ферзя. Итак, начнем, например, с четвертой горизонтали. Допустим, что на некотором этапе поиска мы решаем, можно ли расположить первого ферзя на пересечении вертикали с и горизонтали IV, а второго

Рис. 5.15 а. Задача о восьми ферзях.

на пересечении вертикали и горизонтали III: На рис. 5.15 а представлена шахматная доска, на которой отмечены соответствующие запреты и импликации. Значения степеней свободы для оставшихся горизонталей соответственно равны 4, 3, затем 3, 4, 5 и, наконец, 4. Для вертикалей степени свободы равны: . Таким образом, одним из трех рядов, обладающих наименьшей степенью свободы, является горизонталь V; место для третьего ферзя мы будем искать именно на ней. Если мы решим поместить третьего ферзя в вертикали а (в первой свободной клетке данной горизонтали), наша шахматная доска примет вид, представленный на рис. 5.156.

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

Итак, одна из свободных клеток на вертикали — клетка (VII, — заставляет нас вернуться назад, поскольку она налагает запрет сразу на обе оставшиеся клетки в вертикали е. Следовательно, при данном расположении размещение четвертого

ферзя является вынужденным. Так как при этом блокируется одна из двух свободных клеток в вертикали размещение пятого ферзя в клетке (VIII, е) также неизбежно.

Рис. 5.156. Задача о восьми ферзях (продолжение).

Рис. 5.16. Полное решение. Цифры в кружках обозначают местоположение ферзя; цифры в квадратиках — вынуж денное местоположение ферзя.

Клетка, (II, Ь) уже была обязательной, а клетка (VII, h) становится таковой. Эти два вынужденных значения неизбежно приводят

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

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

Рис. 5.17. Невозможность продолжения поиска после выбора местоположения третьего ферзя.

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

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

Вернемся еще раз назад. Последний вариант размещения третьего ферзя при фиксированном положении ферзей 1 и 2 — йлетка (V, g). В этом случае мы получаем несколько горизонталей со степенью свободы, равной 2. Если поместить ферзя 4 на горизонтали II в клетке (II, Ь), то размещение ферзя 5 в

Рис. 5.18. Завершение поиска после выбора местоположения для двух ферзей.

клетке (VII, а) является вынужденным, но эти два варианта закрывают все возможности в последней вертикали. Выбор другой свободной клетки на горизонтали влечет за собой такие размещения и но тогда все остальные клетки уже оказываются под запретом, и мы не можем получить решения (рис. 5.18). Итак, мы доказали, что после осуществления двух первых выборов (VI, с) и (III, существует единственное решение, и оно соответствует частичному решению Данная конфигурация была выбрана произвольно. Исходя из этого, мы можем оценить усилия, необходимые для построения всех решений. Как только мы фиксируем положение первого ферзя, для второго — если он стоит на соседней горизонтали — остается пять возможностей (кооме случаев, когда первый стоит в одной из крайних клеток: тогда для второго существует шесть вариантов размещения). Учитывая симметрию шахматной доски (а следовательно, и симметричность решений по отношению к вертикальной оси симметрии), мы можем рассматривать только те четыре случая, когда первый ферзь стоит слева от данной оси. Так что в конечном счете нам придется вести поиск, примерно эквивалентный тому, который мы провели для конфигурации (IV, с), (III, f); число вариантов равно Следует отметить, что это число невелико. Итак, при удачных критериях выбора и эффективном управлении импликациями и возвратами для вывода о пригодности данной конфигурации

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

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

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

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

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