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