Редактировать расстояние между двумя перегородками

17

У меня есть два раздела [1n] и я ищу расстояние редактирования между ними.

Этим я хочу найти минимальное количество отдельных переходов узла в другую группу, которые необходимы для перехода из раздела A в раздел B.

Например, расстояние от {0 1} {2 3} {4}в {0} {1} {2 3 4}будет два

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

Любая помощь приветствуется

Зенна
источник
5
Какое расстояние вы бы посчитали между {0 1 2 3} и {0 1} {2 3}? Было бы 2? Во-вторых, я не понимаю, почему на графике вообще появляются «графики». Похоже, у вас есть два раздела [n] и вы хотите вычислить расстояние между ними.
Суреш Венкат
Да, было бы два. На самом деле это множественные разбиения на узлах графа (то есть разбиения графа). Это, вероятно, не важно для решения, но это проблема, которую я пытаюсь решить, поэтому я и упомянул ее.
Зенна
3
Если график не имеет значения, удалите все ссылки на «графики» и «узлы» из вашего вопроса; это не помогает, это отвлекает.
Юкка Суомела
Разве расстояние редактирования не может быть определено в терминах расстояния на решетке разбиения?
Тегири Ненаши
@Tegiri - Это действительно геодезическое расстояние на решетке разбиений. К сожалению, вычисление этой решетки для любого набора мощностей, намного превышающего 10, является неразрешимым.
Зенна

Ответы:

21

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

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

Пусть и В = { B 1 , B 2 , . , , , Б л } разбиения числа [ 1 , 2 , . , , , п ] . Также, без ограничения общности, пусть k l (допускается, потому что e d i tA={A1,A2,...,Ak}B={B1,B2,...,Bl}[1,2,...,n]kl ). Тогда пусть B l + 1 , B l + 2 , ..., B k все будут пустым множеством. Тогда максимальное количество вершин, которые не меняются:edit(A,B)=edit(B,A)Bl+1Bl+2Bk

maxfi=1k|AiBf(i)|

где является перестановкой [ 1 , 2 , . , , , к ] .f[1,2,...,k]

Это именно та задача присваивания, где вершинами являются , ..., A k , B 1 , ..., B k, а ребра - пары ( A i , B j ) с весом | A iB j | , Это можно решить за O ( | V | 2 log | V | + | V | | E | ) время.A1AkB1Bk(Ai,Bj)|AiBj|O(|V|2log|V|+|V||E|)

bbejot
источник
Не могли бы вы назвать алгоритм, который на этот раз усложняет, пожалуйста?
D-503
Я считаю, что @bbejot относится к последовательному алгоритму кратчайшего пути (с подпрограммой Дейкстры, реализованной с использованием куч Фибоначчи).
Вэй
Мне понадобилось много времени, чтобы разобрать это, потому что я не математик, но спасибо. Я потратил много времени на поиск, и это было единственное, что я смог найти, чтобы показать, как преобразовать проблему расстояния между разделами в задачу назначения - или в любой алгоритм, который я мог бы вызвать из некоторой библиотеки Python. (Самой сложной задачей для меня было выяснить, как использовать scipy.optimize.linear_sum_assignment, а затем настроить матрицы на основе этих инструкций.)
Зигфрид
Мне нужно было сделать вес отрицательным. В противном случае scipy.optimize.linear_sum_assignment даст мне 0 за все.
Зигфрид
2

Посмотрите на PDF этой статьи

http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.0030160

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

Лучше всего, Роб

обкрадывать
источник
Спасибо, Роб. Однако, если я что-то упускаю, это расстояние редактирования, определенное в терминах разделенных перемещений. Они хорошо изучены, и, как отмечается в статье, изменение информации является теоретико-информационной мерой этого. Однако меня интересуют одноэлементные переходы.
Зенна
1

Капризная идея воскресного утра, которая может быть, а может и не быть правильной:

Wlog, пусть будет разделом с большим количеством множеств, P 2 другой. Сначала назначим попарно разные имена n 1 ( S ) Σ вашим множествам P 1 . Затем найдите наилучшее наименование n 2 ( S ) для множеств P 2 по следующим правилам:P1P2n1(S)ΣP1n2(S)P2

  • для S P 2 смаксимальным S S среди всех S P 1 ; выберите тот, который создает наименьшее количество конфликтов, если возможны несколько вариантов.n2(S):=n1(S)SP2SSSP1
  • n2(S)=n2(S)SSS,n1(S)=n2(S)P1 он разделяет вторые по величине элементы, то есть, конкурирует ли он за имя этого набора.
  • SP1S,S that shares more elements with the respective set whose name they can compete for; the other keeps the formerly conflicting name.
  • Iterate this procedure until all conflicts are resolved. Since P1 does not have less sets than P2, there are enough names.

Now, you can consider the bit strings of your elements wrt either partition, i.e. w1=n1(1)n1(n) and w2=n2(1)n2(n) (with nj(i)=nj(S),iSPj). Then, the desired quantity is dH(w1,w2), i.e. the Hamming distance between the bit strings.

Raphael
источник