Круговое соответствие. PHP / MySql

Question

Привет, мне нужна помощь в следующем сценарии в php. У меня есть БД с пользователями, у каждого пользователя есть ID, have_card и want_card. Я знаю, как сделать прямое соответствие (один пользователь торгует с другим пользователем). Но если нет прямого совпадения, но есть круговой обмен, такой как:

У пользователя # 1 есть карточка A, которая хочет карточку B

Пользователь № 2 имеет карту B, которая хочет карту C

Пользователь № 3 имеет карту C, которая хочет карту A

В этом сценарии нет прямого совпадения между двумя пользователями. Но если:

Пользователь # 1 отдает свою карту Пользователю # 3

Пользователь № 3 отдает свою карту Пользователю № 2

Пользователь # 2 отдает свою карту Пользователю # 1

Все счастливы.

Вся информация, с которой я должен начать, - это пользователь № 1, как мне найти пользователя № 2 и пользователя № 3?

Спасибо всем за ваши ответы.

Answer 1

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

Это именно то, что вы хотите.

Вот объяснение того, как TradeMaximizer работает . Он использует алгоритм Дейкстры и косые кучи , чтобы найти минимальные подходящие решения (т. Е. Меньший круг предпочтительнее большего круга).

Конечно, это создано в Java, но алгоритмы универсальны, и вы можете воссоздать его по мере необходимости, особенно если вы понимаете, что он делает и почему.

Answer 2

Вот как бы я это сделал: Создайте рекурсивный алгоритм, подобный этому:

1 возьми одного пользователя, посмотри что он хочет

2 найти другого пользователя, у которого есть то, что он хочет

- if user two wants, what user one has, everything is fine an we're done
- if not, continue

3 найти другого пользователя, у которого есть то, что хочет два пользователя

- if user three wants, what user one has, everything is fine and we're done
- if not, continue ...

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

Answer 3

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

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

В моем сценарии нужные книги находились в отдельной таблице от книг, которые были у пользователей. Надеюсь, вы сможете увидеть логику в этом запросе:

$query = "SELECT 
        A.Owner_ID as Owner_1, C.Owner_ID as Owner_2, E.Owner_ID as Owner_3 
    FROM
        E_User_Books_Have as A, E_User_Books_Have as C, E_User_Books_Have as E,
        E_User_Books_Needed as B, E_User_Books_Needed as D,E_User_Books_Needed as F

    WHERE 
        A.Book_ID=D.Book_ID AND
        C.Book_ID=F.Book_ID AND
        E.Book_ID=B.Book_ID AND 
        A.Owner_ID='$ME' AND B.Owner_ID='$ME' AND A.ID='$ID'AND 
        C.Owner_ID=D.Owner_ID AND  
        E.Owner_ID=F.Owner_ID AND
        C.Owner_ID!='$ME' AND
        E.Owner_ID!='$ME'";

Answer 4

Может быть, это:

Поиск возможных первых совпадений (пользователи, которым нужен пользователь карты # 1)

select name from user where has in (select wants from user where name = '1');

Выполните итерацию этих совпадений и попробуйте найти недостающую ссылку:

select name from user where name in (select name from user where has in (select wants from user where name = <match>));