* Поиск многоуровневых сделок (участвует более двух участников). Например,
— Васе нужен Сахар и у него есть Конфеты;
— у Пети есть сахар, но ему нужно Масло;
— у Маши есть Масло и ей нужны Конфеты.
Здравствуйте, nvoynov, Вы писали:
N>Подскажите пожалуйста, есть ли какие стандартные алгоритмы для решения подобных задач?
Имеем двудольный орграф: слева агенты, справа товар.
Ребро от агента к товару значит, что товар в наличии (поставляется агентом).
Ребро от товара к агенту — что он хочет его приобрести.
Задача номер один: разбить орграф на циклы.
Задача номер два — совсем тривиальная — ввести брокера и представить обход цикла как работу через брокера.
Здравствуйте, Кодт, Вы писали:
К>Имеем двудольный орграф: слева агенты, справа товар. К>Ребро от агента к товару значит, что товар в наличии (поставляется агентом). К>Ребро от товара к агенту — что он хочет его приобрести.
Может путаю терминологию (очень давно "числил методы") двудольный наверное не получается — у агента есть один товар, а нужен ему другой, т.е. ребра могут быть двунаправленными.
К>Задача номер один: разбить орграф на циклы. К>Задача номер два — совсем тривиальная — ввести брокера и представить обход цикла как работу через брокера.
и по идее это большая система предложений, соответственно ребра могут быть а могут не быть как в прямом так и обратном направлении ...
в любом случае это граф, наверное товаров (что на что можно поменять) и в нем нужно искать циклы, а потом выбирать наименьшие ...
Здравствуйте, nvoynov, Вы писали:
N>Может путаю терминологию (очень давно "числил методы") двудольный наверное не получается — у агента есть один товар, а нужен ему другой, т.е. ребра могут быть двунаправленными.
Так как раз двудольный и ориентированный.
Двудольность заключается в том, что все вершины принадлежат к двум подмножествам — агенты и товары, и рёбра есть только между агентами и товарами, но не внутри агентов или внутри товаров.
А ориентированность — в том, что одни рёбра означают предложение, другие спрос; и естественно задать тип отношения направлением ребра.
К>>Задача номер один: разбить орграф на циклы. К>>Задача номер два — совсем тривиальная — ввести брокера и представить обход цикла как работу через брокера.
N>и по идее это большая система предложений, соответственно ребра могут быть а могут не быть как в прямом так и обратном направлении ...
N>в любом случае это граф, наверное товаров (что на что можно поменять) и в нем нужно искать циклы, а потом выбирать наименьшие ...
Я сформулировал наиболее общий случай. Скажем, один агент выставляет множество предложений и множество же заявок.
Это может означать, что
— нужно удовлетворить все заявки (т.е. мы разбиваем граф на циклы, разбивая множество рёбер-заявок)
— нужно удовлетворить ровно одну заявку (т.е. мы разбиваем множество вершин-агентов)
— нужно удовлетворить хотя бы одну заявку агента, чтобы он "имел навар с яиц" (т.е. мы не разбиваем, а покрываем множество вершин-агентов)
А возможно, что условия задачи провозглашают, что у агента ровно одна заявка и ровно одно предложение.
В таком случае заявка-агент-предложение является ребром.
И тогда у нас получается просто орграф из вершин-товаров и рёбер-агентов.
И мы разбиваем его на циклы, разбивая (или покрывая) множество рёбер.
Покрытие рёбер значит, что несколько циклов могут проходить через одно ребро — т.е. агент неоднократно наваривается на бартере. (Как в первом случае — двудольного графа, так и во втором).
Тут для уточнения нужно или вводить кратность рёбер, или вес — и требовать, чтобы ток денежного эквивалента по контуру был одинаков во всех рёбрах, а сумма токов через ребро равнялась весу этого ребра.
Здравствуйте, ТОЭ и законы Кирхгофа!
Кстати, а может, действительно можно припахать электротехнику?
Очевидно, что задача имеет решение только тогда, когда сумма токов каждого товара равна нулю (сумма предложений равна сумме заявок).
Иначе бартер не состоится.
Ну а раз такая пьянка, то мне начинает казаться, что решения всегда есть, и задача уточняется до поиска кратчайших циклов, а не до поиска любых циклов.
Резисторы?
Точно! Каждое ребро представляет резистор и источник тока.
Здравствуйте, Кодт, Вы писали:
К>Я сформулировал наиболее общий случай. Скажем, один агент выставляет множество предложений и множество же заявок. К>Это может означать, что К>- нужно удовлетворить все заявки (т.е. мы разбиваем граф на циклы, разбивая множество рёбер-заявок) К>- нужно удовлетворить ровно одну заявку (т.е. мы разбиваем множество вершин-агентов) К>- нужно удовлетворить хотя бы одну заявку агента, чтобы он "имел навар с яиц" (т.е. мы не разбиваем, а покрываем множество вершин-агентов)
К>А возможно, что условия задачи провозглашают, что у агента ровно одна заявка и ровно одно предложение. К>В таком случае заявка-агент-предложение является ребром. К>И тогда у нас получается просто орграф из вершин-товаров и рёбер-агентов. К>И мы разбиваем его на циклы, разбивая (или покрывая) множество рёбер.
Сразу пост не переварил и буду еще сегодня курить ...
Условия задачи вообще тоже в процессе разработки, озвучены заказчиком просто как "Бартер". Но пока выглядит так. Клиент размещает заявку в которой указывает что у него есть, на что он готов это поменять и на каких условиях (возможно как-то дальше будет преобразовываться в вес ребра). Если есть прямые предложения обмена шило-на-мыло, то пользователь может совершить операцию самостоятельно. Если прямых нету то включается брокер, который пытается совершить этот сложный обмен.
Пока не думал над множеством предложений от одного человека и рассматривал простой случай, который приведен в первом посте. Тогда для первого случая я построил граф товаров что-на-что меняется и получил цикл конфеты->сахар->масло.
В общем задача видится так
— клиент размещает предложения 1..* и потребности 1..*
— клиент обращается к агенту для того, чтобы агент помог совершить ему обмен (конечно только то что получится, т.е. есть в базе товар и сложные пути его обмена — циклы)
— агент при помощи системы ищет все возможные варианты и выбирает наиболее оптимальные, вернее системе помогает ему подобрать оптимальные варианты (различные условия доставки товара могут влиять на вес ребер обмена)
Пока покурив немного литературу нашел
— Иванов, Дискретная математика. Алгоритмы и программы.
На стр. 151 "Кратчайшие пути на графе" решается очень похожая задача, но пока не разобрался с другими путями кроме кратчайшего.
Покурю еще раз двудольный орграф и продолжение поста ...
Тут возникла мысль, видно что Вы разбираетесь в вопросе, я бы с удовольствием попробовал выбить у начальства средств и передать эту конкретную часть задачи (поиск возможных вариантов) Вам.
Здравствуйте, nvoynov, Вы писали:
N>Условия задачи вообще тоже в процессе разработки, озвучены заказчиком просто как "Бартер". Но пока выглядит так. Клиент размещает заявку в которой указывает что у него есть, на что он готов это поменять и на каких условиях (возможно как-то дальше будет преобразовываться в вес ребра). Если есть прямые предложения обмена шило-на-мыло, то пользователь может совершить операцию самостоятельно. Если прямых нету то включается брокер, который пытается совершить этот сложный обмен.
N>Пока не думал над множеством предложений от одного человека и рассматривал простой случай, который приведен в первом посте. Тогда для первого случая я построил граф товаров что-на-что меняется и получил цикл конфеты->сахар->масло.
N>В общем задача видится так N>- клиент размещает предложения 1..* и потребности 1..* N>- клиент обращается к агенту для того, чтобы агент помог совершить ему обмен (конечно только то что получится, т.е. есть в базе товар и сложные пути его обмена — циклы) N>- агент при помощи системы ищет все возможные варианты и выбирает наиболее оптимальные, вернее системе помогает ему подобрать оптимальные варианты (различные условия доставки товара могут влиять на вес ребер обмена)
Тут нужно курить не в сторону теории графов, а в сторону практического смысла.
Пусть заказчик скажет, что он думает про такие ситуации:
1. Если удовлетворить клиента в данный момент в принципе невозможно, он остаётся на рынке и ждёт? или сваливает?
2. Если ждут несколько, и вдруг пришёл кто-то с товаром, который может замкнуть несколько разных цепочек (прямой обмен — частный случай) — какому варианту отдавать предпочтение?
— минимизировать длину цепочки (предпочитать прямой обмен)
— удовлетворить наиболее долго ждущих
А что, если одна цепочка состоит из ждущего год и ждущего день, а вторая — из ждущего 9 месяцев и ждущего 3 месяца? И длина одинаковая, и суммарное ожидание одинаковое... Что делать?
Брокеру, кстати, выгодно иметь дело с наиболее длинными цепочками: комиссионные больше
А чтобы курить практический смысл, нужно немножко отвлечься от абстрактной постановки вопроса и озвучить реальную.
На товарной бирже ситуация одна, в агентстве недвижимости другая, в игрушке-стратегии-квесте третья...
Зачем вообще потребовалось автоматизировать разруливание цепочек? Правда ли, что такой большой поток заявок, что обычные люди не справляются? Или просто понты мечут, захотели внедрить передовые технологии в купипродайную лавку?
N>Тут возникла мысль, видно что Вы разбираетесь в вопросе, я бы с удовольствием попробовал выбить у начальства средств и передать эту конкретную часть задачи (поиск возможных вариантов) Вам.
Пожалуй, откажусь!
Мои познания в теории графов невелики и отрывочны, больше из любопытства.
Здравствуйте, Кодт, Вы писали:
К>Тут нужно курить не в сторону теории графов, а в сторону практического смысла. К>Пусть заказчик скажет, что он думает про такие ситуации: К>1. Если удовлетворить клиента в данный момент в принципе невозможно, он остаётся на рынке и ждёт? или сваливает?
Клиент просто попросил брокера выполнить обмен, у заявки должен быть "срок годности". Если возможности в этом конкретном месте нету, нет возможных цепочек, то их просто нету. Если появятся до окончания срока годности то работа может быть продолжена. По идее у брокера лежат заявки и система по какому-то расписанию пересчитывает варианты
К>2. Если ждут несколько, и вдруг пришёл кто-то с товаром, который может замкнуть несколько разных цепочек (прямой обмен — частный случай) — какому варианту отдавать предпочтение? К>- минимизировать длину цепочки (предпочитать прямой обмен) К>- удовлетворить наиболее долго ждущих К>А что, если одна цепочка состоит из ждущего год и ждущего день, а вторая — из ждущего 9 месяцев и ждущего 3 месяца? И длина одинаковая, и суммарное ожидание одинаковое... Что делать?
Кто первый встал того и тапки. Как правило с определенными группами товаров работают вполне определенные люди, поэтому не думаю что с этим проблемы будут. К тому же могут быть приоритеты постоянных клиентов, либо сделок на постоянной основе (постоянно компания берет сахар и отдает конфетами). Вообще конечно же минимизировать длину цепочки, т.е. быстрее обработать запрос. С другой стороны если 10 операций можно провести в 2 местах или 10 в 7 местах, наверное 10 ходовая комбинация в двух местах будет быстрее .. опять же можно отдавать на согласование с клиентом. Поэтому и нужны большинство из возможных вариантов, плюс возможность рулить приоритетами и сравнивать.
К>А чтобы курить практический смысл, нужно немножко отвлечься от абстрактной постановки вопроса и озвучить реальную. К>На товарной бирже ситуация одна, в агентстве недвижимости другая, в игрушке-стратегии-квесте третья...
К>Зачем вообще потребовалось автоматизировать разруливание цепочек? Правда ли, что такой большой поток заявок, что обычные люди не справляются? Или просто понты мечут, захотели внедрить передовые технологии в купипродайную лавку?
Да нету никакого потока заявок, и пока играемся с абстрактными примерами. Но вообще вроде красиво выходит .. клиент подал заявок/предложений и тут же получил возможные сейчас варианты, либо их сразу получил брокер и предложил услуги.
Ну в таком простом случае, действительно — поиск кратчайшего цикла либо поиск всех циклов через данную вершину двудольного орграфа.
(Или с участием данного ребра в графе товаров, если клиент представлен ребром "отдам А строго за Б").
Тупейшие волновые алгоритмы спасут отца русской демократии.
Правда, ты можешь поймать комбинаторный взрыв количества циклов, если граф имеет, например, такой вид
А-Б1-В-Г1-Д-...-А
А-Б2-В-Г1-Д-...-А
А-Б3-В-Г1-Д-...-А
А-Б1-В-Г2-Д-...-А
А-Б2-В-Г2-Д-...-А
А-Б3-В-Г2-Д-...-А
А-Б1-В-Г3-Д-...-А
А-Б2-В-Г3-Д-...-А
А-Б3-В-Г3-Д-...-А
...
Удовлетворит ли заказчика эта простыня, или наоборот, ввергнет в печаль?
Здравствуйте, nvoynov, Вы писали:
N>* Поиск многоуровневых сделок (участвует более двух участников). Например, N>- Васе нужен Сахар и у него есть Конфеты; N>- у Пети есть сахар, но ему нужно Масло; N>- у Маши есть Масло и ей нужны Конфеты.
N>Подскажите пожалуйста, есть ли какие стандартные алгоритмы для решения подобных задач?
Есть — динамическое программирование.
Будем считать, что у Васи что-то есть если он имеет это изначально или может получить в результате обмена. На каждом шаге пытаемся обменять имеющееся на что-нибидь новое. Затем добавим это новое в список имеющегося (и запомним с кем мы менялись). Будем повторять шаги пока список имеющегося перестанет увеличиваться. В конце концов получится список всего, что можно получить с помощью обмена. А запомненная информация об участниках бартера позволит восстановить цепочку обмена.
Например:
Кто Есть Надо
Вася Конфеты Сахар
Маша Масло Конфеты
Миша Масло Конфеты
Петя Сахар Масло
Вова Соль Масло
Гоша Соль Конфеты
Света Сахар Орехи
1. Вася имеет [Конфеты]. Ищем кому нужны конфеты. Значит можно получить [Масло (Маша), Масло (Миша), Соль (Гоша)]
2. Вася "имеет" [Конфеты, Масло (Маша), Масло (Миша), Соль (Гоша)]. Ищем кому нужно масло и соль. Нашли [Сахар (Петя), Соль (Вова)]
3. Вася "имеет" [Конфеты, Масло (Маша), Сахар (Петя, Маша), Сахар (Петя, Миша), Соль (Гоша), Соль (Вова, Маша), Соль (Вова, Миша)]. Кому надо сахар и соль? Нет таких.
Перекуём баги на фичи!
В конце концов получится список всего, что можно получить с помощью обмена. А запомненная информация об участниках бартера позволит восстановить цепочку обмена.