Соответствует ли этот сценарий каким-либо известным проблемам информатики? - PullRequest
Новая
       12

Соответствует ли этот сценарий каким-либо известным проблемам информатики?

0 голосов
/ 07 сентября 2011

Я работаю над проблемой в области интеграции данных опросов, но ее проще описать искусственной аналогией.Поскольку установка немного затянулась, я с самого начала задам свои вопросы:

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

  2. Если нет, то какие подходы вы могли бы предложить?Я никого не прошу решить проблему;скорее, просто надеясь быть направленным в одном или нескольких многообещающих направлениях.

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

Atoms in the universe: a b c d.

Ecosystem X
    creature x1
        molecule 1: a b
        molecule 2: c
        molecule 3: d
    creature x2
        molecule 4: a b c
        molecule 5: d
    creature x3
        molecule 6: a b c d

Ecosystem Y
    creature y4
        molecule 7: a b
        molecule 8: c
        molecule 9: d
    creature y5
        molecule 10: a b
        molecule 11: c d

Учитывая две экосистемы, моя задача состоит в том, чтобы создать «спаривания».Спаривание состоит из набора молекул (или комбинаций молекул) из одной экосистемы, которые отображаются на эквивалентные молекулы (или комбинации молекул) из другой экосистемы.Эквивалентность определяется основными атомами.Как и у существ, спаривания нежизнеспособны, если каждый из двух наборов молекул (по одному из каждой экосистемы) не использует все атомы ровно один раз.Вот некоторые (не все) пары из приведенного выше примера: 

# A direct mapping from the molecules of creature x1 to those of y4.
m1 = m7
m2 = m8
m3 = m9

# As above, but substitute m10 for m7.
m1 = m10
m2 = m8
m3 = m9

# We can combine molecules.
m4 = m7 + m8
m5 = m9

# Another combination.
m1      = m10
m2 + m3 = m11

В реальной проблемной области может быть от 2 до 100 атомов в игре (с соответствующим разнообразием размеров молекул) ипара дюжин существ на экосистему.Кроме того, две экосистемы могут не давать жизнеспособных пар.В этом случае моему приложению Python в конечном итоге потребуется предложить приблизительные пары (список комбинаций молекул, которые объединяются, а затем список отставших от каждой экосистемы).

1 Ответ

2 голосов
/ 07 сентября 2011

Это пахнет чем-то вроде проблемы покрытия .

  1. Индекс (хэш) молекул по их подмножествам атомов, производя отображения вроде {a, b} -> {m1, m7, m10}
  2. Выбратьэкосистемы и, перечисляя разделы, обнаруживают и индексируют подмножества атомов с их расширениями других экосистем (такими как {a, b, c} -> {{{a, b}, {c}}} для m4 = m7 + m8.)
  3. Отбрасывают любые подмножества атомов, которые не имеют расширения (пониманиечто m1 = m7 считается расширением.)
  4. Из остатка перечислите разделы алфавита (совокупность всех атомов.) Из шага 3 мы знаем, что любые обнаруженные разделы будут переводиться в потенциально много разделов вдругая экосистема, с помощью уже рассчитанного отображения.
  5. Выберите другую экосистему и повторите шаги 2-4.
  6. Дедупликация результатов (возможно, путем их накопления в хэш-наборе.)
  7. Расширение разделов, состоящих из подмножеств атомов, обратно в наборы молекул с отображением, созданным на шаге 1.

Одна часть, котораяeems tricky off-hand - это подпрограмма, которая принимает коллекцию подмножеств и перечисляет конструктивные разделы некоторого целевого набора.В зависимости от точной семантики, это может быть NP-hard.

...