Можно ли применить алгоритм поиска ширины первого слова к библиотеке boost?

Question

Моя задача - найти кратчайший путь в матрице от одной точки к другой. Можно перемещаться только в таком направлении (UP, DOWN, LEFT, RIGHT).

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 - Destination место (Готово)

0 - свободные клетки (мы можем двигаться через них)

1 - "стены" (мы можем» t перемещаются через них)

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

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

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

Answer 1

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

Красота из Boost Graph Library (и общее программирование в целом) заключается в том, что вам не нужно использовать какую-либо конкретную структуру данных, чтобы воспользоваться данным алгоритмом. Матрица, которую вы предоставили вместе с правилами об обходе, уже определяет график. Все, что необходимо, - это кодирование этих правил в классе признаков, который может использоваться для использования алгоритмов 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. Но сначала давайте определим некоторые из функций и типов, которые нам понадобятся.

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

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 (и, очевидно, t сходите с краев матрицы). Создание такого графа не является тривиальным, но я думаю, что очень полезно понять, как работает библиотека Boost Graph: даже если вы не хотите использовать эту конкретную библиотеку, это хороший пример того, как алгоритмы реализованы в абстракции, чтобы алгоритм применим даже в совершенно непредвиденных ситуациях (ОК, я предвзятый: задолго до того, как Джереми создал библиотеку Boost Graph, я написал дипломную диссертацию примерно примерно так же, и мы придумали практически идентичные абстракции).

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