Количество магазинов s, предлагающих товары a по разным ценам.Магазин может не предлагать конкретный продукт.Магазины могут быть связаны друг с другом (улицами).
Задача состоит в том, чтобы найти оптимальный маршрут (цикл) от (и обратно) до некоторого дома, чтобы общая цена была минимальной.Общие цены - это сумма цен на товары и сумма расстояний между магазинами.
Цены на товары известны для каждого магазина.Магазин не должен посещаться для этой информации.
Ограничения:
- Покупатель / путешественник хочет приобрести список товаров, потенциально все товары
- Каждая статья доступна, по крайней мере, в одном магазине
- Расстояния между магазинами выражаются как стоимость , поэтому ее можно просто добавить к стоимости приобретенных товаров при расчете общей суммы.стоимость маршрута
- Магазины можно посещать более одного раза, но это увеличит стоимость поездки, поэтому общая стоимость маршрута
Первоначальное моделирование было выполнено с networkx , моделируя магазины (и дома) в виде ориентированного графа (с расстоянием / стоимостью в качестве веса), где каждый узел (магазин) содержит список всех цен на предлагаемые продукты.
Моя первая попытка состояла в том, чтобы создать решение для перебора, и мне удалось повторить все простых циклов .Затем для каждого цикла я рассчитываю транспортные расходы и затраты на товары (то есть минимальные цены, как они появляются в магазинах цикла).
Теперь вышеприведенное работает, но не масштабируется: сложность по времени для перечисления всех циклов составляет O((n+e)(c+1)) для n узлов, e ребер и c элементарных цепей ( Нахождение всех элементарных цепей направленногограф Д. Б. Джонсон, SIAM Journal по вычислительной технике 4, № 1, 77-84, 1975 ).И число циклов (цепей) растет довольно быстро:
# random 'streetlike' shop-graphs
number of shops: 3, cycles: 2
number of shops: 4, cycles: 11
number of shops: 5, cycles: 11
number of shops: 6, cycles: 60
number of shops: 7, cycles: 229
number of shops: 8, cycles: 868
number of shops: 9, cycles: 1399
number of shops: 10, cycles: 61139
number of shops: 11, cycles: 60066
number of shops: 12, cycles: 1246579
number of shops: 13, cycles: 7993420
Есть предложения для более масштабируемого описания проблемы?Я думаю о решениях для динамического или линейного программирования, но мне очень хотелось бы услышать идеи.
обновление: найдена целая кандидатская диссертация на тему: ftp: //tesis.bbtk.ull.es / ccppytec / cp181.pdf