7.3. Эвристики

Обсудим более подробно задачи на оптимизацию. Как несложно видеть, эффективность всех отсечений в них далеко не в последнюю очередь определяется тем, какое решение мы уже нашли, т.е. чему у нас равно значение \(best\). Чем лучше у нас \(best\), т.е. чем оптимальнее найденное нами на данный момент решение, тем больше веток будет отсекаться.

Поэтому имеет смысл как можно быстрее получать хорошие решения. Я вижу, в общем-то, три способа это делать:

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

Рассмотрим это по порядку.

7.3.1. Эвристики до перебора

Можно ещё до запуска перебора попробовать найти какое-нибудь решение, причём постаравшись, чтобы оно было не слишком плохое. Т.е. специально перед запуском перебора запустить какой-нибудь быстрый алгоритм, который найдёт какое-нибудь решение. Возможно (даже скорее всего), оно будет неоптимальным (если бы оно всегда было оптимальным, то перебор нам не был бы нужен), но все равно неплохим, позволяя отсекать плохие ветки перебора.

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

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

best:=0;
ob:=b;
for i:=1 to n-2 do begin
    {найдем, какое удаление сейчас дешевле всего}
    min:=inf;       {число, которое больше любого возможного штрафа}
    for j:=2 to n-2 do
        if b[j]*(b[j-1]+b[j+1])<min then begin
           minj:=j;
           min:=b[j]*(b[j-1]+b[j+1]);
        end;
    {и удалим, записав результат сразу в ans}
    best:=best+min;
    ans[i]:=j;
    delete(minj);
end;
b:=ob;

Это пишется в главной программе, перед вызовом \(find(1)\), т.е. перед началом перебора (или ещё лучше это сделать отдельной процедурой и вызвать её до вызова \(find(1)\)). Я сразу сохраняю решение в \(best\) и \(ans\), т.к. это будет то «текущее оптимальное» решение, с которым мы начнём перебор (а раньше в начале перебора у нас не было никакого «текущего оптимального» решения, а \(best\) равнялось какому-нибудь очень большому числу, \(inf\)).

Конечно, нет никакой гарантии, что этот метод даст оптимальное решение; более того, в данной конкретной задаче даже вообще не очевидно, что он даст решение, близкое к оптимуму. Но это в любом случае лучше, чем начинать перебор с \(best=inf\).

Задача 7.19:

Приведите пример, когда этот алгоритм находит неоптимальное решение.

Задача 7.20:

Напишите эту программу полностью. Сравните её эффективность с программой без предварительного жадного поиска решения.

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

(Это не значит, что жадный алгоритм никогда не является точным решением задачи; бывают задачи, которые точно решаются жадностью. Но переборные задачи обычно точно жадностью не решаются).

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

Если делать на олимпиаде нечего, можно заниматься придумыванием кучи эвристик, реализовать их все (!) и программно выбирать, какая лучше. В итоге ваша программа будет делать следующее: запускает первую эвристику, смотрит ответ на неё. Запускает вторую, смотрит её ответ, если он лучше, то заменяет «текущий оптимальный» ответ \(best\) и текущее решение \(ans\) на ответ второй эвристики. Потом запускает третью и т.д. Тем самым в начале перебора \(best\) будет лучшим из всего, что на этом тесте смогли сделать эвристики.

Задача 7.21:

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

Как правило, эвристики работают намного быстрее перебора, и поэтому обычно можно написать много эвристик, и это по крайней мере не ухудшит программу. Кроме того, и при написании эвристик не стоит очень оптимизировать их; например, удалять элементы в порядке убывания можно, выбирая на каждом шагу минимальный из оставшихся элементов заново (фактически, сортируя выбором главного элемента), а не сортируя их предварительно qsort’ом и т.п. — все равно, если \(N\) большое, то у вас нет шансов пройти тест, потому что перебор не успеет отработать, а на маленьких \(N\) все равно, какую сортировку применить.

Другое дело, что увеличивать количество эвристик опасно, т.к. (как всегда) есть риск где-нибудь ошибиться. Поэтому всегда надо делать разумное количество эвристик и разумно распределять своё время: может быть, стоит все-таки придумать нормальное решение или, если уж и не успеете решить задачу по-нормальному, то хотя бы проверьте, что все работает! что вы нигде не наглючили, в т.ч. не забыли ничего откатить в процедуре перебора…

7.3.2. Эвристики во время перебора

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

Например, в нашей любимой задаче про удаление чисел можно в процедуре \(find(i)\) перебирать, какое число мы будем удалять, не просто слева-направо (for j:=2 to nn-1), как было во всех примерах выше, а, например, в порядке убывания. Т.е.: удалить самое большое число. запустить \(find(i+1)\). Восстановить самое большое число, удалить число поменьше, запустить \(find(i+1)\). Восстановить это число и т.д.

Это можно реализовать, заведя массив \(was\) и отмечая в нем, какие числа мы уже пытались на этом уровне рекурсии удалять:

procedure find(i:integer);
var j,k:integer;
    x:integer;
    was:array...
    maxj:integer;
    max:integer;
begin
if nn=2 then begin
   check;
   exit;
end;
fillchar(was,sizeof(was),0);
for k:=2 to nn-1 do begin
      {найдем наибольший из элементов, которые
      еще не пробовали удалять на этом уровне рекурсии}
    max:=0;
    for j:=2 to nn-1 do
        if (was[j]=0)and(b[j]>max) then begin
           max:=b[j];
           maxj:=j;
        end;
      {и попробуем удалить его}
    was[maxj]:=1;
    a[i]:=maxj;
    cur:=cur+b[maxj]*(b[maxj-1]+b[maxj+1]);
    x:=delete(maxj);
      {переберем, что может получиться в этом варианте}
    find(i+1);
      {после этого откатим изменения}
    insert(maxj,x);
    cur:=cur-b[maxj]*(b[maxj-1]+b[maxj+1]);
end;
end;

Обратите внимание, что массив \(was\) выделен в стеке, а не глобальной переменной. Понятно, почему: потому что у каждой \(find\) свой массив \(was\). Когда работает \(find(5)\) (т.е. были вызовы \(find(1)\), \(find(2)\), …, \(find(5)\), и все пять процедур находятся в стеке), то она должна отдельно хранить, кого она использовала; \(find(4)\) (которая только что вызвала \(find(5)\)) — отдельно и т.д. Надеюсь, понятно.

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

Задача 7.22:

Напишите такую программу.

Эти идеи — тоже по сути эвристики, в том смысле, что они тоже никак строго не обосновываются. Есть просто надежда, что они помогут, но не ясно, почему, и не ясно, насколько сильно помогут.

Обратите внимание, что здесь не получится применить несколько эвристик одновременно, поэтому придётся вам выбирать, какой эвристике вы больше доверяете :)

И ещё. Рассмотрим программу, написанную чуть выше, которая в первую очередь удаляет самое большое число. Каким будет решение, для которого она первый раз вызовет процедуру \(check\)? Это будет решение, в котором первым ходом было удалено самое большое число, вторым — самое большое из оставшихся и т.д., т.е. в точности решение, которое нашлось бы одной из рассмотренных в разделе Эвристики до перебора. Там было задание, в котором вы писали эту задачу с четырьмя эвристиками, но теперь первое же найденное перебором решение будет совпадать с решением, найденных одной из них, поэтому эту эвристику можно и не запускать. Если ещё не понятно, почему, то попробуйте понять.

7.3.3. Локальная оптимизация

Эту идею я сам ни разу не применял, пример можете посмотреть в ОНЗИ [1]. Идея состоит в следующем: пусть мы нашли какое-то решение. Попробуем его немного поизменять, вдруг получится лучше. Например, вспомним задачу о паросочетании минимального веса в полном графе. Пусть перебор нашёл некоторое решение. Попробуем, например, всеми возможными способами поменять ребра «крест-накрест». Т.е. перебираем все \(n(n-1)/2\) пар рёбер и для каждой пары рёбер (\(u\)\(v\)) и (\(u'\)\(v'\)), входящих в решение, рассматриваем решение, которое отличается от найденного заменой этой пары рёбер на (\(u\)\(v'\)) и (\(u'\)\(v\)), или что-то типа того: (храним в массиве \(a\) сами ребра)

for i:=1 to n do
    for j:=i+1 to do begin
        {начало первого ребра меняем с началом второго}
        t:=a[i].a;
        a[i].a:=a[j].a;
        a[j].a:=t;
        проверить получившееся решение
        вернуть a назад.
    end;

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

Я не уверен, что это имеет смысл делать здесь. Ещё раз: я сам никогда этого не применял. Поэтому подробности смотрите в ОНЗИ, там это довольно подробно описано. Но, как и со всеми эвристиками, тут нет строгих рассуждений, что лучше, что хуже. Что вам кажется лучше, то и делайте.

Задача 7.23:

Придумайте эвристики до перебора и во время перебора к задаче о паросочетании в произвольном графе (в обоих вариантах: а и б). Напишите полную программу.

[1]Виталий Беров, Антон Лапунов, Виктор Матюхин, Анатолий Пономарев. Особенности национальных задач по информатике.