Информатика и компьютеры
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Переключение алгоритмов

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

Три нижеприведенные задачи были в разное время предложены на Всероссийских и Международных олимпиадах. Формулировки задач немного изменены.

Проводки

В доску вбито N гвоздиков. В нашем распоряжении имеется M проводков. Мы должны припаять концы каждого проводка к двум гвоздикам. Одну пару гвоздиков запрещается соединять дважды. После того, как все сделано, считается, сколько проводков припаяно к каждому гвоздику, полученное число возводится в квадрат и все квадраты суммируются. Требуется таким образом выполнить работу, чтобы получившаяся сумма была максимальной.

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

Пример 1.

N = 5, M = 4

Два возможных решения:

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

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

В первом решении степени вершин: 4, 1, 1, 1, 1. Сумма их квадратов равна 20.

Во втором решении степени вершин: 3, 2, 2, 1, 0. Сумма их квадратов равна 18.

Лучшим оказывается алгоритм, опирающийся на первую эвристику.

Пример 2.

N = 5, M = 6

Два решения, которые основываются на вышеупомянутых эвристиках, дают следующие картинки.

В первом решении степени вершин: 4, 3, 2, 2, 1. Сумма их квадратов равна 34.

Во втором решении степени вершин: 3, 3, 3, 3, 0. Сумма их квадратов равна 36.

Лучшим оказывается алгоритм, опирающийся на вторую эвристику.

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

Проход в метро

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

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

Требуется определить, за какое наименьшее время все студенты окажутся в метро.

Введем следующие обозначения.

n – количество студентов,

t1, t2, … tn – время прохода через контроль каждого студента.

Ясно, что решение зависит от очередности прохода студентов через контроль и их возвращения.

Пример 1.

n = 4

t1 = 4 мин. , t2 = 8 мин., t3 = 9 мин., t4 = 10 мин.

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

Итак, сначала он ведет второго и возвращается. Время: 8 + 4 = 12 мин.

Переход с третьим и возврат требуют 9 + 4 = 13 мин.

И последнего он переводит за 10 мин.

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

Пример 2.

n = 4

t1 = 4 мин. , t2 = 5 мин., t3 = 9 мин., t4 = 10 мин.

Отличие от предыдущего примера минимально. Теперь применение нашей эвристики дает следующий результат

Перевод второго и возврат. 5 + 4 = 9 мин.

Переход с третьим и возврат требует 9 + 4 = 13 мин.

И последнего он переводит за 10 мин.

Результат: 32 минуты.

А теперь применим другую, тоже естественную, но немного более «хитрую» эвристику. Заметим, что основные потери времени происходят во время перехода самых медленных студентов. А может быть, надо, чтобы такие студенты шли вместе? Тогда времена их прохода совместятся и потери уменьшатся. Чтобы обеспечить такую тактику, отправим сначала через контроль, как и раньше, самых быстрых студентов, затем один из них возвратится и пошлет двух медленных. После них второй студент возвратится и вместе с первым пройдут в метро. Назовем такую эвристику «совмещением тормозов». В нашем примере она дает следующий результат.

Переход первого и второго, возврат первого: 5 + 4 = 9 мин.

Переход третьего и четвертого: 10 мин.

Возврат второго: 5 мин.

И последний переход первого и второго: 5 мин.

Результат: 29 минут.

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

При совмещении общая потеря времени составит
t2 + t1 + tn + t2 + t2.

Без совмещения: t2 + t1 + tn + t1 + tn–1.

Разница составит: 2t2 – t1 – tn–1. (*)

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

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

Если студентов меньше четырех, то самый быстрый проводит остальных.

Если студентов не меньше четырех, то считаем разницу (*). Если она отрицательна, то организуем «совмещение тормозов» и продолжаем решать задачу рекурсивно с меньшим количеством студентов, иначе применяем первую эвристику.

Коррозия металла

Для хранения двух агрессивных жидкостей A и B используется емкость с многослойной перегородкой, которая изготавливается из имеющихся N листов. Для каждого листа i (i = 1, ..., N) известно время его растворения жидкостью A – ai и жидкостью B – bi . Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа. Требуется спроектировать такую перегородку, время растворения которой было бы максимальным.

Как решать эту задачу? Перебор, очевидно, можно применить только для очень небольших N.

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

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

Пусть у нас всего два листа и время растворения их жидкостями A и B, соответственно равны a1 , a2 и b1 , b2. Следующие эвристические соображения совершенно естественны: если a1 > a2, то первый лист лучше ставить слева, а если b1 > b2, то первый лист лучше ставить справа. А, если выполнено и то и другое? Возникает идея искать характеристику, учитывающую обе возможности и устанавливающую между ними разумный компромисс. После некоторого раздумья такие характеристики находятся.

Первая – упорядочение производить по убыванию разности ai – bi.

Вторая – упорядочение производить по убыванию отношения ai / bi.

Третья – если максимальное из всех времен (и ai и bi) оказывается bi, то ставим i-ый лист последним, иначе – первым. Последняя характеристика оказывается наилучшей в хорошо известном алгоритме Джонсона решения задачи двух станков. Так, на чем остановиться? А не надо выбирать! Пусть программа рассчитает все три варианта и выберет наилучший. Даже то, что им всегда окажется второй вариант, не должно нас останавливать. Пусть будет выбор, так надежнее. А то, что второй вариант действительно оптимален – это совсем не простой теоретический результат.

Контрольное задание

Реализуйте предложенные алгоритмы решения задач в виде программ.

Добавить комментарий


Защитный код
Обновить

Google