Здравствуйте, nvoynov, Вы писали:

N>Условия задачи вообще тоже в процессе разработки, озвучены заказчиком просто как "Бартер". Но пока выглядит так. Клиент размещает заявку в которой указывает что у него есть, на что он готов это поменять и на каких условиях (возможно как-то дальше будет преобразовываться в вес ребра). Если есть прямые предложения обмена шило-на-мыло, то пользователь может совершить операцию самостоятельно. Если прямых нету то включается брокер, который пытается совершить этот сложный обмен.

N>Пока не думал над множеством предложений от одного человека и рассматривал простой случай, который приведен в первом посте. Тогда для первого случая я построил граф товаров что-на-что меняется и получил цикл конфеты->сахар->масло.

N>В общем задача видится так
N>- клиент размещает предложения 1..* и потребности 1..*
N>- клиент обращается к агенту для того, чтобы агент помог совершить ему обмен (конечно только то что получится, т.е. есть в базе товар и сложные пути его обмена — циклы)
N>- агент при помощи системы ищет все возможные варианты и выбирает наиболее оптимальные, вернее системе помогает ему подобрать оптимальные варианты (различные условия доставки товара могут влиять на вес ребер обмена)


Тут нужно курить не в сторону теории графов, а в сторону практического смысла.
Пусть заказчик скажет, что он думает про такие ситуации:
1. Если удовлетворить клиента в данный момент в принципе невозможно, он остаётся на рынке и ждёт? или сваливает?
2. Если ждут несколько, и вдруг пришёл кто-то с товаром, который может замкнуть несколько разных цепочек (прямой обмен — частный случай) — какому варианту отдавать предпочтение?
— минимизировать длину цепочки (предпочитать прямой обмен)
— удовлетворить наиболее долго ждущих
А что, если одна цепочка состоит из ждущего год и ждущего день, а вторая — из ждущего 9 месяцев и ждущего 3 месяца? И длина одинаковая, и суммарное ожидание одинаковое... Что делать?

Брокеру, кстати, выгодно иметь дело с наиболее длинными цепочками: комиссионные больше

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

Зачем вообще потребовалось автоматизировать разруливание цепочек? Правда ли, что такой большой поток заявок, что обычные люди не справляются? Или просто понты мечут, захотели внедрить передовые технологии в купипродайную лавку?



N>Тут возникла мысль, видно что Вы разбираетесь в вопросе, я бы с удовольствием попробовал выбить у начальства средств и передать эту конкретную часть задачи (поиск возможных вариантов) Вам.

Пожалуй, откажусь!
Мои познания в теории графов невелики и отрывочны, больше из любопытства.