Prolog

обнаруживаются раньше более длинных. Дело в том, что для функции  h  условие  h <= h*   выполнено не для всех вершин пространства состояний. Например, для начальной позиции   рис. 12.7 (а)

        h = 4 + 3 * 6 = 22,    h* = 4

С другой стороны, оценка 'суммарное расстояние' допустима: для всех позиций

        сумрасст <= h*

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

Упражнение

12. 2.    Введите в программу поиска с предпочтением, приведенную на рис. 12.3, подсчет числа вершин, порожденных в процессе поиска. Один из простых способов это сделать - хранить текущее число вершин в виде факта, устанавливаемого при помощи assert. Всегда, когда порождаются новые вершины, уточнять это значение при помощи retract и assert. Проведите эксперименты с различными эвристическими функциями задачи 'игра в восемь' с целью оценить их эвристическую силу. Используйте для этого вычисленное количество порожденных вершин.

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

12. 3.    Применение поиска с предпочтением к планированию выполнения задач

Рассмотрим следующую задачу планирования. Дана совокупность задач t₁, t₂, ..., имеющих времена выполнения соответственно T1, Т2, ... . Все эти задачи нужно решить на  m   идентичных процессорах. Каждая задача может быть решена на любом процессоре, но в каждый данный момент каждый процессор решает только одну из задач. Между задачами существует отношение предшествования, определяющее, какие задачи (если таковые есть) должны быть завершены, прежде чем данная задача может быть запущена. Необходимо распределить задачи между процессорами без нарушения отношения предшествования, причем таким образом, чтобы вся совокупность задач была решена за минимальное время. Время, когда последняя задача в соответствии с выработанным планом завершает свое решение, называется временем окончания плана. Мы хотим минимизировать время окончания по всем возможным планам.

На рис. 12.8 показан пример задачи планирования, а также приведено два корректных плана, один из которых оптимален. Из примера видно, что оптимальный план обладает одним интересным свойством, а именно в нем может предусматриваться 'время простоя' процессоров. В оптимальном плане рис. 12.8 процессор  1,  выполнив задачу  t,   ждет в течение двух квантов времени, несмотря на то, что он мог бы начать выполнение задачи  t.

Один из способов построить план можно грубо сформулировать так. Начинаем с пустого плана (с незаполненными временными промежутками для каждого процессора) и постепенно включаем в него задачи

Рис. 12. 8.  Планирование прохождения задач в многопроцессорной системе