Вопрос по algorithm, mapping, plot, bipartite – Наилучшее соответствие в двудольном графике (например, сопоставление меток с точками на графике)

4

Я пытаюсь извлечь семантику из графических графиков xy, где точки отображаются, а некоторые или все имеют метки. Метка нанесена «рядом с точкой». так что человек обычно может понять, какой ярлык идет с какой точкой. Например, на этом графике ясно, какая метка (число) принадлежит какой точке (*), и алгоритм, основанный на евклидовом расстоянии, будет работать. (Метки и точки не имеют семантического порядка - например, график рассеяния)

<code> *1
    *2

        *3

      *4
</code>

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

<code>1**2
 **4
 3
</code>

Человек-читатель обычно может определить, какой ярлык связан с каким ярлыком.

Одно решение, которое я бы принял, состояло бы в создании евклидовой матрицы расстояний и перемешивании строк, чтобы получить минимум функции (например, суммированные квадраты расстояний на диагонали или другую эвристику). Во втором примере (с точками, помеченными a, b, c, d по часовой стрелке от угла NW) мы имеем матрицу расстояний (до 1 d.p.)

<code>             a   b   c   d
 1ab2    1  1.0 2.0 2.2 1.4    
  dc4    2  2.0 1.0 1.4 2.2
  3      3  2.0 2.2 1.4 1.0
         4  2.2 1.4 1.0 2.0
</code>

и нам нужно пометитьa1 b2 c4 d3, Обмен строк 3 и 4 дает минимальную сумму диагонали. Вот более сложный пример, в котором простой выбор ближайшего может потерпеть неудачу

<code> *1*2*5
  **4
  3 *6
</code>

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

Если алгоритм является стандартным, я был бы признателен за указатель на Java с открытым исходным кодом (например, математика JAMA или Apache)

ПРИМЕЧАНИЕ: этот ТАК ответСвязывание ближайших точек с дорожкой не совсем подходит в качестве ответа, потому что указан путь через точки.

Ваш Ответ

3   ответа
6

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

Это известная проблема и имеет известный алгоритм под названиемHungarian Algorithm:

From Wiki:

We are given a nonnegative n×n matrix, where the element in the i-th row and j-th column represents the cost of assigning the j-th point to the i-th number. We have to find an assignment of the point to the numbers that has minimum cost. If the goal is to find the assignment that yields the maximum cost, the problem can be altered to fit the setting by replacing each cost with the maximum cost subtracted by the cost.

The algorithm is easier to describe if we formulate the problem using a bipartite graph. We have a complete bipartite graph G=(S, T; E) with n number vertices (S) and n point vertices (T), and each edge has a nonnegative cost c(i,j). We want to find a perfect matching with minimum cost. The Hungarian method is a combinatorial optimization algorithm which solves the assignment problem in polynomial time and which anticipated later primal-dual methods. f

For detailed algorithm and code you can take a look at статья topcoder и этоPDF возможно использовать

Eстьсредства массовой информации файл, чтобы описать это. (Это видео объясняет, почему работает венгерский алгоритм)

algorithm : step 1:- prepare a cost matrix.if the cost matrix is not a square matrix then add a dummy row(column) with zero cost element.

step 2:- subtract the minimum element in each row from all the elements of the respective rows.

step 3:- further modify the resulting matrix by subtracting the minimum elememnt of each column from all the elements of the respective columns.thus obtain the modified matrix.

step 4:- then,draw minimum no of horizontal and vertical lines to cover all zeros in the resulting matrix.let the minimum no of lines be N.now there are 2 possible cases.

case 1 - if N=n,where n is the order of matrix,then an optimal assignment can be made.so make the assignment to get the required solution.

case 2 - if N less than n then proceed to step 5

step 5: determine the smallest uncovered element in the matrix(element not covered by N lines).subtract this minimum element from all uncovered elements and add the same elements at the intersection of horizontal and vertical lines.thus the second modified matrix is obtained.

step 6:- repeat step(3) and (4) untill we get the case (1) of step 4.

step 7:- (to make zero assignments) examine the rows successively untill a row-wise exactly single zero is found.circle(o) this zero to make the assignment.then mark a cross(x) over all zeros if lying in the column of the circled zero,showing that they can't be considered for future assignment.continue in this manner untill all the zeros have been examined. repeat the same procedure for column also.

step 8:- repeat the step 6 succeccively until one of the following situation arises- (i)if no unmarked zeros is left,then the process ends or (ii) if there lies more than one of the unmarked zero in any column or row then,circle one of the unmarked zeros arbitrarily and mark a cross in the cell of remaining zeros in its row or column.repeat the process untill no unmarked zero is left in the matrix.

step 9:- thus exactly one marked circled zero in each row and each column of the matrix is obtained. the assignment corresponding to these marked circle zeros will give the optimal assignment.

Подробности смотрите в вики иhttp://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf

+1 очень полезный ответ и почти наверняка то, что я хочу. Также в статье в Википедии есть реализация Java. peter.murray.rust
2

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

In polynomial time, compute the distance from each label to each point. In a general graph you would have to solve the all-pairs shortest-path problem. Here, as Mikola points out, you can just do it with a doubly nested and use the coordinate geometry: pick either the Euclidean distance or the Manhattan distance.

In polynomial time, find the minimum-cost bipartite matching between points and labels. The solution to this problem will give you a matching between points and labels that minimizes the total distance.

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

Что немного нестандартно, так это если вы обнаружите более двух подходящих двудольных с минимальными затратами. Если это произойдет, вы можете попробовать их все и посмотреть, минимизирует ли одно совпадение сумму расстояний в квадрате. Если естьstill связи, я рекомендую вам считать горизонтальное расстояние немного короче вертикального и снова запустить алгоритм. Если у вас все еще есть связи, возможно, не существует уникального решения, или вы можете захотеть пометить «ярлык справа». как немного "ближе" чем метка слева.

Но когда есть уникальное решение, его должны найти кратчайшие пути из всех пар, за которыми следует двустороннее сопоставление минимальной стоимости.

+1 Я не думал об этом как о двудольном графе - это полезно и применимо к ряду моих проблем peter.murray.rust
@ Микола хорошая точка зрения; Я забыл, насколько регулярны эти графики. Я отредактирую свой ответ.
Минимальное соответствие кажется правильной идеей, но проблема кратчайшего пути всех пар здесь не кажется полезной. Почему бы просто не сделать цикл по всем вершинам / меткам и использовать это, чтобы получить стоимость?
1

решил эту проблему:

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

region growing

Используйте временные списки для точек и меток. Каждый раз, когда вы найдете определенную пару, удалите соответствующую точку и метку. Просто пропустите метку, если имеется более одной ближайшей точки (здесь: метка 2). Решая другие комбинации меток точек (здесь: метка 3), они должны быть сопоставлены в другой итерации.

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

+1 за создание анимированного решения. Я думаю, что это будет работать в некоторых случаях, но не в тех, где работает венгерский метод. peter.murray.rust
если метка 2 ближе к точке метки 3, чем к точке метки 2 ... что происходит?
@amink Я предполагаю, что это никогда не должно происходить. Если фактическая точка метки 3 ближе всего к метке 2, то она принадлежит метке 2. Мой алгоритм говорит, что иLaw of Proximity в человеческом познании тоже.

Похожие вопросы