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