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

前回の記事でDFSを作成したので、これを利用して初めに作ったPCパーツのグラフからすべてのパターンを求めていきたいと思います。

PCパーツのグラフは以下。

これを隣接行列で表すと以下。

プログラムは以下。

graph = [[0,0,0,1,1,1,0,0,0],[0,0,0,1,1,1,0,0,0],[0,0,0,1,0,1,0,0,0],[0,0,0,0,0,0,1,1,0],[0,0,0,0,0,0,1,1,0],[0,0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
costTable = [3000,4000,5000,6000,8000,9000,8500,13000,20000]
partsName = ['caseA','caseB','caseC','motherA','motherB','motherC','cpuA','cpuB','cpuC']
startVerNum = 3
vnum = 9
pathTable = []
def dfs(vertex, path):
    connectFlag = False
    pathIn = path.copy()
    for i in range(vnum):
        if(graph[vertex][i] == 1):
            connectFlag = True
            pathInTemp = pathIn.copy()
            pathInTemp.append(i)
            dfs(i, pathInTemp.copy())
    if(connectFlag == False):
        pathTable.append(pathIn.copy())
for i in range(startVerNum):
    dfs(i,[i])
for i in range(len(pathTable)):
    print(pathTable[i])
for path in pathTable:
    sum = 0
    for i in range(3):
        sum += costTable[path[i]]
    print(partsName[path[0]] + ',' + partsName[path[1]] + ',' + partsName[path[2]] + ':' + str(sum))

1行目で隣接行列をリストとして入力しています。

2行目はそれぞれのパーツの価格を入力しています。要素0番目がノード0に対応しています。

3行目はそれぞれのパーツの名前を入力しています。

4行目でDFSを始めるノードの数を入力しています。今回は開始ノードが0,1,2と3つ必要なので3が入力されています。

5行目はノード数9が入力されています。

6行目から17行目は前回の記事で紹介したDFSです。

for i in range(startVerNum):
     dfs(i,[i])

18行目と19行目でDFSを3回実行しています。開始ノードと開始時のパスを引数に関数dfsを実行しています。dfs(0, [0])、dfs(1, [1])、dfs(2, [2])が実行されます。

20行目と21行目で求めた経路を表示しています。

for path in pathTable:
    sum = 0
    for i in range(3):
        sum += costTable[path[i]]
    print(partsName[path[0]] + ',' + partsName[path[1]] + ',' + partsName[path[2]] + ':' + str(sum))

22行目から26行目で求めた経路をパーツの名前とその合計金額の形で出力しています。

22行目のfor文は2次元リストから行を一つずつ取り出して変数pathに代入する命令です。

path[0]にはPCケースのノード番号、path[1]にはマザーボードのノード番号、path[2]にはCPUのノード番号が入っています。

path[0]に0が入っているときcostTable[path[0]]はcostTable[0]となり、ノード0の価格がsumに加算されます。それをマザーボードとCPUでも実施します。

26行目でpathの名前と求めた合計を出力しています。

出力は以下となります。

[0, 3, 6]

[0, 3, 7]

[0, 4, 6]

[0, 4, 7]

[0, 5, 8]

[1, 3, 6]

[1, 3, 7]

[1, 4, 6]

[1, 4, 7]

[1, 5, 8]

[2, 3, 6]

[2, 3, 7]

[2, 5, 8]

caseA,motherA,cpuA:17500

caseA,motherA,cpuB:22000

caseA,motherB,cpuA:19500

caseA,motherB,cpuB:24000

caseA,motherC,cpuC:32000

caseB,motherA,cpuA:18500

caseB,motherA,cpuB:23000

caseB,motherB,cpuA:20500

caseB,motherB,cpuB:25000

caseB,motherC,cpuC:33000

caseC,motherA,cpuA:19500

caseC,motherA,cpuB:24000

caseC,motherC,cpuC:34000

このデータをどう使うかは使う人次第ですね。

この価格帯の構成は全部でどれほどか、このパーツを使った組み合わせは全部でどれほどかとか求めると少しは役に立つ？かな。

GPUやメモリなどは隣接行列が巨大になるだけなのでこれ以上は踏み込まないことにします。

またCPUとメモリ、CPUとGPUに依存関係がある場合、プログラムはより複雑になり、上記の単純なdfsでは求めるのが難しくなります。

しかしここではこれ以上踏み込まないことにします。

こういう組み合わせの求め方があるということの勉強になったということで。

以上「自作PCのパーツをグラフ理論とDFSで求める」でした。