Попала ко мне задача:
1. есть человек, у которого 3-хкомнатная квартира. Он ее хочет продать и купить 2 квартиры по 1 комнате + взять деньги.
2. Есть человек, который просто продает 1-комнатную квартиру.
3. Есть человек, который продает 2-хкомнатную квартиру
4. Есть человек, который просто продает 1-комнатную квартиру, доплачивает и покупает 2-хкомнатную.
А теперь надо составить цепочку из всех этих людей так, чтобы все поучаствовали в сделке и все остались довольны. Вопрос в том, что есть объем покупателей и продавцов, сравнимый с avito и риелтерское агенство, которому надо окучить (в идеале) всех людей. Т.е. надо составлять кратчайшие пары, можно составлять цепочки из 3-4 покупателей, лишь бы максимальный охват был. Прямым перебором будет невероятно долго. Как лучше решить эту задачу?
надо составлять кратчайшие пары, можно составлять цепочки из 3-4 покупателей, лишь бы максимальный охват был.
Задача, сформулированная таким образом, не является алгоритмической задачей.
Это фуфло какое-то.
Поработайте над формулировкой, прежде чем на публику вываливать.
Наивно предполагать, что та квартира, которую продаёт 2-ой, нужна 1-ому.
Может она далеко от метро / на последнем этаже или в хрущёвке...
А может быть она дороже, чем может себе позволить 1-ый, т.к. он продаёт трёшку под мурманском, а покупает однушку с видом на кремль...
Зачем искать сложную цепочку там, где можно обойтись прямым звеном. Т.е. для п.1 и п.2 достаточно выборки желающих купить 3к и желающих продать 1к. На базе размера «как у авито» уже на этом шаге найдётся масса вариантов, чтобы загрузить обзвоном всё агентство. Пытаться встроить в эту цепочку ещё и звенья с 2к квартирами – пока ненужное усложнение, если есть кандидаты на сделки.
Имхо не продуманы все условия задачи. Есть ещё масса параметров совместимости – район, цена метра, этаж, наличие лифта, возраст дома, и др. – которые дают каждому потенциальному звену сделки (паре куплю–продаю) свой вес несовпадения. И в поиске будет интересовать минимизация этого веса.
Задача похожа на клиринговую, только с более широким набором условий.
Задача о клиринге, это когда есть ситуация:
А должен Б. Б должен В. В должен А.
Задача клиринга найти среди множества долгов агентов такие цепочки и максимально сделать взаимозачет между агентами.
В общем плане ваша задача для хороша для Пролога, но там он потонет сам по себе в комбинаторной сложности и не выдаст результат + описание правил еще то занятие.
Для начала нужно формализовать задачу. А ваша задача состоит в том, что имеется набор правил и условий перехода с неизвестными операторами :)
А имеет 2х квартиртиру + № денег и хочет разменять её на 2 1к квартиры с доплатой.
Это значит что:
2х квартира А стоимостью X + № денег = 1к квартира Б стоимостью Y + 1к квартира В стоимостью Z.
вот такие правила вам надо сделать а потом уже искать цепочки среди них, которые позволят замкнуть их друг на друге. Т.е. в любом случае нужно оперировать какими-то абстрактными денгами.
Скорее всего надо для каждого требования выбирать формировать массив возможных решений и ранжировать их по разным критериям. Как например это делают сайты авиа билетов по кол-ву пересадок. Тут будет схожий алгоритм.
Прямым перебором будет невероятно долго
Если делать это постоянно - да ресурсоемкая задача, а если при поступления нового предложения, делать для него просчет по всей базе, то вполне нормально.
В момент когда клиент запрашивает цепочку, она уже есть, не надо ее в этот момент рассчитывать.
sergey_privacy, как раз из этой. Это стандартная задача принятия решений. Есть множество решений - множество цепочек, нужно составить максимально эффективную. Это все давно решено и легко гуглится, математики там немного.
А еще часть клиентов будет отказываться от ряда цепочек, так-что невозможно найти одну-единственную и вариантов будет уйма.
В любом раскладе для каждого звена цепочки будет ряд критериев, удовлетворив которые получаем некое множество, в результате применяем комбинаторику и получаем уйму вариантов в каждом случае.
