Вычисление и идентификация «желаемых» маршрутов с помощью направленного графика

Question

Простите неопределенное название, прошло несколько лет с тех пор, как я провел математику, связанную с этой областью, и моя терминология довольно не хватает (часть того, почему я задаю этот вопрос). Я уверен, что есть хорошо определенный алгоритм/теория, которая уже имеет дело с тем, чего я пытаюсь достичь, но я не могу полностью определить слова, чтобы найти их.

Я попытаюсь описать ситуацию, я моделирование:

Учитывая группу элементов [а, Ь, с, д, е, е], человек может предлагать торговать определенные пункты, например Я могу поменять «a» на «b», и вы можете предлагать «2xc» для «e». Я могу зачерпнуть все эти сделки и создать график, в котором излагаются предлагаемые варианты. Я заинтересован в поиске определенных торговых путей и в качестве сторонних торговых путей, которые могли бы дать мне излишки товаров. Я предполагаю, что подобные вещи уже существуют в финансовом секторе (опять же, мне не хватает имен/опыта математика).

так, если бы я был «а» и хотел «е», и я имел следующие доступные пути:

a -> b, b -> f, c -> b, a-> 2(c), b -> a 

Я бы в конечном итоге с

a -> b -> f 

a -> (2)c -> b -> f  
     | 
     c    (An additional c) 

Там может места, где я может циклически повторяться, поэтому, если я использовал отношение b -> a выше, я мог бы постоянно извлекать c из-за избыточного c-элемента.

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

Извинения снова за неопределенность.

Answer 1

Звучит как типичная проблема state space search. Алгоритмы, такие как BFS или iterative deepening, могут найти кратчайшую серию сделок или даже создать все возможности.

Чтобы применить эти алгоритмы, вам придется переопределить свой график. Вместо использования таких узлов, как a и b с краем a -> b, определите пространство состояний, в котором состояние состоит из конечного числа каждого из элементов {a, b, c, f} (в этом случае достаточно четырехцелевых целых чисел) и преемника S, который применяет все возможные сделки с учетом состояния и строит ряд состояний преемников. Например, в нотации псевдо-Python,

S({a: 1, b: 2, c: 0, f: 0}) = [{a: 0, b: 3, c: 0, f: 0}, # trade a for b 
           {a: 1, b: 1, c: 0, f: 1}, # trade b for f 
           {a: 1, b: 2, c: 2, f: 0}, # trade a for 2c 
           {a: 2, b: 1, c: 0, f: 0}] # trade b for a 

Поскольку состояние пространства поиска является классической парадигмой в AI, большинство учебников ИИ накройте его. В частности, я могу порекомендовать AIMA by Russell and Norvig, в котором довольно подробно излагаются его первые несколько глав, посвященных обсуждению состояния пространства.