複数個の対象を特定の規則によって効率よく並び替える方法

下図表中の「並び替える対象」にあるようなデータ（以下、"製品"）
を特定の規則で並べる時の全ての並び順を出力したいです。

並び替えの規則は「条件」のテーブルに示した様に
各製品同士を前後に並べることが可能か不可能か定義されています。
（表の1行目で言うとAの次にBを並べるのは１＝可能）

現在VBAでテスト的に作成したプログラムでは

①1つ目の製品を選ぶ
②次に並べることが可能な製品を選ぶ
③②を繰り返す
④次に並べることができる製品が無く、行き詰った場合は１つ前の製品に戻り、
行き詰まった製品を除外して②を再実行
⑤全製品が並びきれたら完了
⑥次のパターンへ…（繰り返し）

という方式で、並び替えパターンの出力には成功しています。

しかし、この方式では
並べることができる全ルートを試行して並び切るかどうか検証するため、
製品数が大体10以上になると計算量が増え、
使用できるレベルではなくなってしまいます。
(実際の使用時は製品数20~30になります）

上記のような並び替えをより効率的に並び替えるための良い考え方やアイデアがあれば
教えて頂きたいです。

現在はVBAでテストしていますが、
他のツールでの実現可能性があれば試してみたいと考えています。

よろしくお願いいたします。

sk.exe

2022/11/15 08:38

・ADOを用いて自己結合クエリの実行結果を得る。・PowerQueryを用いて上記と同種の結果を得る。今のところ思いつくのは以上のいずれかです。

actorbug

2022/11/15 09:08 編集

そもそも、製品数20~30の全ての並び順を出力することは、現実的に可能なのでしょうか。仮に「可否」をすべて1にしたとすると、並び順の総数は20!~30!となり、兆をはるかに超えるとんでもない数になります。

UZM

2022/11/15 09:52

sk.exe様アドバイス頂きありがとうございます。 ADOやPowerQueryについての知識が無いので調べてみます。 actorbug様コメント頂きありがとうございます。可否ですが実際には「否」の比率が多く、最初に並べる製品によってはどう組み合わせても並びきれない場合すらあります。しかしそれでも総数は多くなる可能性はあると思います。その場合は妥協案として「各製品を先頭にした場合の組み合わせを1組ずつ出力する」というアウトプットでも大きな問題は無いです。（各製品先頭で並びきる組み合わせが見つかった時点で次の製品先頭で移る、というコードを書き加える）実際にこの妥協案をVBAにて製品数20程度で試してみましたが、並び切る組み合わせが見つかるまで無数の組み合わせを検証し続けるのに時間がかかるような状態です。質問本文の①〜⑥のやり方ではおそらく現実的に並べるのは難しいと思っています。何か別の方法や参考になる考え方がないかと思いご相談させて頂きました。

actorbug

2022/11/15 11:30

並び変える対象を節点、条件を辺とみなすと、この問題はハミルトン路を列挙する、という問題となります。 https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3%E8%B7%AF こちらによると、「与えられたグラフがハミルトン路を含むかどうか判定する問題は、NP完全問題。」だそうです。つまり、1つの並び順を見つけることですら難しいということです。

UZM

2022/11/15 12:58

ご返信ありがとうございます。グラフ理論という分野があるのですね。確かにハミルトン路の考え方が適応できる様です。今回の問題の場合、条件によっては辺が一方通行の場合があるため、直感的にですが、より複雑な問題になるようにも思えます。あまりこの方法に固執しすぎず、別のアプローチでの問題解決も考える様にします。

行動規範の内容に同意します

回答1件

ベストアンサー

動的計画法を使って作成してみましたが、時間計算量O(N*2^N)、空間計算量O(2^N)となってしまい、製品数が多くなると厳しいです。製品数30だと、最適化したC++で4GB超のメモリを使用して1分以上の時間をかけて、ようやく計算が終わるレベルです。これをこのままVBAに移植しても、動作させるのは厳しいでしょう。

c++
1#include <iostream>
2#include <vector>
3#include <cstdint>
4using namespace std;
5
6int main() {
7	// 製品数と、可否が1の条件の数
8	uint32_t N, M;
9	cin >> N >> M;
10
11	// 製品 ⇒ 後ろに並べられる製品群
12	vector<uint32_t> edge(N);
13	for (uint32_t i = 0; i < M; ++i) {
14		uint32_t a, b;
15		cin >> a >> b;
16		edge[a] |= 1 << b;
17	}
18
19	// 製品群 ⇒ その製品群を全て並べた際に先頭になりえる製品群
20	vector<uint32_t> start(1ull << N);
21	for (uint32_t i = 1; i < start.size(); ++i) {
22		// 製品が1つの場合は、その要素を並べればOK
23		if ((i & (i - 1)) == 0) {
24			start[i] = i;
25			continue;
26		}
27		// 製品群内の製品それぞれについて
28		for (uint32_t j = 0; j < N; ++j) {
29			if (!(i & (1 << j)))
30				continue;
31			// その製品の後ろに並べられる製品が、残りの製品群の先頭になりえるなら、
32			// その製品は先頭になりえる
33			if (edge[j] & start[i & ~(1 << j)])
34				start[i] |= 1 << j;
35		}
36	}
37
38	// 各製品を先頭にした場合の組み合わせを1組ずつ出力
39	for (uint32_t i = 0; i < N; ++i) {
40		uint32_t x = (1 << N) - 1;
41		// その製品が先頭になりえないなら飛ばす
42		if (!(start[x] & (1 << i)))
43			continue;
44		uint32_t j = i;
45		while (true) {
46			// 表示
47			cout << j << ' ';
48			x &= ~(1 << j);
49			if (x == 0)
50				break;
51			// 現在の製品の後ろに並べられて、残りの製品群の先頭になりえる製品を選ぶ
52			uint32_t y = edge[j] & start[x];
53			for (j = 0; !(y & (1 << j)); ++j)
54				;
55		}
56		cout << endl;
57	}
58}

入力は標準入力から渡す前提です。先頭行に製品数と可否が1の条件の数、2行目以降に可否が1の条件の並び(製品は0始まりの番号)となっています。例えば、製品数3でAB,BC,CAの並びのみ可能だと以下のようになります。

実行すると、各製品を先頭にした場合の組み合わせを1組ずつ標準出力に出力します。

C++の知識がないとのことなので、VBScriptで書き直したものを載せておきます。(Excelは手元にないので)
入力(形式は上で説明した通り)をテキストファイルに保存したうえで、このVBScriptにドラッグ&ドロップすれば動作します。
こちらで試した限りでは、製品数20で10秒以上かかっています。やはり動作させるのは厳しそうです。

vb
1Option Explicit
2Dim objFSO, objTextStream
3Set objFSO = WScript.CreateObject("Scripting.FileSystemObject")
4Set objTextStream = objFSO.OpenTextFile(WScript.Arguments(0))
5
6' 製品数と、可否が1の条件の数
7Dim aryStrings, N, M
8aryStrings = Split(objTextStream.ReadLine())
9N = CInt(aryStrings(0))
10M = CInt(aryStrings(1))
11
12' 製品 ⇒ 後ろに並べられる製品群
13Dim edge(), i, a, b
14ReDim edge(N - 1)
15For i = 1 To M
16    aryStrings = Split(objTextStream.ReadLine())
17    a = CInt(aryStrings(0))
18    b = CInt(aryStrings(1))
19    edge(a) = edge(a) Or 2 ^ b
20Next
21objTextStream.Close()
22
23' 製品群 ⇒ その製品群を全て並べた際に先頭になりえる製品群
24Dim start(), j
25ReDim start(2 ^ N - 1)
26For i = 1 To UBound(start)
27    ' 製品が1つの場合は、その要素を並べればOK
28    If (i And i - 1) = 0 Then
29        start(i) = i
30    Else
31        ' 製品群内の製品それぞれについて
32        For j = 0 To N - 1
33            If i And 2 ^ j Then
34                ' その製品の後ろに並べられる製品が、残りの製品群の先頭になりえるなら、
35                ' その製品は先頭になりえる
36                If edge(j) And start(i Xor 2 ^ j) Then
37                    start(i) = start(i) Or 2 ^ j
38                End If
39            End If
40        Next
41    End If
42Next
43
44' 各製品を先頭にした場合の組み合わせを1組ずつ出力
45Dim x, y, ret
46For i = 0 To N - 1
47    x = 2 ^ N - 1
48    ' その製品が先頭になりえるなら
49    If start(x) And 2 ^ i Then
50        j = i
51        ret = ""
52        Do
53            ret = ret & j & " "
54            x = x Xor 2 ^ j
55            If x = 0 Then Exit Do
56            ' 現在の製品の後ろに並べられて、残りの製品群の先頭になりえる製品を選ぶ
57            y = edge(j) And start(x)
58            For j = 0 To N - 1
59                If y And 2 ^ j Then Exit For
60            Next
61        Loop
62        WScript.Echo ret
63    End If    
64Next

投稿2022/11/17 20:56

編集2022/11/19 05:48

actorbug

総合スコア2224

UZM

2022/11/18 05:17 編集

ご回答ありがとうございます。書いて頂いたコードですが、 C++の知識がないので調べながら解読してみます。この方法でもVBAでは難しいと思われるとのことですが、実現可能ならばVBAにはこだわりません。また素人ながら、なにか良い方法がないか模索しており、遺伝的アルゴリズムを使用する方法はどうかと考えています。・ランダムな並びを親として、これらを交叉して子世代を生成する・各個体の並びのうち、製造可に適応した前後組合せの割合を得点（選別基準）として選別する　例）個体"123456"で製造可能組合せが"2⇒3"のみなら個体の得点は「1/5=20%」・上記を得点100%の個体が現れるまで繰り返す（最悪90%程度で残った製品は人力で並べる？）並び順を全て網羅することはできませんが、これで1つの解を見つけ出すことができる可能性はないでしょうか。（調べただけの感覚ですが、交叉や選別のやり方・調整次第で現実的な時間で解にたどり着くかどうか、変わりそうかなと思っています。) そもそもの本件の目的としては、人力で製品を並び替えているのを自動化することなのですが、それが難しい場合はある程度まで並べて後は人力という半自動化でも効果はあると思っています。

actorbug

2022/11/18 15:57 編集

そもそも2つの並びの交叉を作るのが難しいです。単純に両者の適当な場所で入れ替えるだけだと、同じ製品が並びに複数現れるのを防ぐことができません。例えば、123456と654321を交叉させるとき、中央で分けて入れ替えるだけだと、123321と654456となり、全製品を並べたものにならなくなってしまいます。また、遺伝的アルゴリズムは、90%の解でも有用であるような場合に使うものだと思います。今回の問題は、90%の並びを見つけたとしても、それが100%の並びに近いとは限りません。例えば、4製品でAB, BC, DC, CB, BAが許される場合、66%の並びABCDと、100%の並びDCBAとは、近いとはいいがたいと思われます。英語版Wikipediaに、解くためのアルゴリズムがいくつか載っているようです。(私にはさっぱりわかりません) https://en.wikipedia.org/wiki/Hamiltonian_path_problem 私のやり方は、以下のページで解説されているものと近いです。 https://stackoverflow.com/questions/31439209/how-to-check-for-existence-of-hamiltonian-walk-in-o2n-of-memory-and-o2n-n

UZM

2022/11/20 02:32

交差についてですが、調べてみると順序問題の交叉方法は色々と考案されているようです。方法は様々あるので本件に適したものを選ぶのは難しそうとは思いますが。 90%の解では…の問題についてですが、頂いたご意見のもと考え直すと「100%まで行かなくても残りは人力で並べる」という考え方ではダメでした。製品数が20〜30になれば100%に近い並びが出ると思っていましたが、「123456789」というならびで5→6が製造不可だった場合、 5,6を人力で並べるために除いたところで「1234」と「789」が繋がるとは限りませんね。リファレンスまで頂きありがとうございました。

UZM

2022/11/20 02:49

・100%にならなくてもいくつか出力する・特定の製品のせいで並べられないという傾向が分かれば、それは人力で並べるものとして抜く・上記製品を抜いた製品群で100%を目指すという方法も考えましたが、前提が多く実現可能性は高くないような気がしています。

actorbug

2022/11/20 03:16 編集

正直、もう私の回答とは無関係な話になっているので、質問へのコメントに戻るか、別の質問を作ってそちらで相談してもらえませんか。私としては、この問題については以下の主張しかありません。・最終的に20～30個の製品をすべて並べないといけないのであれば、高速な解法は存在しない　(巡回セールスマン問題のように、最善でなくても意味があるならともかく)

UZM

2022/11/21 01:35

わかりました。 VBScriptでの書き換えして頂いていたことに今気づきました。丁寧なご回答ありがとうございました。

UZM

2022/11/21 08:23 編集

度々の質問申し訳ありません。 VBSのコードの最後のFor文の箇所について、製品群yが0になってしまった場合、（＝「現在の製品の後ろに並べられて、残りの製品群の先頭になりえる製品」がない場合） j=N-1でFor文を抜けて、Loopする…といったことは起こらないのでしょうか。すると「x = x Xor 2 ^ j」の処理によって、 xのN-1の桁が1⇄0と無限にループしてしまうように思えるのですが、そうなならないのでしょうか。

actorbug

2022/11/21 12:56

そのようなことは起こりえません。一つ前のループ内で、事前に同じ条件で判定を行っていて、yが0になるような組み合わせの場合には、start(i)にフラグを立てない(=先頭になりえる製品に含めない)ようにしています。

UZM

2022/11/21 23:49

ご回答ありがとうございます。納得致しました。 "その製品の後ろに並べられる製品が、残りの製品群の先頭になりえるなら"の条件があるため、 y=0になるような製品は前製品の時点で選ばれないということですね。

行動規範の内容に同意します