Как рассчитать изменение веса вершин в ориентированном графе с циклическими зависимостями?
Я делаю небольшую игру на Java, чтобы попрактиковаться в программировании, и натолкнулся на эту маленькую проблему, которую я не могу решить самостоятельно.
В этой игре я хочу построить виртуальный магазин, где я могу покупать и продавать предметы.
Большинство предметов можно получить только в игре, создав их из других предметов, следуя тому, что я назвал "рецептами". Рецепт - это просто набор предметов, необходимых для создания нового предмета. Предмет может иметь несколько рецептов. Результатом рецепта может быть более одного экземпляра новой суммы. Я буду обозначать рецепты, такие как [предмет, предмет,..., предмет](итоговая сумма).
Таким образом, существуют базовые предметы, которые не могут быть созданы, но должны быть получены другими способами, и существуют созданные предметы, которые могут быть получены только по одному из его рецептов.
Я хочу попытаться смоделировать спрос и предложение, и я придумала это свойство, которое я называю "сумма сделки", которая инициализируется в 0 для каждого элемента. Сумма сделки показывает, сколько товара продается или покупается. Если я продам X количества предмета, его объем торговли увеличится на X, а если я куплю Y количества предмета, его объем торговли уменьшится на Y.
Теперь мне нужно определить цену на мои товары.
Всем базовым предметам присваивается фиксированное значение. Затем стоимость и сумма сделки включаются в функцию f(v, t), которая выплевывает цену. Эта цена всегда>= 0. Одно свойство этой функции - если сумма сделки t равна 0, тогда результирующая цена равна входному значению v. Поэтому, если один игрок покупает заданное количество товара, сумма сделки идет вниз на x, и цена становится ближе к 0. Если затем другой игрок продает такое же количество того же предмета, сумма сделки возвращается к 0, и цена возвращается к первоначальному значению.
Теперь, когда у всех базовых предметов есть значение, мне нужно вычислить значения всех созданных предметов, чтобы иметь возможность рассчитать их цену, используя f. Я хочу, чтобы их ценность основывалась на самом дешевом рецепте, необходимом для их создания. Поэтому я должен разобрать все рецепты, сложить цены всех предметов, использованных в каждом рецепте, и определить минимальную цену рецепта. Это стоимость созданного предмета.
Я могу смоделировать эту настройку в виде графика с вершинами, представляющими предметы, которыми можно торговать в магазине, а направленные ребра соединяют предмет с другим предметом, который можно создать из исходного предмета. Таким образом, у меня есть направленный край ("источник -> пункт назначения"), где источник является ингредиентом в одном из рецептов пункта назначения. Исходя из этой предпосылки, я создаю случайный ориентированный граф из 600 вершин. Этот график меняется каждый раз, когда загружается игра, и генератор должен специально разрешать циклы внутри графика.
Вот пример:
Элементы A и B являются базовыми элементами со значениями 10 и 2 соответственно. Их торговые объемы изначально равны 0, поэтому их цены равны их значениям 10 и 2.
Предмет C - это созданный предмет с двумя рецептами R1 = A, A, B и R2 = B, B, B. Теперь я определяю R1 по 22, а R2 по 6, что является минимальной ценой рецепта. Таким образом, позиция C имеет значение 6 (и изначально сумма сделки равна 0, поэтому цена также равна 6).
В этом случае график будет выглядеть примерно так: (A) -> (C) <- (B)
До этого момента все это прекрасно и прекрасно работало.
Теперь у меня возникает проблема, когда зависимости цена-значение являются циклическими.
Вот 3 типа случаев, в которых мне нужна помощь:
(1) - 0 вершинный цикл
Проще говоря, предмет A имеет фиксированную цену, а предмет B можно создать по рецепту [A, B]. Если цена B изменяется, то все элементы, созданные B, должны быть пересчитаны. В этом случае B состоит из A и B, поэтому я также должен пересчитать цену B. Это снова вызывает пересчет B и так далее, и так далее... Я знаю, что посылка странная, но думаю, что это перекрашивание двери (B). Он сделан из той же двери (B) плюс краска (A). Я называю это циклом с 0 вершинами, потому что при прохождении цикла вы передаете 0 вершин, чтобы вернуться к тому, с чего начали.
(2) - 1 вершинный цикл
Если мы возьмем те же предметы A и B из самого первого примера и добавим элемент C с рецептами R1=A, B и R2=D, D, D и пункт D с рецептом R3=C. Таким образом, C можно "разбить" на 3 D, а 3 D можно объединить в один C. Если я сейчас снизу цену C, продав ее много, я должен также понизить цену D, поскольку можно сделать D C. Но поскольку C также может быть сделан из D, и, предполагая, что R2 становится дешевле, чем R1, я должен также понизить цену C, таким образом снова вызывая снижение цены D и так далее, и так далее. Это будет продолжаться до тех пор, пока значение не приблизится где-либо в зависимости от ингредиентов рецептов. Я называю это циклом из 1 вершины, потому что при прохождении цикла вы проходите только одну вершину.
(3) - цикл n вершин
Это общий случай, и я думаю, что если я решу это, два вышеупомянутых конкретных случая также будут разрешены. Если элемент A сделан из B, B из C, C из D и так далее до элемента Z, который сделан из A, то изменение цены одного вызовет изменение цены следующего, что вызовет цена следующая и тд и тп. Эта цепочка может быть практически произвольно длинной.**
Я ищу алгоритм, который может решить мою проблему. Я хочу, чтобы можно было рассчитать все значения и цены всех предметов с первоначальной торговой суммой 0. Когда игроки покупают и продают предметы, изменения цен должны распространяться по графику. Я рассмотрел вопрос об изменении алгоритма Дейкстры, A*, алгоритма Беллмана-Форда и алгоритма Флойда-Варшалла, но не смог получить удовлетворительный результат ни с одним из них.
Может ли кто-нибудь указать мне правильное направление?