アルゴリズムについての質問です

質問

アルゴリズムについての質問です。
以下のようなプログラムを考えています。

プログラムの目的
ある建物で各部屋同士の机の移動を行うため、その労力を最小にする組み合わせを求める。
※このシステムは他の人が使用することを考え、わかりやすいExcel（VBA）を使用しています。

画像に関して
＜図１＞は「No（部屋）」の距離（数字が小さい方が労力が少ない）を表しています。
※プログラムでこの表は出力されています
＜図２＞のようにA群とB群があり、A群からB群に移動する（複数移動も含む）場合について考えます。
＜図３＞のような最小の組み合わせを探します。

正しい結果は出るのですが、1件増えるだけで何倍何十倍と時間がかかってしまいます。
多少結果は妥協して(最小に近い値)でも処理を早くしたいと思っていますが、そのアルゴリズムが思いつきません。
作成したプログラムを下記にありますので、アドバイスをお願いいたします。
作成したプログラムで処理を遅くしている原因があれば指摘もお願いします。

---現在作成したプログラムです。（すべてのパターンを検証）-----------------
Dim 重みtab As Variant
Dim t01(100) As Integer '←A群が、「t01(1)」から順に入っています。
Dim t02(100) As Integer '←B群が、「t02(1)」から順に入っています。
Dim ttt(100) As Integer '←B群を並び替えた結果が入ります。

Sub 計算(移動数 As Integer) '「移動数」は「t01」「t02」の要素の数
Dim t03(100) As Integer
Dim a As Integer

重みtab = Range("重み表") 'Range("重み表") は ＜図１＞の「No」を含まないセル

'仮の最小の計算--------
min = 0
For a = 1 To 移動数
min = min + 重みtab(t01(a), t02(a))
ttt(a) = a
Next
'----------------------

Call 再帰関数(移動数, t03, 1)

'Sheet2に出力----------
For a = 1 To 移動数
Sheets("Sheet2").Cells(a, 1) = t01(a)
Sheets("Sheet2").Cells(a, 2) = t02(ttt(a))
Next
'----------------------

End Sub

Sub 再帰関数(移動数 As Integer, t03() As Integer, cnt1 As Integer)
Dim cnt2 As Integer
Dim flg As Boolean

For a = 1 To 移動数
flg = True
For b = 1 To cnt1 - 1
If t03(b) = a Then
flg = False
End If
Next
If flg Then
t03(cnt1) = a
If cnt1 < 移動数 Then
cnt2 = cnt1
cnt1 = cnt1 + 1
Call 再帰関数(移動数, t03, cnt1)
cnt1 = cnt2
Else
Call 処理(移動数, t03)
End If
t03(cnt1) = 0
End If
Next
End Sub

Sub 処理(移動数 As Integer, t03() As Integer)　　’最小であるか確認
Dim a As Integer
Dim b As Integer

For a = 1 To 移動数
b = b + 重みtab(t01(a), t02(t03(a)))
Next
If min > b Then
min = b
For a = 1 To 移動数
ttt(a) = t03(a)
Next
End If
End Sub

回答No.10

ki073 · ベストアンサー

No.9のプログラムを書いておきます。Rubyなので参考になるか分かりませんが一応、

require "narray"

# 労力合計を計算
def sum_work(grA, grB, works_na)
works_na[NArray.to_na(grA)*(works_na.shape[0])+NArray.to_na(grB)].sum
end

# 山登り法
def method1(grA, grB, works_na)
min=[sum_work(grA, grB, works_na), grB]
loop do
min2=(0...grA.size).to_a.combination(2).collect{|i, j| # 順番を入れ替える要素i,j
b=min[1].dup # B群の値をコピー
b[i], b[j]=b[j], b[i] # 入れ替え
[sum_work(grA, b, works_na), b] # 労力合計を計算
}.min_by{|c| c[0]} # 最小値を求める
break if min2[0]>=min[0] # 小さな値がなければ終了
min=min2 # 最小値を書き換え
end
[min[0], grA, min[1]] # [sum_work, A, B]
end

# 初期値3
def method3(grA, grB, works_na)
grB_rot=(grB+grB[0..-2]).each_cons(grB.size).to_a # Bのローテイト配列
grB_rot.collect{|b|
method1(grA, b, works_na)
}.min_by{|c| c[0]}
end

B群のランダムに並び替えて初期値としたものを追加
最小の労力合計が一定回数（ここでは5回）に達したら答えとする方法です。
アルゴリズムが簡単なので捨てがたいです。

# 初期値をランダムに
def method5(grA, grB, works_na)
rand_results=[]
begin
b=grB.sort_by{rand} # B群をランダムな順番に並び替え
rand_results<<method1(grA, b, works_na)
min=rand_results.min_by{|c| c[0]}
end until rand_results.select{|c| c[0]==min[0]}.size>=5
min
end

お礼

お礼が遅くなりました。申し訳ありません。
ki073 さんの「山登り法」を使わさせていただきサクサクと処理ができています。

A群、B群がそれぞれ1000件ぐらいでも多少待ちますが、苦にならないほど早く処理がなされます。
初期値は提案していただいたものを比較させていただき、
A群[1:2:3:4:5]
B群[1:2:3:4:5]
　　　↓
A群[1:2:3:4:5]
B群[5:1:2:3:4]
　　　↓
A群[1:2:3:4:5]
B群[4:5:1:2:3]
と要素を順にずらして一番最小のものを使用しております。

このアルゴリズムを元に、A群、B群の要素数が違う場合の処理も考えて作成しております。
親身に考えてくださってありがとうございました。

回答No.9

ki073

総当たり法はどうしても限界があるので、昨夜「山登り法」を試してみました
http://ja.wikipedia.org/wiki/山登り法

アルゴリズム１
1. A群,B群の初期値を与えます（後述）
2. 労力の合計を計算する(労力合計１とする)
3. B群の中の２つの要素を入れ替えた組み合わせを作る(組み合わせが28ある)
4. それぞれについて労力の合計を計算する
5. 労力合計１より小さいものがあれば、一番小さいものに置きかえ、労力合計１を書き換え3にもどる。小さいものが無ければ終了
以上です。

初期値１
A群,B群をそのまま初期値とする
誤差0が962個、誤差2が27、誤差4が3、誤差6が1、誤差10が5、誤差12が1、誤差20が1
原理的にどうしても誤差の大きなものがでる可能性がある

初期値２
No.2の提案1の結果を初期値に
誤差0が985個、誤差2が14、誤差8が1
提案1より改善されています

初期値３
B群を１つずつローテーションした値（８組）を初期値とし、８組全部を計算し最小のものを使用
全部誤差0

初期値４
No.2の提案1の７をやる前の値（８組）を初期値とし、８組全部を計算し最小のものを使用
全部誤差0

山登り法は初期値により局所的な頂上に行ってしまうことが原理的に避けられませんので、初期値３よりも、初期値４の方が安心して使えるように思います。

回答No.8

Tacosan

机の過不足関係を供給・需要と思い, ある部屋から別の部屋への距離を費用とすれば, そのまま最小費用流だよね.

お礼

お礼が遅くなりました。申し訳ございません。
「最小費用流」納得しました。

しかし、それをプログラムに起こすことができませんでした。
アイディアをありがとうございます。

回答No.7

ki073

No.4です。
＞１００個のデータというのは、A群：１００個　B群：１００個でしょうか。
8個の数値からなるA群を作って、数値が重ならないように8個の数値からなるB群を作るという方法です。
それを100組分作ってチェックしました。要するに図2を100組です。

さらに1000組まで増やして計算した誤差です。
誤差0が668, 誤差2が261, 誤差4が49, 誤差6が10, 誤差8が6, 誤差10が4, 誤差12が1, 誤差14が1という結果です。

プログラムをざっと見たのですが、
重みtab(t01(a), t02(a))
などように重みtabのなかにt01(a)のように配列がはいっているのをやめて、
最初に重みtabの必要な部分だけを取り出したA群数×B群数の大きさの配列（抜き出した重みtab）をつくってしまったらどうでしょうか。
そうすると「抜き出した重みtab(a,a)」で取り出せますので、多少は速くなりそうな気がします。
それとNo.1でも指摘されていますが、再帰呼び出しは一般的にはかなり遅くなります。普通にぐるぐるループを回した方が速いです。

回答No.6

nag0720

＃３です。

＃３の回答に誤りがありました。
1～4を第１グループ(G1)
5～9を第２グループ(G2)
10～13を第３グループ(G3)
14～18を第４グループ(G4)
です。（コピー＆ペーストしたあと変更し忘れました）

＞人力でグループ分けをするのは避けたいと思っております。
＞＜図１＞の補足ですが、
＞別のシートで、建物の上から見た図を階数ごとに作成できるようになっていて、
＞そこから、プログラムで部屋ごとの距離（重み）を＜図１＞に出力しています。

別シートにどんな情報があって、どのようなプログラムで＜図１＞を出力しているのか分かりませんが、
その別シートの情報からは自動でグループ分けすることができないんでしょうか？

＜図１＞を見ると、
「1～4は近接していて、5～9は同じ階の少し離れたところに近接していて、10～13、14～18は別の階に1～4、5～9と同じ位置関係にある」
と想像できますが、別シートの情報からそのようなことを判断するのは難しいのでしょうか？
もしそうなら、グループ分けは手作業でやるしかないでしょう。

それとも、図面を見てもグループ分けすること自体が難しいのでしょうか？
そうであればこの方法は使えません。

お礼

ありがとうございます。

実際に今回のデータは１～９が１階、１０～１８が２階で、１～９と１０～１８はそれぞれ上下の関係にあり、１～４と５～９は離れています。階段は、３、５の近くに２か所あります。
しかし、今回のようにキレイにグループ分け出来るような間隔で部屋があるとは限りません。
例えば４と５の部屋のちょうど間に部屋が来るような場合があるかも知れず、その点を考慮すると、グループで分けて考えるのは難しいように感じます。
また、同じ階でも、端から端に移動するより、上下に移動する方がいい場合もあるので、各部屋への移動する労力を数値化して＜図１＞表を作成する方法をとりました。

回答No.5

Tacosan

「最小費用流」っぽい.

お礼

回答ありがとうございます。

「最小費用流」を調べましたが、よくわかりませんでした。
もう少し詳しく教えていただけますか？

回答No.4

ki073

こういう問題は整数計画法という分野が有って、アルゴリズムもできています。
EXCELにもそのためのソルバーがあります。整数計画法で検索してみてください。ちょっと取っ付きにくいところがあるのですが、利用するのは簡単です。もし興味が有りましたら書き込んでください。

No.2で提案されている提案1ですが、ちょっとやってみました。ランダムに100個のデータを発生させて図1のデータを使っやりました。
総当たり法と、提案1による比較では提案1の正答率は43%で、誤差があった場合の大半は2大きく出ている程度ですので近い値にはなるような感じです。最大の誤差は12のものがありましたので、これをどう見るかですが。
（実際にはEXCELではなくRubyでやっています。この場合は100個で総当たりの実行時間が1秒程度です）

お礼

回答ありがとうございます。

整数計画法を調べましたが、おっしゃる通り難しいですね。
ソルバーは、ソルバーアドインをインストールする必要がありますよね。
インストール等は行いたくありません。
特定のPCで行うわけではなく、また、PCには環境復元ソフトが入っているため、インストールが難しいです。

No.2の提案を試してくださり、ありがとうございます。
誤差は２程度ですか。このくらいなら妥協できる範囲だと思います。
ただ１２の誤差が出るのは、気になりますね。
１００個のデータというのは、A群：１００個　B群：１００個でしょうか。

回答No.3

nag0720

＞多少結果は妥協して(最小に近い値)でも処理を早くしたいと思っていますが、

ということなら、

＜図１＞を見ると、部屋Noがグループ化できることが分かります。

1～4を第１グループ(G1)
5～9を第１グループ(G2)
10～13を第１グループ(G3)
14～18を第１グループ(G4)

とすれば、＜図２＞のＡ群、Ｂ群は、

Ａ群：G2,G2,G2,G3,G4,G4,G4,G4
Ｂ群：G1,G1,G1,G2,G2,G3,G3,G3

となります。さらに＜図１＞から、

G1⇔G1、G2⇔G2、G3⇔G3、G4⇔G4　の移動労力を０
G1⇔G2、G1⇔G3、G2⇔G4、G3⇔G4　の移動労力を１
G1⇔G4、G2⇔G3　の移動労力を２

と簡略化できるので、これでＡ群からＢ群への最小移動のグループの組み合わせを求めます。
これなら、すべての組み合わせの総数はかなり少なくなるので時間を短縮できるはずです。

これができたら、それぞれのグループを元の部屋Noに戻して、グループ内での最小移動の組み合わせを求めます。
ただし、Ａ群からＢ群への最小移動のグループの組み合わせは１つとは限りません。複数あったら、それぞれに対してこの処理をして、最小の移動労力を調べる必要があります。

お礼

回答ありがとうございます。

画像にある＜図１＞データですが、これは変わる可能性があるので、値が変わると、グループを考え直さなければなりません。
グループ分けを素早くプログラム上でできるでしょうか。
人力でグループ分けをするのは避けたいと思っております。

＜図１＞の補足ですが、
別のシートで、建物の上から見た図を階数ごとに作成できるようになっていて、
そこから、プログラムで部屋ごとの距離（重み）を＜図１＞に出力しています。

回答No.2

utun01

ソースは書いていませんが、アルゴリズムレベルのご提案です。

提案１：ベターな解を求める
１、A群の要素(1)から最も近いB群の要素Xを探し、これを確定します。
２、A群の要素(2)以降も同様に確定していきます。
３、一通り終わったらこの結果を保存しておきます。
４、最初に戻りA群の要素(2)から最も近いB群の要素Xを探し、これを確定します。
５、A群の要素(1),(3)～を同様に処理します。
６、残りを同様に処理します。
７、A群の要素数分の解が出ているので、この中から最小の値を探す。

提案２：最適解を求める
ご提示されたソースは読み込んでおりませんが、「再帰関数」部分をクイックソート的なアルゴリズムに変えることが出来れば改善されるように思います。

その他：
「重みtab」はrangeオブジェクトのまま使用すべきではありません。
別途テーブル用のクラスを作り、そこで管理すべきです。
Excelオブジェクトへのアクセスは非常に重たい処理ですので、これを改善するだけで一気に改善される可能性があります。
また、重い処理をする際にはExcelの描画と計算を止めて下さい。
http://www.asahi-net.or.jp/~ef2o-inue/vba_o/sub05_090_040.html

お礼

回答ありがとうございます。

提案１
そのようなアルゴリズムも頭の中では考えていましたが、あまり小さい値が出てこないのではないかと思い、試していませんでした。
今度試して妥協できるような値が出るかを確認してみたいと思います。

提案２
「クイックソート」はわかるのですが、今回のプログラムにどのように活用できるか、見当もつかないのですが、もう少し説明を加えていただけますか。

＞「重みtab」はrangeオブジェクトのまま使用すべきではありません。
ループで値だけテーブルに代入するプログラムを作成するということですね。
試してみます。

回答No.1

Tacosan

図2 の数字の意味が分かりません.

お礼

説明が足りませんでした。

＜図２＞のＡ群、Ｂ群は部屋番号を表しています。
Ａ群にある一番初めの要素「５」は、「５」の部屋から机を持ち出したい（机がいらない）
Ｂ群にある一番初めの要素「１」は、「１」の部屋に机を持ってくる（机が必要である）

Ａ群の「１５」は2つありますが、それは、机が2ついらないことを表しています。
Ｂ群も同じで、同じ数字が２つある場合は２つ必要であることを表しています。
※同じ数字が３つ４つとなる可能性もあります。