長年の疑問がおおむね解消された気がするので、記念エントリ。
わかっている人には「ではない」て言われても「そりゃそうなのでは？」という感じだと思いますが、ご容赦ください。
デザインパターン（というか、オブジェクト指向設計）のあっさい理解が原因の悲しい誤解ストーリーです。
あらすじ
Strategyパターンは、GoFのデザインパターンのうちの1つで、振る舞いを切り替えるパターン。
LSP（Liskov Substitution Principle）は、派生型の定義の一種で、簡単に言うと「スーパークラスのオブジェクトを使用できる場所では、そのサブクラスも使用できなければならない（置き換え可能でなければならない）」とするもの。
で、Strategyパターンは「サブクラス化によって振る舞いを切り替える」わけだから、LSPに違反してしまうのでは？と思っていたのですが……、どうやらそういうわけではなかった！
StrategyパターンはLSP違反ではないようだ？
下図をご覧ください。
Strategyパターンの簡単なクラス図（例）です。
Performerクラスは、Performer.walk()が呼ばれたら、WalkingStrategyインタフェースのwalk()を呼び出し、生成されている実オブジェクト（NormalWalkingStrategyかMoonWalkingStrategy）に応じて、その具象クラスのwalk()のコードが実行されます。
NormalWalkingStrategyなら普通に歩きますし、MoonWalkingStrategyならムーン・ウォークします。
さて、かつての僕が注目していたのは、「NormalWalkingStrategy」と「MoonWalkingStrategy」は「振る舞いが異なる」ので、「置き換え可能ではない」のでは？というところでした。
が！
おわかりのように、たとえばMoonWalkingStrategyは、NormalWalkingStrategyのサブクラスではありません。し、逆もまた然り。あくまでどちらもWalkingStrategyインタフェースを実装しているだけです。
よって、NormalWalkingStrategyがMoonWalkingStrategyに置き換え可能である必要はありません。（逆もまた然り）
StrategyパターンはLSP違反ではない！
さて、両クラスが実装しているインタフェースであるWalkingStrategyのwalk()は、呼ばれたら「歩く」ことを約束しているみたいです。よって、LSPに従うと、WalkingStrategyインタフェースを使用しているすべての場所で、NormalWalkingStrategyとMoonWalkingStrategyの両方を使用できる必要があります。*1
できます。
というか、WalkingStrategyインタフェース自体がまさにNormalWalkingStrategyとMoonWalkingStrategyの共通項を抽象したものとも言うべきものなので、できるに決まってます。（できるように作ったのだから、できる）
WalkingStrategyのwalk()が「前に歩く」とは言っていないことがポイントです。
WalkingStrategyのクライアントであるPerformerは、もちろん、「前に歩くとは限らない」ということを知ったうえで、WalkingStrategyインタフェースを使用する必要があります。
だから、WalkingStrategyのドキュメントを作るとしたら、ただ「歩く」と書くだけじゃなくて、「歩く（前に、時には後ろや横に、斜めもあるかもね）*2」とか書くべきかもしれません。（普通の人は前に歩きますしね……）
StrategyパターンをLSP違反だと勘違いしていた理由
僕が「StrategyパターンはLSP違反なのでは？」と心配しているときにうすぼんやりと思い浮かべていたのは、実のところ、こういった設計だったのでした。（念のため注意：この図はStrategyパターンではありませんし、別にかつての僕がStrategyパターンをこういう形で理解していたわけでもありません。浅い理解こわい）
寂しくなりましたね。
WalkingStrategyがインタフェースではなくなり、具象クラスになって、更にStrategyパターンのときの「NormalWalkingStrategy」のwalk()が持っていた実装を持っています。
これは、LSP違反です。
NormalWalkingStrategyのwalk()は「前に向かって歩く」ことを約束しているので、「ムーン・ウォークする」MoonWalkingStrategyによって置き換え可能ではありません。
そう……
StrategyパターンはLSP違反ではなく、むしろLSP違反を避けるための設計パターンだったのだ！
（たぶん……）
まとめ
- StrategyパターンはLSP違反ではない。なぜなら、具体的なStrategyどうし（それぞれに振る舞いが違う）は継承関係を持たず、それらの共通項を抽象したインタフェースを実装しているだけだから。
- むしろStrategyパターンを適用することでLSP違反を避けられる。
参考文献
