Можно ли применить алгоритм поиска расширенной библиотеки по ширине к матрице?

Question

Моя задача - найти кратчайший путь в матрице из одной точки в другую. Можно двигаться только в таком направлении (ВВЕРХ, ВНИЗ, ВЛЕВО, ВПРАВО).

0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 0 1 0 1 F 0
0 1 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 S 0 1 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0

S - Начальная точка

F - Место назначения (Финиш)

0 - свободные ячейки (мы можем перемещаться по ним)

1 - "стены" (мы не можем пройти через них)

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

Как я могу выполнить поиск в ширину в моем случае, используя Boost? Как я понял, в ширину первый алгоритм поиска Boost предназначен только для графиков. Я думаю, что не очень хорошая идея преобразовывать матрицу в граф с m*n вершинами и m*(n -1) + (m-1)*n ребрами.

Можно ли применить алгоритм поиска в ширину к матрице (без преобразования его в график) или лучше реализовать собственную функцию поиска в ширину?

Answer 1

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

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

В частности, мы хотим определить специализацию boost::graph_traits<T> для вашего графа.Давайте предположим, что ваша матрица представляет собой один массив int в формате строки.К сожалению, специализация graph_traits для int[N] не будет достаточной, поскольку она не предоставляет никакой информации о размерах матрицы.Итак, давайте определим ваш график следующим образом:

namespace matrix
{
  typedef int cell;

  static const int FREE = 0;
  static const int WALL = 1;

  template< size_t ROWS, size_t COLS >
  struct graph
  {
    cell cells[ROWS*COLS];
  };
}

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

Тип вершины и вспомогательные функции:

namespace matrix
{
  typedef size_t vertex_descriptor;

  template< size_t ROWS, size_t COLS >
  size_t get_row(
    vertex_descriptor vertex,
    graph< ROWS, COLS > const & )
  {
    return vertex / COLS;
  }

  template< size_t ROWS, size_t COLS >
  size_t get_col(
    vertex_descriptor vertex,
    graph< ROWS, COLS > const & )
  {
    return vertex % COLS;
  }

  template< size_t ROWS, size_t COLS >
  vertex_descriptor make_vertex(
    size_t row,
    size_t col,
    graph< ROWS, COLS > const & )
  {
    return row * COLS + col;
  }
}

Типы и функции для обхода вершин:

namespace matrix
{
  typedef const cell * vertex_iterator;

  template< size_t ROWS, size_t COLS >
  std::pair< vertex_iterator, vertex_iterator >
  vertices( graph< ROWS, COLS > const & g )
  {
    return std::make_pair( g.cells, g.cells + ROWS*COLS );
  }

  typedef size_t vertices_size_type;

  template< size_t ROWS, size_t COLS >
  vertices_size_type
  num_vertices( graph< ROWS, COLS > const & g )
  {
    return ROWS*COLS;
  }
}

Тип ребра:

namespace matrix
{
  typedef std::pair< vertex_descriptor, vertex_descriptor > edge_descriptor;

  bool operator==(
    edge_descriptor const & lhs,
    edge_descriptor const & rhs )
  {
    return
      lhs.first == rhs.first && lhs.second == rhs.second ||
      lhs.first == rhs.second && lhs.second == rhs.first;
  }

  bool operator!=(
    edge_descriptor const & lhs,
    edge_descriptor const & rhs )
  {
    return !(lhs == rhs);
  }
}

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

namespace matrix
{
  template< size_t ROWS, size_t COLS >
  vertex_descriptor
  source(
    edge_descriptor const & edge,
    graph< ROWS, COLS > const & )
  {
    return edge.first;
  }

  template< size_t ROWS, size_t COLS >
  vertex_descriptor
  target(
    edge_descriptor const & edge,
    graph< ROWS, COLS > const & )
  {
    return edge.second;
  }

  typedef boost::shared_container_iterator< std::vector< edge_descriptor > > out_edge_iterator;

  template< size_t ROWS, size_t COLS >
  std::pair< out_edge_iterator, out_edge_iterator >
  out_edges(
    vertex_descriptor vertex,
    graph< ROWS, COLS > const & g )
  {
    boost::shared_ptr< std::vector< edge_descriptor > > edges( new std::vector< edge_descriptor >() );

    if( g.cells[vertex] == FREE )
    {
      size_t
        row = get_row( vertex, g ),
        col = get_col( vertex, g );

      if( row != 0 )
      {
        vertex_descriptor up = make_vertex( row - 1, col, g );

        if( g.cells[up] == FREE )
          edges->push_back( edge_descriptor( vertex, up ) );
      }

      if( row != ROWS-1 )
      {
        vertex_descriptor down = make_vertex( row + 1, col, g );

        if( g.cells[down] == FREE )
          edges->push_back( edge_descriptor( vertex, down ) );
      }

      if( col != 0 )
      {
        vertex_descriptor left = make_vertex( row, col - 1, g );

        if( g.cells[left] == FREE )
          edges->push_back( edge_descriptor( vertex, left ) );
      }

      if( col != COLS-1 )
      {
        vertex_descriptor right = make_vertex( row, col + 1, g );

        if( g.cells[right] == FREE )
          edges->push_back( edge_descriptor( vertex, right ) );
      }
    }

    return boost::make_shared_container_range( edges );
  }

  typedef size_t degree_size_type;

  template< size_t ROWS, size_t COLS >
  degree_size_type
  out_degree(
    vertex_descriptor vertex,
    graph< ROWS, COLS > const & g )
  {
    std::pair< out_edge_iterator, out_edge_iterator > edges = out_edges( vertex, g );
    return std::distance( edges.first, edges.second );
  }
}

Теперь мы готовычтобы определить нашу специализацию boost::graph_traits:

namespace boost
{
  template< size_t ROWS, size_t COLS >
  struct graph_traits< matrix::graph< ROWS, COLS > >
  {
    typedef matrix::vertex_descriptor vertex_descriptor;
    typedef matrix::edge_descriptor edge_descriptor;

    typedef matrix::out_edge_iterator out_edge_iterator;
    typedef matrix::vertex_iterator vertex_iterator;

    typedef boost::undirected_tag directed_category;
    typedef boost::disallow_parallel_edge_tag edge_parallel_category;
    struct traversal_category :
      virtual boost::vertex_list_graph_tag,
      virtual boost::incidence_graph_tag {};

    typedef matrix::vertices_size_type vertices_size_type;
    typedef matrix::degree_size_type degree_size_type;

    static vertex_descriptor null_vertex() { return ROWS*COLS; }
  };
}

А вот как выполнить поиск в ширину и найти кратчайшие пути:

int main()
{
  const size_t rows = 8, cols = 8;

  using namespace matrix;

  typedef graph< rows, cols > my_graph;

  my_graph g =
  {
    FREE, FREE, FREE, FREE, WALL, FREE, FREE, FREE,
    WALL, FREE, FREE, FREE, FREE, FREE, FREE, FREE,
    FREE, FREE, FREE, WALL, FREE, WALL, FREE, FREE,
    FREE, WALL, FREE, WALL, FREE, FREE, FREE, FREE,
    FREE, FREE, FREE, WALL, FREE, FREE, FREE, FREE,
    FREE, FREE, FREE, WALL, FREE, FREE, WALL, FREE,
    FREE, FREE, FREE, FREE, FREE, FREE, WALL, FREE,
    FREE, FREE, FREE, FREE, FREE, FREE, WALL, FREE,
  };

  const vertex_descriptor
    start_vertex = make_vertex( 5, 1, g ),
    finish_vertex = make_vertex( 2, 6, g );

  vertex_descriptor predecessors[rows*cols] = { 0 };

  using namespace boost;

  breadth_first_search(
    g,
    start_vertex,
    visitor( make_bfs_visitor( record_predecessors( predecessors, on_tree_edge() ) ) ).
    vertex_index_map( identity_property_map() ) );

  typedef std::list< vertex_descriptor > path;

  path p;

  for( vertex_descriptor vertex = finish_vertex; vertex != start_vertex; vertex = predecessors[vertex] )
    p.push_front( vertex );

  p.push_front( start_vertex );

  for( path::const_iterator cell = p.begin(); cell != p.end(); ++cell )
    std::cout << "[" << get_row( *cell, g ) << ", " << get_col( *cell, g ) << "]\n" ;

  return 0;
}

, который выводит ячейки вдоль кратчайшегоПуть от начала до конца:

[5, 1]
[4, 1]
[4, 2]
[3, 2]
[2, 2]
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[1, 6]
[2, 6]

Answer 2

Вы определенно можете использовать библиотеку Boost Graph для этого! Идея реализации алгоритмов в этой библиотеке состоит в том, чтобы абстрагироваться от любой структуры данных графа и вместо этого работать в терминах итераторов. Например, для перехода от одного узла к другому в алгоритмах используется итератор смежности. Вы бы по сути посмотрели и конкретный алгоритм, например BFS и выясните, какие концепции требует этот алгоритм: в этом случае используемый вами граф должен быть «графом вершинного списка» и «графом инцидентности». Обратите внимание, что это не конкретные классы, а понятия: они определяют, как получить доступ к структуре данных. Алгоритм также принимает ряд дополнительных аргументов, таких как начальный узел и карта свойств , чтобы пометить (покрасить) уже посещенные узлы.

Чтобы использовать алгоритм с вашей матрицей, вы бы предоставили алгоритму "графическое представление" вашей матрицы: узел смежен с его прямыми соседями, если соответствующий сосед не установлен на 1 (и, очевидно, вы не сойти с краев матрицы). Создание такого графика не совсем тривиально, но я думаю, что очень полезно понять, как работает библиотека Boost Graph: даже если вы не хотите использовать эту конкретную библиотеку, это хороший пример того, как алгоритмы реализуются в абстракции, чтобы сделать алгоритм применимым даже в совершенно непредвиденных ситуациях (хорошо, я пристрастен: задолго до того, как Джереми создал библиотеку Boost Graph, я написал дипломную работу примерно об одном и том же, и мы придумали по существу идентичные абстракции).

С учетом всего сказанного, я думаю, что использование поиска в ширину может не стоить усилий, чтобы изучить библиотеку Boost Graph: это такой тривиальный алгоритм, что вы можете захотеть просто реализовать его напрямую. Кроме того, это выглядит как домашнее задание, и в этом случае вы, вероятно, должны реализовать алгоритм самостоятельно. Хотя может быть весьма впечатляющим использование библиотеки Boost Graph для этого, ваш инструктор может не подумать об этом. Что я считаю еще более впечатляющим, так это реализовать BFS в стиле, не зависящем от структуры данных, как это делает библиотека Boost Graph, а затем использовать это. Под руководством библиотеки Boost Graph это определенно выполнимо, даже как упражнение (хотя, вероятно, больше усилий, чем требуется). Кстати, да, я мог бы разместить код, но нет, я не буду. Тем не менее, я рад помочь вам опубликовать конкретные проблемы.