深さ優先探索（Depth-First Search）

深さ優先探索（Depth-First Search）

ある状態からはじめて、遷移できなくなるまで状態を進める。
遷移できなくなったら1つ前の状態に戻る。
上記はstackのpushとpopで実現できる。
このため、深さ優先探索は再帰関数（呼び出し元に戻る）で実装できる場合が多い。

部分和問題（Partial Sum）

{a1, a2, ..., an}からいくつか選んだ和がkになるかを判別する。
今回は深さ優先探索で各組み合わせの和をすべて求める。
a1から順に和に加えないor加えるを決める。
このため、以下のような二分木に対して、深さ優先探索を行えば良い。

public class PartialSum
{
  internal List<int> PartialSums = new();
  internal List<int> Numbers;
  
  public PartialSum(List<int> numbers)
  {
    this.Numbers = numbers;
  }
  
  public List<int> GetPartialSums()
  {
    this.ParsePartialSums(0, 0);
    return this.PartialSums;
  }
  
  private void ParsePartialSums(int i, int sum)
  {
    if (i == Numbers.Count)
    {
      this.PartialSums.Add(sum); // 葉に到着（これ以上遷移不可能）の場合は終了
      return;
    }
  
    ParsePartialSums(i + 1, sum); // 合計値にi番目の値を加えない
  
    ParsePartialSums(i + 1, sum + this.Numbers.ElementAt(i)); // 合計値にi番目の値を加える
  }
}

ナップサック問題（Knapsack Problem）

部分和の対象が以下のような『重量と価値の組』になる。
{ (w1, v1), (w2, v2), ..., (wn, vn)}

public class KnapsackProblem
{
  internal List<(int weight, int value)> WeightValues;
  internal int LimitWeight;
  
  internal List<(int weight, int value)> SumWeightValue = new();
  
  public KnapsackProblem(List<(int weight, int value)> weightValues, int limitWeight)
  {
    this.WeightValues = weightValues;
    this.LimitWeight = limitWeight;
  }
  
  public List<(int weight, int value)> GetSumWeightValue()
  {
    this.CreateWumWeightValue(0, 0, 0);
    return this.SumWeightValue;
  }
  
  private void CreateWumWeightValue(int i, int weight, int value)
  {
    if (i == WeightValues.Count)
    {
      this.SumWeightValue.Add((weight, value));
      return;
    }
  
    CreateWumWeightValue(i + 1, weight, value);
  
    CreateWumWeightValue(i + 1, weight + WeightValues.ElementAt(i).weight, value + WeightValues.ElementAt(i).value);
  }
}

迷路

スタート（S）とゴール(G)のほかに道(.)と壁(#)からなる地図で、ゴールまで辿り着けるか。

S.#.
..#G
....

深さ優先探索を用いて、以下のように隣接する縦・横・斜めの道を進む。

上記のように探索するためには、左斜め上は現在地から(-1, -1)、上は(0, -1)...なので以下のようになる。

以上より、コードは以下のようになる。

private void CanReachToGoalByRecursive(int row, int col)
{
  if (this.CanReachToTheGoal) return;
  this.Map[row, col] = ALREADY_VISITED;

  for (var adjacentRow = -1; adjacentRow <= 1; ++adjacentRow)
  {
    var nextRow = row + adjacentRow;
    var inRowRange = nextRow >= 0 && nextRow < H; // 縦方向に地図内に収まっている
    if (!inRowRange) continue;
    for (var adjacentCol = -1; adjacentCol <= 1; ++adjacentCol)
    {
      var nextCol = col + adjacentCol;
      var inColRange = nextCol >= 0 && nextCol < W; // 横方向に地図内に収まっている
      if (!inColRange) continue;
      var nextPlace = this.Map[nextRow, nextCol];
      if (nextPlace == GOAL)
      {
        this.CanReachToTheGoal = true;
        return;
      }
      if (nextPlace == ROAD)
        CanReachToGoalByRecursive(nextRow, nextCol); // 次が道であれば進む
    }
  }
}

再帰関数（Rucursive Function）

再帰（Recursion）

ある物事について記述する際に、記述しているもの自体への参照が、その記述中にあらわれること。
つまり、再帰関数はある処理を実行中にそのある処理があらわれること。
⇒関数内で自身を呼び出す関数。

public void ProcessA()
{
    ...
    ProcessA(); // 自身
    ...
}

終了条件

上記のProcessAを考えると、

  • 1回目のProcessAで、2回目のProcessAを呼び出し
  • 2回目のProcessAで、3回目のProcessAを呼び出し
  • 3回目のProcessAで、4回目のProcessAを呼び出し
  • ...

のように、永遠に続いてしまう(無限ループ)。 このため、再帰関数には終了条件が必須。

再帰関数のイメージ

一般的にはスタックをイメージすると分かりやすい。

public void Display(int number)
{
    if (number-- == 0) return;
    Display(number);
    System.Console.Write($"{number}の表示,");
}

上記をDisply(5)で実行すると以下が表示される。
「0の表示,1の表示,2の表示,3の表示,4の表示,」
以下のイメージ

代表的な例

階乗（Factorial）

最もメジャーな例
階乗n!は1～nまでの整数の積
終了条件は0! = 1を使用する。

public int Factorial(int n) => n== 0 ? 1 : n * Factorial(n - 1);

べき乗（Exponentiation）

bn = b × b × ... × b × b(bはn個)
終了条件はb0 = 1を使用する

public int Exponentiatin (int baseNumber, int exponent) => exponent == 0 ? 1 : baseNumber * Exponentiation(baseNumber, exponent - 1);

Factory Methodパターン

Factory Method

生成に関するデザインパターン。
使用頻度は少ないっぽい。
直訳すると工場のメソッドだが、何の工場なのか？
⇒インスタンスの工場
Factory MethodはVirtual Constructorとも呼ばれコンストラクタの代わりとなるメソッド。
このメソッドはスーパークラスで定義して、サブクラスで実際にオブジェクトを作成する。

運送会社を例に考える

トラックで運送を行っている会社は、
トラックを車庫から出して（インスタンスの生成）
そのトラックを使用して荷物を届けている。

public class Logistics
{
  public void Delivery()
  {
    var truck = new Truck();
    truck.Deliver();
  }
}

public class Truck
{
  public void Deliver() => System.Console.WriteLine("トラックで運ぶよ");
}

離島への運送依頼

報酬が良かったため、特別に離島への運送を行うことにした。

public class Logistics
{
  public void Delivery()
  {
    //var truck = new Truck();
    var truck = new Ship();
    truck.Deliver();
  }
}

public class Ship
{
  public void Deliver() => System.Console.WriteLine("船で運ぶよ");
}

継続と問題

海路の運送が意外に利益が大きいため、今後も続けることにした。
それ以外の問題として、これまでトラックを使ってしていたDelivery()でエラーが発生した。
⇒Factory Methodを適用。

スーパークラスの定義

どちらも運送なので、Logisticsクラスを作成

public abstract class Logistics
{
  public void Delivery()
  {
    var transport = CreateTransport();
    transport.Deliver();
  }

  public abstract ITransport CreateTransport();
}

public interface ITransport
{
  public void Deliver();
}
サブクラス陸路
public class LandLogistics : Logistics
{
  public override ITransport CreateTransport() => new Truck();
}
 
public class Truck : ITransport
{
  public void Deliver() => System.Console.WriteLine("トラックで搬送");
}
サブクラス海路
public class SeaLogistics : Logistics
{
  public override ITransport CreateTransport() => new Ship();
}
 
public class Ship : ITransport
{
  public void Deliver() => System.Console.WriteLine("船で搬送");
}

UMLクラス図

 

Template Methodパターン


Template Method

振る舞いに関するデザインパターン。
スーパークラスで処理手順を決定。
サブクラスで各処理を実装。

例：丼物

丼物をスーパークラスとする。
丼物を作成する流れ（処理手順）は以下

  1. ご飯を炊く
  2. トッピングを料理
  3. ご飯を盛る
  4. トッピングを乗せる

以上より、各処理と作成は以下のように定義できる。

public abstract class DonMono
{
  public abstract void CookRice();
  public abstract void CookTopping();
  public abstract void ServeRice();
  public abstract void GarnishTopping();
  
  public void Make()
  {
    this.CookRice();
    this.CookTopping();
    this.ServeRice();
    this.GarnishTopping();
  }
}

牛丼

牛丼は丼物のサブクラスで以下の用に定義できる。

public class GyuDon : DonMono
{
  public override void CookRice() => System.Console.WriteLine("固めで炊く");
  public override void CookTopping() => System.Console.WriteLine("牛肉と玉ねぎを煮込む");
  public override void ServeRice() => System.Console.WriteLine("ご飯を盛り付ける");
  public override void GarnishTopping() => System.Console.WriteLine("牛肉を盛り付ける");
}

かつ丼

かつ丼も丼物のサブクラスで以下のように定義できる。

public class KatsuDon : DonMono
{
  public override void CookRice() => System.Console.WriteLine("普通に炊く");
  public override void CookTopping() => System.Console.WriteLine("豚肉を揚げる");
  public override void ServeRice() => System.Console.WriteLine("ご飯を盛り付ける");
  public override void GarnishTopping() => System.Console.WriteLine("とんかつを盛り付ける");
}

提供

public void Main(string[] args)
{
  DonMono donMono = new KatsuDon();
  donMono.Make();
  donMono = new GyuDon();
  donMono.Make();
}

UMLクラス図

Abstract Factoryパターン

Abstract Facotry

　生成に関するデザインパターン。
　整合性が必要とされる一連のオブジェクト群を具象クラスを指定することなく生成するインターフェイスを提供する。

整合性が必要とされる一連のオブジェクト

立ち技格闘技を例に考える。
立ち技格闘技といっても、ムエタイ、シュートボクシング、キックボクシングなどでルールが異なる。
腕を使用した攻撃について、ムエタイの場合は"エルボー"を使えるが、キックボクシングでは使えない。
クリンチ状態の攻撃について、ムエタイの場合は"こかし"を使えるが、キックボクシングでは使えない。
立ち技格闘技の攻撃は共通して、"腕を使用した攻撃", "脚を使用した攻撃", "クリンチ状態の攻撃"に分類した場合、 ムエタイの"腕を使用した攻撃", "脚を使用した攻撃", "クリンチ状態の攻撃"は整合性を保つ必要がある。
この"腕を使用した攻撃", "脚を使用した攻撃", "クリンチ状態の攻撃"が一連のオブジェクト。

整合性が取れなくなるパターン

以下のように、立ち技格闘技に対して、"腕を使用した攻撃", "脚を使用した攻撃", "クリンチ状態の攻撃"を個々に設定できるようにした場合、

public class StandingBout
{
    private AbstractLegAttack LegAttack;
    private AbstractHandAttack HandAttack;
    private AbstractClinchWork ClinchWork;
        
    public void SetAbstractLegAttack(AbstractLegAttack abstractLegAttack) => this.LegAttack = abstractLegAttack;
    public void SetAbstractHandAttack(AbstractHandAttack abstractHandAttack) => this.HandAttack = abstractHandAttack;
    public void SetAbstractClinchWork(AbstractClinchWork abstractClinchWork) => this.ClinchWork = abstractClinchWork;
}

　ユーザによっては、"腕を使用した攻撃"にキックボクシング、"クリンチ状態の攻撃"にムエタイなど設定して整合性が取れなくなる可能性がある。

整合性をとる

抽象クラスの立ち技格闘技に各攻撃（一連のオブジェクト）を宣言し、 具象クラス（ムエタイ・シュートボクシング・キックボクシング）で各攻撃を定義する。

public abstract class AbstractStandingBout
{
    public abstract AbstractLegAttack CreateAbstractLegAttack();
    public abstract AbstractHandAttack CreateAbstractHandAttack();
    public abstract AbstractClinchWork CreateAbstractClinchWork();
}
public class MuayThai : AbstractStandingBout
{
    public override AbstractLegAttack CreateAbstractLegAttack()
        => new MuayThaiLegAttack();

    public override AbstractHandAttack CreateAbstractHandAttack()
        => new MuayThaiHandAttack();

    public override AbstractClinchWork CreateAbstractClinchWork()
        => new MuayThaiClinchWork();
}

　これによって、一連のオブジェクトの整合性は保てる。

具象クラスを指定することなく生成する

これまでのパターンだと以下のように具象クラスを指定することなく生成するは解決できていない。

var standingBout = new MuayThai();

　解決策は、抽象クラスで引数に応じて、具象クラスを作成するメソッドを追加する。

public abstract class AbstractStandingBout
{
    public abstract AbstractLegAttack CreateAbstractLegAttack();
    public abstract AbstractHandAttack CreateAbstractHandAttack();
    public abstract AbstractClinchWork CreateAbstractClinchWork();

    public static AbstractStandingBout CreateAbstractStandingBout(StandingBouts standingBouts)
    {
        return standingBouts switch
        {
            StandingBouts.MuayThai => new MuayThai(),
            StandingBouts.ShootBoxing => new ShootBoxing(),
            _ => new KickBoxing(),
        };
    }
}

クラス図

 

Singletonパターン

Singleton

生成に関するデザインパターン。
システムにクラスのインスタンスが1つのみであることを保証する。
一般的に"グローバルスコープ"からの呼び出しによく使われる。
しかし、"複数アクターに対して責任を持ってしまう"ため、SOLID原則の

単一責任の原則（Single Responsibility Principle） - おっさんの備忘録

に違反する。

// Singletonパターン
public class MySingleton
{
  private static MySingleton? mySingleton;
  
  public int UniqueValue { get; set; }
  
  private MySingleton() {}
  
  public static MySingleton GetInstance() => mySingleton ??= new();
}
// 動作確認
[TestClass]
public class SingletonUT
{
  [TestMethod]
  public void MySingletonUT()
  {
    var mySingleton1 = MySingleton.GetInstance();
    var mySingleton2 = MySingleton.GetInstance();
    Assert.AreEqual(mySingleton1, mySingleton2);
    
    mySingleton1.UniqueValue = 10;
    Assert.AreEqual(10, mySingleton1.UniqueValue);
    Assert.AreEqual(10, mySingleton2.UniqueValue);

    mySingleton2.UniqueValue = 15;
    Assert.AreEqual(15, mySingleton1.UniqueValue);
    Assert.AreEqual(15, mySingleton2.UniqueValue);
  }
}

SOLID原則

ソフトウェア設計をより平易かつ柔軟に保守するための原則。
原則は以下の5つあり、SOLIDはそれぞれの頭文字からきた造語。

ttkcd.hatenablog.com

ttkcd.hatenablog.com

ttkcd.hatenablog.com

ttkcd.hatenablog.com

ttkcd.hatenablog.com