ВУЗ:
Составители:
Рубрика:
63
К таким задачам относятся следующие задачи:
задача о восьми ферзях;
переупорядочение кубиков, поставленных друг на друга в виде
столбиков;
головоломка «игра в восемь»;
головоломка о «ханойской башне»;
задача о перевозке через реку волка, козы и капусты;
задача о двух кувшинах;
задача о коммивояжере;
другие оптимизационные задачи.
Со всеми задачами такого
рода связано два типа понятий:
проблемные ситуации;
разрешенные ходы или действия, преобразующие одни проблемные
ситуации в другие.
Проблемные ситуации вместе с возможными ходами образуют
направленный граф, называемый пространством состояний.
Пространство состояний некоторой задачи определяет «правила игры»:
вершины пространства состояний соответствуют ситуациям, а дуги –
разрешенным ходам или действиям, или шагам решения
задачи. Конкретная
задача определяется:
пространством состояний;
стартовой вершиной;
целевым условием или целевой вершиной.
Каждому разрешенному ходу или действию можно приписать его
стоимость. Например, в задаче о коммивояжере ходы соответствуют
переездам из города в город, ясно, что стоимость хода в данном случае – это
расстояние между соответствующими городами.
В тех случаях, когда ход
имеет стоимость, программист заинтересован
в отыскании решения минимальной стоимости. Стоимость решения – это
сумма стоимостей дуг, из которых состоит «решающий путь» – путь из
стартовой вершины в целевую. Даже если стоимости не заданы, все равно
может возникнуть оптимизационная задача: требуется найти кратчайшее
решение.
В представленной в примере 73 программе о N ферзях проблемная
ситуация (вершина в пространстве состояний) описывается в виде списка из
N X-координат ферзей, а переход из одной вершины в другую генерирует
предикат queens, причем начальная ситуация генерируется предикатом range,
а целевая ситуация определяется при помощи предиката attack.
Страницы
- « первая
- ‹ предыдущая
- …
- 61
- 62
- 63
- 64
- 65
- …
- следующая ›
- последняя »
