Есть ли разница между вырезкой и поиском в графике?
Основанные на графике методы использовались для проблем сегментации медицинских изображений. Каждый пиксель (воксель в 3D) на изображении представлен узлом на графике, а ребра соединяют соседние узлы. Кроме того, добавлены два узла, а именно источник и приемник. Стоимость определяется для каждого узла (кроме источника и приемника), на основании которого вычисляется минимальный закрытый набор затрат. Этот набор соответствует границе (поверхность в 3D), которая отделяет узлы, принадлежащие источнику, от узлов, принадлежащих приемнику. Обычно эта граница дает требуемую сегментацию. Подробности в этой статье.
Я видел довольно много работ, использующих этот подход, но некоторые называют их методом поиска графа ( Гарвин и др.), В то время как другие называют их разрезом графа ( Каба и др.). После прочтения эти работы кажутся очень похожими.
Есть еще одна работа, которая подразумевает разницу между поиском по графу и вырезкой из графика, но даже после прочтения этой работы я не могу понять разницу.
Может кто-нибудь уточнить разницу, если есть?
2 ответа
Поиск в графе - это любой способ обхода графа.
Вырезание графа - это алгоритм разбиения графа, который назначает метки для определения минимального разреза. Чтобы сделать это, он должен пройти по графику, выполнить поиск по графику.
Я думаю, что статья Гарвина и др. (Поиск по графику), на которую вы ссылались, использует необычную терминологию. Насколько я могу судить по просмотру статьи, "поиск в графе" должен означать, что "мы ищем набор вершин в графе, чтобы минимизировать некоторую функцию стоимости". (Но используя это слабое понимание, почти любой алгоритм графа можно назвать "поиском графа"). Алгоритм, который они используют для этого поиска, такой же, как алгоритм вырезания графика:
Затем было найдено замкнутое множество с минимальной стоимостью путем вычисления минимального сечения в тесно связанном графе.
Так что я думаю, что вы правы, они на самом деле имеют в виду график вырезать здесь. Но если вы читаете термин "поиск в графе" в другом месте, это может означать что-то совершенно другое (например, поиск кратчайшего пути в графе)