Python

自作PCのパーツをグラフ理論とDFSで求める1

Python

[PR]当サイトはアフィリエイト広告を利用しています。

今回は自作PCのパーツの組み合わせをプログラムで求めてみます。

私も自作PCは何台か所有していますが、パーツをどう選択するかは結構悩みます。

たくさんのパーツからどれとどれを組み合わせるか、選択肢が多いのがその理由の一つだと思います。PCケースはミニタワー、マザーボードはAMD用でMicro ATX、するとCPUはIntelが使えないからRyzenか。

そんな組み合わせ上の制約も考える必要があります。

そこで今回は「パーツの組み合わせを求めてみよう」というテーマです。

このプログラムを使っても自作PCのパーツ選びにはおそらくあまり役には立たないと思います。

最終的にプログラムを実行してみたら、この価格帯の組み合わせってこんなにあるんだという発見があっただけでした。

多少利点があるとすれば、あまりif文の条件を記述せずにパーツとパーツのつながりが追えるというのが利点といえば利点のような気がします。

ただ発展させてメモリとCPUの依存関係までやろうとすると例外処理が生じてプログラムは複雑になります。今回の一連の記事ではそこまで立ち入らないことにします。

完成したプログラムを走らせて思ったのは、データベースソフトの中でやってる処理ってこんな感じなのかなあということでした。

同じことはAccessでできるかもしれない。

そのくらいの話ですがプログラミングの練習にはなったかなということで記事にしました。

使う知識はグラフ理論と深さ優先探索(DFS: depth-first search)です。

最終的にパーツの組み合わせが求まるまで長い旅ですが、さっそく始めましょう。

グラフ理論

まずこの記事ではパーツをグラフ理論でグラフに表すまでを説明します。

グラフ理論とはグラフに関する理論です。

ここでいうグラフとは、折れ線グラフや棒グラフのようなグラフではなく、点と線で表現された、情報と情報のつながりを表現したものです。

上の例では情報がA,B,C,D,Eと5つあり、情報間につながりがあればそこに線が引かれています。ここでいうグラフとは上のようなものです。

その情報をこの記事ではノードと呼ぶことにします。Aの情報はノードAです。

グラフ理論は大学の数学の講義で勉強することもあるようです。私は以下の本で勉強しました。詳しく学習したい方はそちらをどうぞ。

小林みどり(2013)『あたらしいグラフ理論入門』牧野書店.

さてこの理論を使ってPCパーツを表現してみようと思います。

上のグラフの使い方ですが、まずPCケースを選択します。そこから線をたどれるマザーボードを選択します。さらにそのマザーボードから線をたどれるCPUを選択します。

そうすると線をたどることでパーツの組み合わせが求まります。

グラフは有向グラフにしています。無向グラフだと後々のプログラミングで探索アルゴリズムがノードを行ったり来たりしてうまくいかないからです。

また本来はPCケースとマザーボードとCPU以外にグラフィックボードやメモリなども選ばなければなりません。

しかし簡単に原理を説明するために上の三種類それぞれ三つ、計9つのパーツで解説していきます。

次にそれぞれのノードに付けられた名前を番号に置き換えます。

そのほうがプログラミングするときに都合がいいからです。

PCケースA(ミドルタワー)はノード0、マザーボードA(Micro ATX,AMD)はノード3に置き換えられます。

ノード数9個のグラフになりました。

番号の付け方は自由ですが、パーツの種類ごとに連番で番号をふった方がやりやすいです。

PCケースの番号付けが終わってから、マザーボードの番号付けをします。

PCケースA、マザーボードA、CPU Bを選択した場合、ノードの組み合わせは(0, 3, 7)となります。

この組み合わせをすべて求めてみようというのが今回の目的です。

ここでそのパターンを求める方法が次回の記事で出てくる深さ優先探索(DFS)です。

次回に続きます。