電気回路の配線長を最適化するC++プログラムの実装方法

本記事では、電気回路における配線長(ワイヤ長)を最適化するC++プログラムを紹介します。このプログラムは、グラフ理論の代表的なアルゴリズムであるダイクストラ法を応用し、起点となる部品から各電子部品までの最短距離を求めることで、回路全体の配線を効率化します。

アルゴリズムの概要

配線長の最適化は、以下の手順で行われます。

1. 距離を格納する配列 dist[N] を宣言します。
2. sptSet[i] は、部品 i が最短経路木に含まれているか、あるいは始点 src から i までの最短距離が確定している場合に true となるフラグです。
3. すべての距離を無限大(INT_MAX)で初期化し、sptSet[] をすべて false に設定します。
4. 始点部品自身からの距離は常に 0 とします。
5. cnt = 0 から N-2 までループを実行し、すべての部品について最短経路を求めます。
   • A) まだ処理されていない部品の集合から、距離が最小の部品を選択します。
   • B) 選択した部品を「処理済み」としてマークします。
   • C) 選択した部品に隣接する部品の dist 値を更新します。
   • D) 部品 v が sptSet に含まれておらず、u から v への辺が存在し、u を経由する始点から v までの経路の総重量が現在の dist[v] よりも小さい場合にのみ、dist[v] を更新します。

サンプルコード

#include <limits.h>
#include <iostream>
using namespace std;
#define N 6

// 最小距離を持つ部品を見つける関数
int minDist(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < N; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

// 結果を表示する関数
void displaySolution(int dist[], int n) {
    cout << "Component\tDistance from other component\n";
    for (int i = 0; i < n; i++)
        printf("%d\t\t%d\n", i, dist[i]);
}

// 配線長を最適化する関数
void optimizeLength(int g[N][N], int src) {
    int dist[N];
    bool sptSet[N];
    for (int i = 0; i < N; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    dist[src] = 0;

    // すべての部品に対して最短経路を求める
    for (int cnt = 0; cnt < N - 1; cnt++) {
        // 未処理の部品の中から最小距離の部品を選択
        int u = minDist(dist, sptSet);
        // 選択した部品を処理済みとしてマーク
        sptSet[u] = true;
        // 選択した部品に隣接する部品のdist値を更新
        for (int v = 0; v < N; v++)
            if (!sptSet[v] && g[u][v] && dist[u] != INT_MAX
                && dist[u] + g[u][v] < dist[v])
                // sptSetに含まれず、uからvへの辺があり、
                // u経由の経路の方が現在値より小さい場合のみ更新
                dist[v] = dist[u] + g[u][v];
    }
    displaySolution(dist, N);
}

int main() {
    int g[N][N] = { { 0, 0, 6, 7, 0, 4}, { 4, 0, 8, 0, 1, 2 },
        {0, 9, 0, 2, 0, 4 }, { 0, 0, 7, 0, 9, 5 },
        { 0, 1, 0, 0, 6, 7 }, { 6, 7, 0, 0, 2, 3} };
    cout << "Enter the starting component: ";
    int s;
    cin >> s;
    optimizeLength(g, s);
    return 0;
}

コードの解説

このプログラムは、隣接行列 g[N][N] を用いて電子部品間の接続関係とその重み(配線の長さやコスト)を表現しています。要素が 0 の場合は、対応する部品間に直接の接続がないことを意味します。

• minDist():未確定の部品の中から最も距離が近い部品のインデックスを返します。
• displaySolution():各部品の始点からの距離を一覧表示します。
• optimizeLength():ダイクストラ法のコア部分を実装しており、計算量は O(N²) です。

実行結果

Enter the starting component: 4
Component Distance from other component
0   5
1   1
2   9
3   11
4   0
5   3

結果の読み方

この実行例では、部品 4 を始点として入力しています。出力は、始点である部品 4 から各部品までの最短距離を示しています。例えば、部品 4 から部品 1 までは距離 1、部品 3 までは距離 11 であり、これらの値を採用することで回路全体の配線長を最小限に抑えられます。

まとめ

ダイクストラ法を電気回路の配線設計に適用することで、各部品間の最短接続距離を体系的に求めることができます。単一始点最短経路問題として定式化することで、プリント基板のレイアウト設計や配線コストの削減など、実際の回路設計の場面でも応用可能な手法です。