それぞれの水差しの水量を x, y であらわすとすると、 その数値の組 (x, y) で、２つの水差しの「状態」をあらわすことができます。
ある「状態」で何らかの操作をすると、水差しの水量が変わりますから、 「状態」は別の「状態」に移り変わります。 例えば、両方の水差しが空のときの状態は (0,0) で表されますが、 その状態で「大を満たす」操作をすると、(5,0) という状態に移ります。
そのような「状態」を○で表わし、 その間の可能な移り変わりを矢印で表した図を状態遷移図といいます。 先の問題の状態遷移図は左のようになります。
先の問題は、この状態遷移図上で、状態 (0,0) を出発点として、 状態 (4,0) または (4,3) をゴールとする道筋を見つけだす、 いわば「迷路」を解く問題になります。
コンピュータがこのような問題を解くときには、 このような道筋を系統的に見つけだすようにプログラミングされます。 人工知能の重要なテクニックの一つは、 このような「探索」を確実に、また、効率的に行うためのものです。