Как найти цепочки пар?

Попала ко мне задача:
1. есть человек, у которого 3-хкомнатная квартира. Он ее хочет продать и купить 2 квартиры по 1 комнате + взять деньги.
2. Есть человек, который просто продает 1-комнатную квартиру.
3. Есть человек, который продает 2-хкомнатную квартиру
4. Есть человек, который просто продает 1-комнатную квартиру, доплачивает и покупает 2-хкомнатную.
А теперь надо составить цепочку из всех этих людей так, чтобы все поучаствовали в сделке и все остались довольны. Вопрос в том, что есть объем покупателей и продавцов, сравнимый с avito и риелтерское агенство, которому надо окучить (в идеале) всех людей. Т.е. надо составлять кратчайшие пары, можно составлять цепочки из 3-4 покупателей, лишь бы максимальный охват был. Прямым перебором будет невероятно долго. Как лучше решить эту задачу?
  • Вопрос задан
  • 1199 просмотров
Пригласить эксперта
Ответы на вопрос 6
Кратчайшие графы и максимальный охват взаимоисключающие вещи имхуется мне.
Ответ написан
begemot_sun
@begemot_sun
Программист в душе.
Задача похожа на клиринговую, только с более широким набором условий.
Задача о клиринге, это когда есть ситуация:
А должен Б. Б должен В. В должен А.

Задача клиринга найти среди множества долгов агентов такие цепочки и максимально сделать взаимозачет между агентами.

В общем плане ваша задача для хороша для Пролога, но там он потонет сам по себе в комбинаторной сложности и не выдаст результат + описание правил еще то занятие.
Ответ написан
webinar
@webinar
Учим yii: https://youtu.be/-WRMlGHLgRg
Скорее всего надо для каждого требования выбирать формировать массив возможных решений и ранжировать их по разным критериям. Как например это делают сайты авиа билетов по кол-ву пересадок. Тут будет схожий алгоритм.
Прямым перебором будет невероятно долго

Если делать это постоянно - да ресурсоемкая задача, а если при поступления нового предложения, делать для него просчет по всей базе, то вполне нормально.
В момент когда клиент запрашивает цепочку, она уже есть, не надо ее в этот момент рассчитывать.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
@checkifitworththat
import IO с нейросетью достаёт любой кол с сайта в csv и потом в ексел кидай и считать какая цена или профит.
Ответ написан
iCoderXXI
@iCoderXXI
React.JS/FrontEnd developer
А еще часть клиентов будет отказываться от ряда цепочек, так-что невозможно найти одну-единственную и вариантов будет уйма.

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

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы