суббота, 11 апреля 2009 г.

Обобщение фундаментальных алгоритмов.

Иногда удивляюсь, насколько время меняет подходы к реализации и использованию фундаментальных алгоритмов, которым много лет!

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

Как решалась эта задача раньше (точнее как я ее решал в ВУЗ-е): брались классы-вершины и классы-ребра, и под них писался алгоритм. Я использовал алгоритм Дейкстры для случаев с неотрицательными весами (кстати, алгоритму 50 лет в этом году!). Естественно, что использование реализации алгоритма под конкретные типы невозможно для других типов вершин и ребер. О реюзе даже речи не идет.

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

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

И тут приходят делегаты. Нет, не делегаты. Если рассматривать делегаты как аналог указателям на методы, то с приходом указателей на метод и делегатов в этом плане ничего не изменилось. А вот когда пришли (в .net) лексические замыкания в совокупности с анонимными методами, вот тогда, видимо, и наступил переломный момент. Наступил, но не все его заметили. Лямбда-выражения подлили масла в огонь, и теперь использовать обобщенные методы одно удовольствие (хотя сами лямбды в обобщении алгоритма участия не принимают):
var edjes = new[]
{
  new { s = 1, t = 2 },
  new { s = 2, t = 3 },
  new { s = 3, t = 4 },
  new { s = 4, t = 5 },
  new { s = 2, t = 4 },
  new { s = 2, t = 1 },
};

var pathes = Dijkstra.ComputePathes(
  1,
  v => edjes.Where(_ => _.s == v),
  (v, e) => e.t,
  e => 1);

CollectionAssert.AreEqual(
  new[] { new { s = 1, t = 2 } },
  pathes(2).ToArray());
Это фрагмент одного из тестов алгоритма нахождения кратчайших путей. Нетрудно заметить, что граф представлен набором направленных ребер-являющих собой переход от одной целой вершины к следующей. Первым аргументом задается исходная вершина, далее метод, возвращающий набор исходящих дуг для указанной вершины, далее функция перехода, которая по вершине и исходящей из нее дуге возвращает вершину, в которую ведет дуга. Последний аргумент - функция веса. Вполне можно было приписать к ребрам поле веса и возвращать его для каждого ребра. Обращаю внимание на то, что для использования алгоритма с конкретными (с дуба упавшими) типами данных практически ничего писать не пришлось!

Вот реализация алгоритма Дейкстры:
class Dijkstra
{
  public static Func<V, IEnumerable<E>> ComputePathes<V, E>(
      V s,
      Func<V, IEnumerable<E>> adjacentEdjes,
      Func<V, E, V> dest,
      Func<E, double> weight,
      IEqualityComparer<V> equalityComparer)
  {
      if (adjacentEdjes == null)
      {
          throw new ArgumentNullException("adjacentEdjes");
      }

      if (dest == null)
      {
          throw new ArgumentNullException("dest");
      }

      weight = weight ?? new Func<E, double>(_ => 1.0);
    
      equalityComparer = equalityComparer ?? EqualityComparer<V>.Default;

      var distancesFromS = new Dictionary<V, double>(equalityComparer) { { s, 0 } };

      // метод нахождения расстояния от указанной вершины до s.
      double tmp;
      Func<V, double> distanceFromS = v =>
          distancesFromS.TryGetValue(v, out tmp) ? tmp : double.PositiveInfinity;

      // запомненные пути (из какой вершины по какому ребру пришли в данную вершину).
      var sourceVertices = new[] { s }.ToDictionary(
          x => x,
          x => new { source = x, edje = default(E) },
          equalityComparer);

      // множество не вершин, кратчайший путь до которых не вычислен.
      var F = new HashSet<V> { s };

      while (F.Count > 0)
      {
          // Найти вершину с минимальным расстоянием от s
          var w = F.Aggregate(
              F.First(),
              (c, v) => distanceFromS(c) < distanceFromS(v) ? c : v);

          F.Remove(w);

          foreach (E e in adjacentEdjes(w))
          {
              V v = dest(w, e);
              double distanceToV = distanceFromS(w) + weight(e);
              if (distanceFromS(v) > distanceToV)
              {
                  // обновить расстояние.
                  distancesFromS[v] = distanceToV;
                  F.Add(v);
                  // запомнить откуда пришли.
                  sourceVertices[v] = new { source = w, edje = e };
              }
          }
      }

      // вернуть метод вычисления последовательности ребер.
      return x =>
      {
          var edges = new List<E>();

          while(sourceVertices.ContainsKey(x) && !equalityComparer.Equals(x, s))
          {
              var w = sourceVertices[x];
              edges.Add(w.edje);
              x = w.source;
          }

          edges.Reverse();
          return edges;
      };
  }
}
На удивление - это всего лишь один метод, который довольно хорошо коррелирует с псевдокодом по ссылке выше. Потому комментировать я его не буду за исключением нескольких моментов:

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

Второе - реализация не оптимальна в плане алгоритмической сложности. За скоростью не гнался. Кое-что можно улучшить при поиске вершины с минимальным весом из множества F, для этого можно использовать сортирующий контейнер с логарифмическим доступом, и что важно, ключами должны быть вершины, а не расстояния от исходной вершины до вершины, способ сравнения - по расстояниям от исходной вершины. Чтобы использовать существующие сортирующие контейнеры, требуется класс компарера, который будет принимать словарь весов, либо адаптер делегата к компареру. Я решил не связываться.

Третье - алгоритм вычисляет кратчайшие пути до всех достижимых вершин графа. Возвращать единственный путь не целесообразно, т.к. в этом случае для вычисления путей до нескольких вершин придется запускать поиск многократно. Вместо кратчайшего пути до указанной вершины алгоритм возвращает метод, который строит кратчайший путь до указанной методу вершины с помощью накопленной во время поиска информации о переходах. Еще кое-что: код
double tmp;
Func<V,double> distanceFromS = v =>
    distancesFromS.TryGetValue(v, out tmp) ? tmp : double.PositiveInfinity;
содержит потенциальный баг. А именно, переменная tmp должна быть объявлена внутри анонимного метода! Я же использовал замыкание переменной tmp только для того, чтобы сэкономить на фигурных скобках и ключевом слове return, которые пришлось бы добавить, помести я переменную в тело метода. Полагаю, что этот код не будет распараллеливаться.

Вернемся к обсуждению прелестей обобщенных реализаций алгоритмов.
  • Отсутствие каких либо ограничений на типы данных позволяет оперировать вершинами V и ребрами E, ничего не требуя от них. Это здорово! Вершинами может быть все: числа, строки, сайты, города... Это позволяет тестировать реализацию алгоритма на элементарных типах данных. Задача, под которую я писал эту реализацию, обладает довольно сложновообразимыми типами данных. Тесты алгоритма на этих типах очень непрозрачны и нелаконичны. Обобщение позволило мне писать простые и понятные тесты (часть теста в начале поста). В качестве бонуса для себя я получил возможность реюза этого алгоритма тут же не отходя от кассы, при решении сопутствующей задачи анализа возможностей переходов по ребрам из первой задачи. Во втором случае не требовался кратчайший путь, достаточно было лишь установления факта существования пути на других типах данных, но писать специальный алгоритм для решения этой задачи стимула небыло.
  • Отсутствие ограничений на типы позволило так же сконцентрироваться именно на реализации фундаментального алгоритма, а не на его поведении в рамках конкретной системы. Создание вершин, перебор ребер-переходов, вычисление весов - все это осталось за бортом. Реализация алгоритма приобрела вид, очень близкий к псевдокоду на википедии. Если кому-то придется поддерживать этот алгоритм, он без труда это сделает, даже не вникая в задачу, в рамках которой используется этот алгоритм.
  • Задание управляющих методов делегатами позволяет гибко настраивать работу алгоритма, позволяет использовать преимущества лексических замыканий при обращении к алгоритму (делегаты тут и не причем, я хотел сказать функциональные типы, но в C# за них делегаты).
  • Анонимные типы и лексические замыкания позволили вернуть накопленные в ходе расчета данные в удобном для использования виде. Не потребовалось описывать дополнительные типы для хранения результатов счета.
P.S. И кто сказал, что библиотеки для работы с графами должны быть Объектно-Ориентированными?

1 комментарий: