Алгоритм сопоставления списка желаний

Question

Алгоритм сопоставления списка желаний / наличия

Я внедряю систему торговли товарами на сайте с большим трафиком.У меня есть большое количество пользователей, каждый из которых поддерживает список HAVE и список WANT для ряда конкретных элементов.Я ищу алгоритм, который позволил бы мне эффективно предлагать торговых партнеров на основе ваших HAVE и WANTS, соответствующих их.В идеале я хочу найти партнеров с самым высоким потенциалом взаимной торговли (т.е. у меня есть куча вещей, которые вы хотите, у вас есть куча вещей, которые я хочу).Мне не нужно находить глобальную пару с самым высоким потенциалом (что звучит сложно), просто найти пары с самым высоким потенциалом для данного пользователя (или даже просто некоторые пары с высоким потенциалом, а не глобальный максимум).

Пример:

User 1 HAS A,C WANTS B,D

User 2 HAS D WANTS A

User 3 HAS A,B,D WANTS C

User 1 goes to the site and clicks a button that says 
  "Find Trading Partners" and the top-ranked result is
   User 3, followed by User 2.

Дополнительным источником сложности является то, что предметы имеют разные значения, и я хочу совпасть по максимально возможной сделке, а не по наибольшему числуматчей между двумя трейдерами.Таким образом, в приведенном выше примере, если все элементы стоят 1, а A и D - 10, пользователь 1 теперь сопоставляется с пользователем 2 выше пользователя 3.

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

Кто-нибудь может порекомендовать хороший подход к решению этой проблемы?Я видел такие сайты, как Magic Online Trading League, которые, кажется, решают эту проблему в режиме реального времени.

Answer 1

Вы можете сделать это в O(n*k^2) (n - количество людей, k - среднее количество элементов, которые они имеют / хотят) , сохраняя хеш-таблицы (или, в базе данных, индексы) из всех людей, которые имеют и хотят получить данные предметы, затем выставляют оценки всем людям, у которых есть предметы, которые хочет текущий пользователь, и хотят предметы, которые есть у текущего пользователя. Показать лучшие 10 или 20 баллов.

---

[Edit] Пример того, как это будет реализовано в SQL:

-- Get score for @userid wants
SELECT UserHas.UserID, SUM(Items.Weight) AS Score
FROM UserWants
INNER JOIN UserHas ON UserWants.ItemID = UserHas.ItemID
INNER JOIN Items ON Items.ItemID = UserWants.ItemID
WHERE UserWants.UserID = @userid
GROUP BY UserWants.UserID, UserHas.UserID

Это дает вам список других пользователей и их оценки, в зависимости от того, какие элементы у них есть, что хочет текущий пользователь. Сделайте то же самое для элементов, которые у текущего пользователя есть у других, а затем объедините их как (добавьте баллы или все, что вы хотите) и возьмите верхние 10.

Answer 2

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

Answer 3

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

Это было бы быстро. O (log n) для каждой операции вставки. В худшем случае O (n) для предложения торговых партнеров, но вы связали это временем обработки.

1. Вы уже ведете список элементов на пользователя.
2. Дайте каждому пользователю оценку, равную сумме значений предметов, которые у него есть.
3. Ведение списка пользовательских HAVES и user-WANTS для каждого элемента (@Dialecticus), отсортированных по количеству пользователей. (Вы можете сортировать по требованию или динамически сортировать списки каждый раз, когда пользователь меняет свой список HAVE.)
4. Когда пользователь user1 запрашивает предложенных торговых партнеров
   • Перебирать их элементы item по порядку по значению.
   • Итерация пользователя-ХАЙСА user2 для каждого item, в порядке убывания рейтинга пользователя.
   • Вычислить стоимость сделки для user1 trades-with user2.
   • Запомните лучшую сделку на данный момент.
   • Сохраняйте обработанные хэши пользователей, чтобы избежать повторного вычисления значения для пользователя несколько раз.
   • Завершить, когда у вас закончится время обработки (ваша гарантия в реальном времени).

Сортировка по значению элемента и оценке пользователя - это приблизительное значение, которое делает это быстрым. Я не уверен, насколько это было бы неоптимальным. Есть, конечно, простые примеры, когда это не поможет найти лучшую сделку, если вы не запустите ее до конца. На практике кажется, что это может быть достаточно хорошо. В пределе вы можете сделать его оптимальным, позволяя ему работать до тех пор, пока он не исчерпает списки в шагах 4.1 и 4.2. Есть дополнительные затраты памяти, связанные с инвертированными списками, но вы не сказали, что ограничены в памяти. И, как правило, если вам нужна скорость, вы можете воспользоваться компромиссным пространством для ее получения.

Answer 4

Хорошо, как насчет этого:

Есть в основном гигантские "Бассейны"

Каждый "пул" содержит "секции".Каждый «Пул» предназначен для людей, которые владеют определенным предметом.Каждый раздел предназначен для людей, которые владеют этим предметом и хотят другой.

Что я имею в виду:

Пул A (Для тех, кто запрашивает A)

- Раздел B (Дляте, кто запрашивает A с B)

- Раздел C (для тех, кто запрашивает A с C, даже если они также имеют B)

Пул B

- SectionA

- Секция B

Бассейн C

- Секция A

- Секция C

Каждая секция заполненалюди.«Сделки» будут состоять из одного «Запрошенного» предмета и «Пакета», который вы готовы отдать любому или всем предметам, чтобы получить запрошенный вами предмет.

Каждый «Сделка» рассчитываетсяза пул .... если вам нужен данный предмет, вы идете в пулы предметов, которые вы хотели бы отдать, и он находит раздел, принадлежащий запрашиваемому предмету.

Аналогично, ваша сделка размещается в пулах.Таким образом, вы можете сразу же найти всех подходящих людей, потому что вы точно знаете, какие пулы и ТОЧНО какие разделы искать, сортировка не требуется, как только они вошли в систему.

И тогда возраст будет иметьприоритет, более старые предложения будут выбраны, а не новые.

Answer 5

Я отмечаю товар по буквам, а пользователь по номеру.

• m - количество элементов во всех списках «есть / хочу» (есть или хочу, нет и хочу)
• x - количество пользователей.

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

1 - ABBCDE FFFGH
2 - CFGGH BE
3 - AEEGH BBDF

Для каждой пары пользователей вы генерируете два значения и сохраняете их где-то, вы сгенерируете их только один раз, а затем актуализируете. Сортировка первой таблицы и генерация второй - O(m*x*log(m/x)) + O(log(m)) и потребует O(x^2) дополнительной памяти. Это следующие значения: сколько получит первый пользователь, а сколько - другое (если вы хотите, вы можете изменить эти значения, умножив их на значение определенного элемента).

1-2 : 1 - 3 (user 1 gets 1) - (user 2 gets 3)
1-3 : 3 - 2
2-3 : 1 - 1 

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

• Добавление / удаление элемента - O(m*log(m/x)) (Вы просматриваете список пользователя / хотите и выполняете бинарный поиск в списке есть / хотите каждого пользователя и актуализируете данные)
• Поиск лучшего соединения - O(1) or O(x) (Зависит от того, верен ли результат, сохраненный в кэше, или его нужно обновить. Вы перебираете пары пользователей и делаете с данными все, что хотите, чтобы вернуть пользователю лучшее соединение)

По m/x Я оцениваю количество элементов в списке желаний / иметь одного пользователя.

В этом алгоритме я предполагаю, что все данные не хранятся в базе данных (я не знаю, возможен ли бинарный поиск с базами данных) и что вставка / удаление элемента в списке - O(1).

PS. Извините за плохой английский, и я надеюсь, что я все правильно рассчитал и что он работает, потому что он мне тоже нужен.

Answer 6

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

Answer 7

Просто сделайте это только до н.э.Это решает все проблемы.

Answer 8

Конечно, вы всегда можете разделить систему на три категории;«Хочет», «Хэйвз» и «Открытые предложения».Допустим, пользователь1 имеет элемент A, пользователь2 имеет элемент B & C и обменивает их на элемент A, но пользователь1 все еще хочет элемент D, а пользователь2 хочет элемент E. Таким образом, пользователь1 (предполагая, что он является «владельцем» сделки), помещает запрос,или хотите для пункта D и пункта E, таким образом, предложение остается в силе и заносится в список «Открытые предложения».Если оно не будет принято или отредактировано в течение двух дней, оно будет автоматически отменено.Таким образом, Пользователь3 ищет Элемент F и Элемент G и ищет в «Списке» Элементы F & G, которые разделены между Пользователем1 и Пользователем2.Он понимает, что открытое предложение User1 и User2 включает в себя запросы на элементы D & E, которые он имеет.Поэтому он решает «присоединиться» к операции, и это принимается на их условиях, торгуя и обменивая их между собой.

Допустим, пользователь1 теперь хочет получить элемент H. Он просто ищет в списке «Иметь» для поискаitem, и среди результатов он находит, что User4 обменяет Item H на Item I, который имеет User1.Они торгуют, все хорошо.