Calculating and identifying "desirable" routes through directed graph -

Calculating and identifying "desirable" routes through directed graph -

forgive vague title, it's been few years since i've done mathematics related area , terminology lacking (part of why i'm asking question). i'm sure there's defined algorithm/theory deals i'm trying achieve, can't quite pin downwards words find it.

i'll seek , describe situation i'm modelling:

given grouping of items [a,b,c,d,e,f], person may offering trade items, e.g. may swap "a" "b", , may offering "2xc" "e". can scoop these trades , create graph outlining options on offer. i'm interested in looking particular trade paths, , aside, trade paths give me surplus items - assume sort of thing must exist in financial sector (again, i'm missing names/experience of mathematics).

so if had "a" , wanted "f", , had next paths available:

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

i'd end with

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

there may places cycle repeatedly, if used b -> relation above, continually extract c because of surplus c item.

i'm reasonably sure can write programme this, i'm big fan of understanding right terminology , methodology behind problems one. if can point me in right direction particular topic read about, or if there's obvious name i'm trying achieve, i'd grateful.

apologies 1 time again vague-ness.

sounds typical state space search problem. algorithms bfs or iterative deepening can find shortest series of trades, or generate possibilities.

to apply these algorithms, you'll have redefine graph. instead of using nodes a , b border a -> b, define state space state consists of finite number of each of elements {a, b, c, f} (in case, four-tuple of integers suffice) , successor function s applies possible trades given state , constructs set of successors states. e.g., in pseudo-python notation,

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

since state-space search classical paradigm in ai, ai textbooks cover it. in particular, can recommend aima russell , norvig, spends first few chapters discussing state space search in quite detail.

graph-theory