Метод проб и ошибок программирование

Время на прочтение
9 мин

Количество просмотров 8.6K

Перевод статьи Coding A.I. Techniques in Elixir: The Generate and Test Algorithm

В последнее время, я работал над проектом в области И.И. (искусственный интеллект). По моим ожиданиям, работа над этим проектом займет ещё значительное время. Цель состояла в том, чтобы написать проект 100% на языке Elixir, но прежде чем я смог принять это решение, мне нужно было удостовериться, что я смогу реализовать некоторые из самых популярных решений в области И.И. на Elixir. На протяжении нескольких дней я изучал некоторые из наиболее эффективных техник, которые применяют исследователи в области И.И. для решения проблем программными средствами.

В этой статье я сделаю краткое объяснение метода, называемого алгоритмом генерации и испытаний — Generate and test algorithm (он же проб и ошибок), а затем я буду использовать вариацию этого метода для решения простой задачи с использованием языка программирования Elixir.

В И.И. есть много областей, из которых наиболее известными на сегодняшний день являются машинное обучение, обработка естественного языка (natural language processing) и робототехника. Тем не менее, для меня моя любимая дисциплина в И.И. известна как автоматизированные рассуждения — Automated reasoning. Программа, которую я продемонстрирую попадет в эту область И.И.

Проблема

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

Решение

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

1. Сформировать возможное решение
2. Проверка того, что получено ожидаемое решение
3. Если решение верно, возвращаем его и завершаем работу, в противном случае повторяем шаги с 1 по 3

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

Код

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

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

defmodule SumAndTest do
  @moduledoc """
  This script is designed to show the functionality of the AI Algorithm
  that is known as Generate and Test. It will produce the results to a
  addition question and answer whether or not the answer is even.
  """

• Elixit организует код с помощью модулей. СЛАВА БОГУ, НИКАКИХ КЛАССОВ!!!

• @moduledoc является макросом для добавления комментария, который позволяет дать краткое описание того, для чего предназначен данный модуль.

Мы должны ответить на вопрос: «Является ли результат х + у четным числом?». Так что давайте двигаться далее и создадим функцию, которая содержит этот вопрос.

  defp addition_question(first_numbaer, second_number) do
    "Is the result of #{first_numbaer} + #{second_number} even?"
  end

• Мы определяем функцию addition_question с двумя аргументами

• Интерполяция в строке в Elixir имеет тот же синтаксис, что и в Ruby

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

  defp say_answer(true) do
    "YES! Even result found."
  end

  defp say_answer(false) do
    "No."
  end

• Когда передан аргумент true, мы говорим «да», когда false, мы просто говорим «нет»

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

Мы создали возможность отвечать да и нет. Но что будет инициировать этот ответ? Нам необходимо определить, является ли результат на суммы 2 чисел четным числом. Создадим соответствующую функцию.

  defp even?(number) when is_number(number) do
    if rem(number, 2) == 0, do: true, else: false
  end

Так же возможно переписать тело функции просто как rem(number, 2) == 0, что само по себе возвращает true или false (прим. пер.).

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

• В Elixir имеется аналог тернарного оператора в одну строку

• rem() является функцией Elixir, принадлежащий к модулю Kernel (ядро). Она определяет остаток от деления нацело.

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

  defp generate(amount_of_questions) when is_number(amount_of_questions) do
    generate(0, amount_of_questions)
  end

  defp generate(accumulator, amount_of_questions) when amount_of_questions >= 1 do
    question = addition_question(Enum.random(1..100_000), Enum.random(1..100_000))
    build_list(question)
    generate(accumulator + 1, amount_of_questions - 1)
  end

  defp generate(total, 0) do
    IO.puts "#{total} addition questions generated."
    :ok
  end

• Вы растеряны? Не нужно. В Elixir обычно не используются циклы. Функции являются вашим основным инструментом. В случае необходимости повторно выполнять действия используют рекурсию.

• С помощью сопоставления аргументов (pattern matching) мы можем в методе generate принять необходимое количество вопросов и передать его в версию того же метода, но с двумя аргументами. Первый аргумент имеет значение 0, потому что это, где начальное значение количества уже сгенерированных вопросов.

• Второй вариант функция generate вызывается только тогда, когда она получает два аргумента второй из которых не меньше 1.

• Функция Enum.random принимает заданный диапазон и возвращает случайное число в пределах верхней и нижней границы этого диапазона. Это идеально подходит для нашей системы, мы не знаем, какие числа будут использованы. Это позволит отлично проверить правильность работы нашей системы!

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

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

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

Мы довольно близки к завершению. Но есть еще кое что важное. В функции generate/2 мы вызывали функцию build_list. Почему нам это нужно?

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

Мы создали эти вопросы, но нам нужен способ, чтобы сохранить их, так что система не потеряет их после того, как мы выйдем из функции. Вот где вступают агенты Elixir. Агенты в Elixir позволяют программе удерживать состояние. Это делает отслеживание изменений структуры данных с течением времени независимым. Использование агентов довольно просто, и они могут быть главной причиной, почему Джо Армстронг (создатель Erlang) говорит, что с Erlang и Elixir «Вам не нужна база данных!». Давайте создадим агента, который в начале будет содержать пустой список. Этот список будет хранить наши вопросы.

  defp start_list do
    Agent.start(fn() -> [] end, [name: __MODULE__])
  end

• Мы видим создание агента с двумя аргументами. Первый — функция, которая возвращает пустой список. Второй аргумент представляет собой список ключ-значений (keyword list). Функция получает имя от текущего модуля.

• (ПРИМЕЧАНИЕ) Всегда давайте имена своим агентам!

Здорово! Теперь, когда наш агент имеет возможность инициализации и может содержать состояние, модно двигаться далее и реализовать функцию build_list которая встречалась ранее.

  defp build_list(question) do
    Agent.update(__MODULE__, fn(list) -> [question | list] end)
  end

• Функция принимает один аргумент — вопрос, и на самом деле build_list является оберткой функции Agent.update, которая принимает два аргумента. Первый аргумент является именем агента. Второй аргумент это функция, которая берет текущий список и добавляет текущий вопрос к новой версии списка.

Чтобы увидеть все вопросы, на которые системе необходимо ответить, нужно получить текущее состояние агента. Мы можем просто использовать функцию Agent.get/2. Назовем эту функцию questions.

  defp questions do
    Agent.get(__MODULE__, &(&1))
  end

• Agent.get принимает два аргумента. Название текущего модуля, и короткую версию функции fn(x) -> x end.

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

1. Получить все подстроки содержащте по одному числу из строки вопроса.
2. Преобразовать подстроки в целые числа.
3. Подсчитать сумму.
4. Проверить четная ли сумма.
5. Ответить "Да" или "Нет".

Здесь мы будем использовать pipeline оператор (или оператор конвейера). Этот оператор представляет собой мышечную ткань языка программирования Elixir, и это делает алгоритмы обработки И.И. гораздо нагляднее, чем они в были бы в LISP.

  defp answer_to(question) do
    Regex.scan(~r/(d+) + (d+)/, question, [capture: :all_but_first])
    |> List.flatten
    |> Enum.map(&String.to_integer(&1))
    |> Enum.reduce(0, fn(n, acc) -> n + acc end)
    |> even?
    |> say_answer
  end

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

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

  defp answer_to(question) do
    Regex.scan(~r/d*(d) + d*(d)/, question, [capture: :all_but_first])
    |> List.flatten
    |> Enum.map(&String.to_integer(&1))
    |> Enum.reduce(0, fn(n, acc) -> n + acc end)
    |> even?
    |> say_answer
  end

Или используя модуль Bitwise можем учитывать только последнюю цифру числа в двоичной системе (1 или 0). Оператор ^^^ вычисляет побитовую операцию XOR своих аргументов.

  use Bitwise

  defp answer_to(question) do
    Regex.run(~r/(d+) + (d+)/, question, [capture: :all_but_first])
    |> List.flatten
    |> Enum.map(&String.to_integer(&1))
    |> Enum.reduce(0, fn(n, acc) -> acc ^^^ (n &&& 1) end)
    |> even?
    |> say_answer
  end

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

  defp display_answer_for(question) do
    IO.puts(question)
    IO.puts(answer_to(question))
  end

• IO является главным модулем для работы стандартного ввода/вывода для устройств.

Наконец-то! Мы в последней части системы. Нам нужен способ, для того чтобы вызвать весь этот процесс. Нам нужна функция запуска, которая выполняет следующие действия…

1. Вызвать `start_list`, чтобы запустить агент.
2. Затем сгенерировать определенное количество вопросов. Давайте начнем с 20-ти.
3. Для каждого вопроса мы должны показать ответ на этот вопрос.

Вот как эта функция может выглядеть.

  def start do
    start_list
    generate(20)
    Enum.each(questions, &display_answer_for(&1))
  end

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

Мы готовы! Что происходит, когда мы вызываем SumAndTest.start? Система производит 20 случайных вопросов с соответствующими ответами. Смотрите вывод ниже!!

$ iex
Erlang/OTP 18 [erts-7.3] [source] [64-bit] [smp:8:8] [async-threads:10] [hipe] [kernel-poll:false] [dtrace]

Interactive Elixir (1.3.1) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> c("sum_and_test.ex")
[SumAndTest]
iex(2)> SumAndTest.start
20 addition questions generated.
Is the result of 31956 + 95609 even?
No.
Is the result of 56902 + 37929 even?
No.
Is the result of 63154 + 23758 even?
YES! Even result found.
Is the result of 22268 + 66438 even?
YES! Even result found.
Is the result of 76068 + 36127 even?
No.
Is the result of 14158 + 84195 even?
No.
Is the result of 55174 + 13171 even?
No.
Is the result of 53028 + 68694 even?
YES! Even result found.
Is the result of 82027 + 39083 even?
YES! Even result found.
Is the result of 32349 + 70547 even?
YES! Even result found.
Is the result of 41416 + 37714 even?
YES! Even result found.
Is the result of 91326 + 32635 even?
No.
Is the result of 42663 + 21205 even?
YES! Even result found.
Is the result of 90054 + 71218 even?
YES! Even result found.
Is the result of 38305 + 69972 even?
No.
Is the result of 59014 + 3954 even?
YES! Even result found.
Is the result of 55096 + 34449 even?
No.
Is the result of 89363 + 16018 even?
No.
Is the result of 60760 + 12438 even?
YES! Even result found.
Is the result of 10044 + 47646 even?
YES! Even result found.
:ok

Вывод

Это, вероятно, самый простой из всех алгоритмов искусственного интеллекта. Его простота это то почему я решил написать об этом алгоритме в моей первой статье на «Automating the Future». Я бы рассматривал возможность использования метода проб и ошибок, если бы я имел дело с проблемой, в которой фигурируют только небольшое количество возможных исходов.

Автор: Quentin Thomas

исходный код

Вставка, поиск, удаление

Приведем рекурсивную функцию поиска в бинарном дереве поиска (эта и следующая функция добавлены в класс, реализующий бинарные деревья поиска):

has (x: G): BOOLEAN
        — Есть ли x в каком-либо узле?
    require
        argument_exists: x /= Void
    do
        if x ~ item then
            Result := True
        elseif x < item then
            Result := (left /=Void) and then left.has (x)
        else — x > item
            Result := (right /= Void) and then right.has (x)
        end
    end
        

Алгоритм имеет сложность O(h), где h – высота дерева, что означает O(log n) для полного или почти полного дерева.

В этом варианте приводится простая нерекурсивная версия алгоритма:

has1 (x: G): BOOLEAN
        — Есть ли x в каком-либо узле?
    require
        argument_exists: x /= Void
    local
        node: BINARY_TREE [G]
    do
        from
            node := Current
        until
            Result or node = Void
        invariant
    — x не находится в вышерасположенных узлах на нисходящем пути от корня
        loop
            if x < item then
                node := left
            elseif x > item then
                node := right
            else
                Result := True
            end
        variant
            — (Высота дерева) – (Длина пути от корня к узлу)
        end
    end
        

Для вставки элемента можно использовать следующую рекурсивную процедуру:

put (x: G)
        — Вставка x, если он не присутствует в дереве.
    require
        argument_exists: x /= Void
    do
        if x < item then
            if left = Void then
                add_left (x)
            else
                left.put (x)
            end
        elseif x > item then
            if right = Void then
                add_right (x)
            else
                right.put (x)
            end
        end
    end
        

Отсутствие ветви else во внешнем if отражает наше решение не размещать дублирующую информацию. Как следствие, вызов put с уже присутствующим значением не имеет эффекта. Это корректное поведение («не жучок, а свойство»), о чем и уведомляет заголовочный комментарий. Некоторые пользователи могут, однако, предпочитать другой API с предусловием, устанавливающим not has(x).

Нерекурсивная версия остается в качестве упражнения.

Возникает естественный вопрос: как написать процедуру удаления – remove(x:G)? Это не так просто, поскольку нельзя просто удалить узел, содержащий x, если только это не лист дерева. Удаление листа сводится к обнулению одной из ссылок – left или right. Удаление произвольного узла приводило бы к нарушению инварианта бинарного дерева поиска.

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

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

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

• в левом поддереве – это элемент с максимальным значением (такой элемент является листом дерева или имеет только одну связь);
• в правом поддереве – это элемент с минимальным значением.

Если перемещаемый элемент является листом дерева, то после перемещения соответствующий узел удаляется. Если элемент имеет одну ссылку, то ссылка родителя перемещаемого элемента связывается с потомком перемещаемого элемента, тем самым перемещаемый узел исключается из дерева. Инвариант при этих операциях сохраняется.

Предположим, что удаляется корень дерева – remove (35). Тогда в корень можно поместить либо элемент 23 (из левого поддерева), либо элемент 41 из правого поддерева.

Подобно поиску и вставке процесс удаления должен выполняться за время O(h), где h – это высота дерева. Процедура удаления остается в качестве упражнения.

Время программирования!

8.5. Перебор с возвратами и альфа-бета

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

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

Бедственное положение застенчивого туриста

При необходимости достижения некоторой цели путешествия в незнакомом городе как к последней надежде можно прибегнуть к перебору с возвратом. Скажем, Вы находитесь в точке А (главная станция Цюриха) и хотите добраться до точки В (между главными зданиями ЕТН и Университета Цюриха):

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

На каждом этапе вы проверяете отрезки улиц, начиная с севера и двигаясь по часовой стрелке. Первая попытка приводит в точку 1. Здесь вы понимаете, что это не отвечает вашей цели, так как далее все возможные пути ведут на запад, то есть это тупик и нужно возвращаться назад в исходную точку А. Далее вы испытываете следующий выбор, приводящий в 2. Здесь есть несколько возможностей, и вначале вы проверяете путь, ведущий в 3, который оказывается тупиком, так что приходится вернуться в точку 2.

Если все «правильные» (не ведущие на запад) пути в 2 были исследованы и приводили к тупикам, то из 2 пришлось бы вернуться в точку А. Но в данной ситуации из 2 есть еще не исследованный выбор, ведущий в точку 4.

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

find ( p: PAT H): PATH
            — Решение, если оно существует, начинающееся в P.
    require
            meaningful: p /= Void
    local
            c: LIST [CHOICE]
    do
        if p.is_solution then
            Result := p
        else
            c := p.choices
            from c.start until
                (Result /= Void) or c.after
            loop
                Result := find ( p + c)
                c.forth
            end
        end
    end
        

Здесь применяются следующие соглашения. Выборы на каждом шаге описываются типом CHOICE (во многих ситуациях для этой цели можно использовать тип INTEGER). Есть также тип PATH, но каждый путь path – это просто последовательность выборов, и p + c – это путь, полученный присоединением c к p. Мы идентифицируем решение с путем, приводящим к цели, так что find возвращает PATH. По соглашению, если find не находит решения, то возвращается void. Запрос is_solution позволяет выяснить, найдено ли решение. Список выборов – p.choices, доступных из p, является пустым списком, если p – это тупик.

Для получения решения достаточно использовать find(p0), где p0 – начальный пустой путь.

Как обычно, Result инициализируется значением Void. Если в вызове find(p) ни один из рекурсивных вызовов на возможных расширениях p + c не вырабатывает решения (в частности, если таких расширений вообще нет, поскольку p.choices пусто), то цикл завершится со значением c.after, и тогда find(p) вернет значение Void. Если это был начальный вызов find(p0), то процесс завершается, не достигнув положительного результата, в противном случае рекурсивно включается следующий вызов, пока не будет получен результат или не будут перебраны все возможности.

Если один из вызовов находит, что p является решением, то p возвращается в качестве результата, и, подымаясь вверх по цепочке вызовов, результат возвращается, поскольку Result /= Void является условием выхода.

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

Дальнейшее обсуждение также показывает, как улучшить эффективность данного алгоритма, удаляя излишние записи. Например, фактически нет необходимости передавать путь как явно заданный аргумент, освобождая пространство в стеке вызовов. Вместо этого p может быть атрибутом, если мы добавим p:= p+x перед рекурсивным вызовом и p:= p.head после него (где head вырабатывает копию последовательности с удаленным последним элементом). Мы разработаем общий каркас, позволяющий безопасно выполнять такую оптимизацию.

Правильная организация перебора с возвратом

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

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

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

Пути [1, 2, 3, 4], [1, 2, 3, 4, 2, 3, 4], [1, 2, 3, 4, 2, 3, 4, 2, 3, 4] и так далее являются эквивалентными. Пример, демонстрирующий нахождение маршрута без циклов, состоял в важной рекомендации – «никогда не уезжайте на запад, молодой человек». Конечно, этот совет не может служить общей рекомендацией и связан лишь с конкретной проблемной ситуацией. Чтобы справиться с циклом, необходимо сохранять информацию о ранее посещенных точках и игнорировать любой путь, ведущий к такой точке.

Перебор с возвратами и деревья

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

Мы можем представлять всю карту города подобным образом: узлы отражают местоположение указанных на карте точек, дуги представляют отрезки улиц, соединяющих точки. В результате получается граф. Граф может быть деревом только в том случае, если в нем нет циклов. Если граф не является деревом, то на его основе можно построить дерево, называемое остовным деревом графа, которое содержит все узлы графа и некоторые из его дуг. Для этого используются методы, упомянутые ранее, а также существует соглашение, позволяющее избежать цикла (никогда не ходите на запад) или построения путей из корня и исключающее любую дугу, которая ведет к ранее встречающемуся узлу. Вышеприведенное дерево является остовным деревом для части нашего примера, включающего узлы А, 1, 2, 3 и 4.

Для такого представления нашей задачи в виде дерева:

• решением является узел, удовлетворяющий заданному критерию (свойство, ранее названное is_solution, адаптированное для применения к узлам);
• выполнение алгоритма сводится к префиксному обходу дерева (самый левый в глубину).

В нашем примере этот порядок приведет к посещению узлов А, 1, 2, 3, 4.

Это соответствие указывает, что «Префиксный обход» и «Перебор с возвратами» основаны на одной и той же идее: всякий раз, когда мы рассматриваем возможный путь, мы разматываем все его возможные продолжения – все поддеревья узла, – прежде чем обращаемся к любому альтернативному выбору на уровне, представляющем непосредственных потомков узла. Например, если А на предыдущем рисунке будет иметь третьего потомка, то обход не будет его рассматривать, прежде чем не обойдет все поддеревья 2.

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

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

Мину. Математическое программирование.Теория и алгоритмы.- М.: Наука, 1990.]. Например, если функции f,gi – линейные и S Zn , тозадача (1.1) относится к классу задач целочисленного линейного программирования.В отдельный класс выделим задачи комбинаторной оптимизации. Они возникают,например, при проектировании информационно-управляющих систем реального времени.В постановке любой задачи комбинаторной оптимизации присутствуют некоторыеобъекты, которые требуется определенным образом разместить, упорядочить или разбитьна группы.

В этом случае множество S состоит из решений X, описывающихвсевозможные размещения/упорядочивания/разбиения на группы исходно заданныхобъектов. Математически множество S описывается набором ограничений, которыетребуют согласованного изменения значений элементов X: изменение значения одного изэлементов для сохранения корректности решения может требовать принятия конкретныхзначений ряда других элементов.

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

Для каждойработы задано время ее выполнения. Расписание определено, если для каждой работы3задан процессор, на котором она выполняется и порядковый номер выполнения работы напроцессоре (работа не может начать выполняться, пока не выполнены все работы сменьшими номерами). Требуется построить расписание выполнения работ на минимальнонеобходимом числе процессоров время выполнения которого не превосходит исходнозаданный директивный срок. Для этой задачи значением функции f является числопроцессоров, функция g задает ограничение: время выполнения расписания не должнопревышать директивный срок. Множество S определяется следующими ограничениями:1.

Каждая работа должна быть назначена на процессор для выполнения.2. Каждая работа должна быть назначена лишь на один процессор.3. Частичный порядок, заданный на множестве работ должен быть сохранен врасписании.4. Расписание должно быть беступиковым. Условием беступиковости расписанияявляется ацикличность отношения частичного порядка в расписании.Если эти условия не выполняются, то мы не можем вычислить время выполнениярасписания.Если мы изменяем расписание путем перемещения работы с процессора А напроцессор В, то номера работ на процессоре А больше перемещаемой должныуменьшиться на 1, а номера работ на процессоре В, которые должны выполняться послеперемещаемой работы должны увеличиться на 1.1.2. Понятие «сложных» задач условной оптимизации. Проблемыприменения оптимальных и эвристических алгоритмов, использующихаприорно известные свойства о целевой функции и функцияхограниченийПод сложными задачами условной оптимизации будем понимать задачи (1.1) длякоторых отсутствует априорная информация о функциях f,gi и множестве S, котораяможет быть использована для организации поиска оптимального решения, или сложностьполучения этой информации неприемлема.

Можно выделить следующие основныеособенности сложных задач условной оптимизации:1. Функций f,gi могут быть операторами, заданными правилами/алгоритмами ихвычисления, т.е. их аналитическая структура не может быть использована дляорганизации поиска оптимального решения задачи (1.1).2.

Негладкий характер функций f,gi.43. Отсутствие информации о производных функций f,gi или их производные неявляются непрерывными.4. Множество S может быть компонентно разнородным: S = SR  SZ  SF  SKS, т.е.различные компоненты вектора X могут принадлежать подмножествам множествадействительных чисел (R), целых чисел (Z), функций (F) и комбинаторных структур (KS).Указанные выше особенности делают проблематичным применение оптимальныхи эвристических методов, использующих некоторые априорно известные свойства задачидля организации поиска оптимального решения.

При больших размерности и/илиразмерах задачи (1.1) методы полного перебора допустимых решений также оказываютсянеприемлемыми по сложности.Идея о целесообразности случайного поведения, при наличии неопределенности,т.е. отсутствии достаточной информации, которая может быть использована дляорганизации поиска оптимального решения/поведения, впервые в четкой форме быласформулирована У.Р. Эшби в работе [У. Росс Эшби. Конструкция мозга.- М.:, ИЛ, 1962.] иреализована в известном гомеостате (гомеостат Эшби). Применительно к сложнымзадачам условной оптимизации, алгоритм поиска оптимального решения долженопираться на метод проб и ошибок.

Только такой процесс позволяет извлечь информацию,необходимую для организации поиска решения. Метод проб и ошибок основан напонятии случайного эксперимента: случайного выбора значений компонентов вектора X,что дает возможность получить информацию о функциях f,gi и множестве S, котораяможет быть использована для организации поиска решения сложной задачи условнойоптимизации.Наиболееширокоприменяемымиподходамикпостроениюалгоритмовоптимизации опирающихся на метод проб и ошибок являются следующие:алгоритмы случайного поиска (ненаправленного, направленного,направленного с самообучением) [ Л.А.

Растригин. Статистические методы поиска.- М.:Наука, 1968.],алгоритмы имитации отжига [Уоссермен Ф. Нейрокомпьютерная техника. Теория ипрактика.- М.: Мир, 1992. – 240с.],генетические и эволюционные алгоритмы [Holland J.N. Adaptation in Natural andArtificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.],муравьиные алгоритмы [Dorigo M.

Optimization, Learning and Natural Algorithms. // PhDThesis. Dipartimento di Elettronica, Politechnico Di Milano, Milano. 1992.], [Штовба С.Д.Муравьиные алгоритмы: теория и применение// Программирование. 2005. №4.].51.3. Классические задачи комбинаторной оптимизации1.3.1. Задача коммивояжераЗадачу коммивояжёра можно представить в виде нахождения пути на графе.Вершины графа соответствуют городам, а ребра между вершинами являются путямисообщения между этими городами.

Граф является полносвязным, т.е. между любымидвумя вершинами есть ребро. Каждому ребру можно сопоставить вес, который можнопонимать, например, как расстояние между городами, время или стоимость поездки.Маршрутом (гамильтоновым циклом) называется маршрут на таком графе, в которыйвходит по одному разу каждая вершина графа. Задача заключается в отысканиикратчайшего маршрута. Длина маршрута определяется как сумма весов входящих внего ребер. Маршрут может быть описан циклической перестановкой номеров городовJ  ( j1 , j2 , jn , jn1 ) , где ji — номер города находящийся в i –ой позиции перестановки.Пространством поиска решений является множество перестановок n городов, таких,что все j1 , j2 , jn разные и j1  jn1 .Существует несколько частных случаев общей постановки задачи, в частности:симметричная задача коммивояжера,асимметричная задача коммивояжера,метрическая задача коммивояжера.В симметричной задаче коммивояжера задается неориентированный граф и всепары ребер между одними и теми же вершинами имеют одинаковый вес, т.е.

длялюбого ребра (i,j) wij  w ji .В асимметричной задаче коммивояжера задается ориентированный граф и дугимежду одними вершинами могут иметь разный вес, т.е. wij  w ji .Симметричная задача коммивояжера является метрической, если для весов ребервыполняется правило треугольника: wij  wik  wkj . То есть прямой путь междулюбыми двумя вершинами не длиннее любого обходного пути.В практических задачах, если между некоторыми вершинами не существует ребер,то они искусственно добавляются в граф и им присваиваются большие веса. Из-забольшого веса такое ребро никогда не попадает в оптимальный маршрут и маршруты,близкие по длине к оптимальному маршруту.6Данная задача принадлежит к классу NP-трудных задач и часто используется кактестовая задача для сравнения качества работы различных алгоритмов опирающихсяна метод проб и ошибок.Математическиематематическойформулировкиформулировкизадачиопределяетсямогутбытьклассомразными.алгоритма,Выборкоторыйпредполагается использовать для решения задачи.1.3.2.

Задача о рюкзакеИмеется рюкзак объемом b и набор n различных товаров. Для каждого товара iзаданы: объем ai и стоимость ci. Требуется упаковать рюкзак так, чтобы суммарнаястоимость упакованных товаров была максимальной и их суммарный объем непревышал объем рюкзака b.Математически эту задачу можно записать следующим образом:nmax( ci  xi )Xi 1na  xi 1iibi  1,, n : xi  0 или 1Если товар упакован в рюкзак, то xi=1, если нет xi=0.Если все коэффициенты ai целые числа и b целое число, то задача является NPтрудной. Если все коэффициенты ai вещественные, то задача может быть решенажадным алгоритмом сложности O(n·log n). Обе задачи о рюкзаке обладают свойствомоптимальности для подзадач. Вынув товар i из оптимально загруженного рюкзака,получим решение задачи о рюкзаке с максимальным объемом b-ai и набором из n-1товара.

То есть, жадный алгоритм может быть построен как для непрерывной, так идискретной задачи. Вычислим относительную стоимость всех товаров в расчете наединицу объема ci ai . Оптимальный жадный алгоритм для непрерывной задачизаключается в следующем: сначала в рюкзак укладывается по максимуму товар ссамой дорогой относительной стоимостью. Если товар закончился, а рюкзак незаполнен, то укладывается следующий по относительной стоимости товар, затемследующий, и так далее, пока не набран вес b .

В [Кормен Т., Лейзерсон Ч., Ривест Р.Алгоритмы: построение и анализ. М.: МЦНМО, 2000.] показано, что аналогичный жадныйалгоритм может не получать оптимум в дискретной задаче о рюкзаке.71.3.3. Задачи построения расписаний и их классификацияОпишем общую задачу построения расписания согласно [Теория расписаний ивычислительные машины.

Под ред. Э.Г. Коффмана. М.: Наука, 1984. 334 с.]. Модель в рамках котороймогутбытьсформулированымногиезадачипостроениярасписанийзадаетсясовокупностью моделей ресурсов, системы заданий (работ) и меры оценки расписаний.Ресурсы. В большинстве моделей ресурсы состоят просто из набора процессоров P.В наиболее общей модели еще имеется набор дополнительных типов ресурсов R,некоторое подмножество которых используется на протяжении всего времени выполнениязадания на некотором процессоре. Общее количество ресурса типа Ri задается целымположительным числом.Система работ может быть определена через T,  , [τji], {Rj}, где:T={T1,T2,…,Tn} — набор работ подлежащих планированию; — заданное на T отношение частичного порядка, которое определяетограничение на последовательность выполнения работ.