通過有向圖計算和確定「理想」路線

Question

原諒模糊的標題，這是因爲我已經做了幾年與該領域有關的任何數學，而且我的術語還相當欠缺（爲什麼我要問這個問題的部分原因）。我確信有一個明確定義的算法/理論已經處理了我想要達到的目標，但我無法確定要找到它的單詞。

我會試着描述的情況我在造型：

給定一組項目[A，B，C，d，E，F]，一個人可以被提供給貿易中對某些項目，例如我可能會將「a」換成「b」，並且您可能會爲「e」提供「2xc」。我可以收集所有這些交易，並創建一個圖表概述所提供的選項。我對尋找特定的交易路徑很感興趣，另外還有一些交易路徑可以讓我獲得多餘的產品 - 我認爲這種事情必須已經存在於金融領域（再次，我錯過了數學）。

，所以如果我有「A」，並希望「F」，我有好以下路徑：

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

我想最終

a -> b -> f 

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

有可能的地方，我可以反覆循環，所以如果我使用上面的b - >關係，我可以繼續提取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，它的前幾章將詳細討論狀態空間搜索。