質問編集履歴
4
改善
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -38,11 +38,11 @@
|
|
|
38
38
|
|
|
39
39
|
|
|
40
40
|
|
|
41
|
-
コネクト
|
|
41
|
+
コネクト(繋げなければならないノード同士)
|
|
42
42
|
|
|
43
|
-
繋げたい
|
|
43
|
+
繋げたい出発地点のノード番号
|
|
44
44
|
|
|
45
|
-
繋げる
|
|
45
|
+
繋げる目的地点のノード番号（複数あり）
|
|
46
46
|
|
|
47
47
|
|
|
48
48
|
|
|
@@ -64,7 +64,7 @@
|
|
|
64
64
|
|
|
65
65
|
|
|
66
66
|
|
|
67
|
-
それぞれグループごとにコネクト通りに、つまり
|
|
67
|
+
それぞれグループごとにコネクト通りに、つまり出発地点からどこかの経路を通って到着地点のノードに繋げなければなりません。
|
|
68
68
|
|
|
69
69
|
なおかつ、同じ辺を使うのを避け、辺の重複度を最小化したいという問題です。
|
|
70
70
|
|
|
@@ -118,7 +118,9 @@
|
|
|
118
118
|
|
|
119
119
|
そして、グループ内で通る経路の重複度の合計最大値を最小化することが目的である。
|
|
120
120
|
|
|
121
|
+
この例だと重複度合計はグループID.0は4,ID.1は3,ID.2は3,
|
|
122
|
+
|
|
121
|
-
|
|
123
|
+
よって最大値は４である。
|
|
122
124
|
|
|
123
125
|
|
|
124
126
|
|
|
@@ -137,3 +139,7 @@
|
|
|
137
139
|
|
|
138
140
|
|
|
139
141
|
例えば、先にルーティングしておくと比較的、後の経路が重複しなくなるようなグループの順番でルーティングする方法（どうすればいいか探す必要がありますが。。）や、数理計画法のようなアプローチができるかと考えましたが、他に良い方法がありませんでしょうか？
|
|
142
|
+
|
|
143
|
+
|
|
144
|
+
|
|
145
|
+
様々なアイデアをいただければありがたいのと、似たような解法が紹介されているサイトなどあれば教えていただきたいです。
|
3
補足図追加
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -80,7 +80,7 @@
|
|
|
80
80
|
|
|
81
81
|
|
|
82
82
|
|
|
83
|
-
**※補足 不可な例です。**
|
|
83
|
+
**※補足図１ 不可な例です。**
|
|
84
84
|
|
|
85
85
|
|
|
86
86
|
|
|
@@ -100,7 +100,7 @@
|
|
|
100
100
|
|
|
101
101
|
|
|
102
102
|
|
|
103
|
-
**補足 以下もエッジ５-６が使われているのでそれより１番目の例の方が最適であると言えます。**
|
|
103
|
+
**補足図２ 以下もエッジ５-６が使われているのでそれより１番目の例の方が最適であると言えます。**
|
|
104
104
|
|
|
105
105
|
|
|
106
106
|
|
2
問題補足
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -56,6 +56,10 @@
|
|
|
56
56
|
|
|
57
57
|
例として以下のようにグラフがあり、コネクト、グループがあるとします。
|
|
58
58
|
|
|
59
|
+
|
|
60
|
+
|
|
61
|
+
**※補足 グラフは有向グラフです。双方向につながるわけではありません。向きも考慮しなければなりません。**
|
|
62
|
+
|
|
59
63
|
|
|
60
64
|
|
|
61
65
|
|
|
@@ -68,7 +72,7 @@
|
|
|
68
72
|
|
|
69
73
|
例えば、グループID.0をルーティングするとこのような感じになります。
|
|
70
74
|
|
|
71
|
-
|
|
72
76
|
|
|
73
77
|
上の図はコネクトID.0,1,2のように全て繋げることができる例の一つです。
|
|
74
78
|
|
|
@@ -76,19 +80,35 @@
|
|
|
76
80
|
|
|
77
81
|
|
|
78
82
|
|
|
83
|
+
**※補足 不可な例です。**
|
|
84
|
+
|
|
85
|
+
|
|
86
|
+
|
|
87
|
+
これではコネクトID.2を満たしていません。５から６に繋がっていないです。
|
|
88
|
+
|
|
89
|
+
エッジ１-５が双方向につながるわけではないからです。
|
|
90
|
+
|
|
91
|
+
|
|
92
|
+
|
|
79
93
|
次にグループID.1をルーティングすると以下のように二つ考えられると思います。
|
|
80
94
|
|
|
81
|
-
|
|
82
96
|
|
|
83
|
-
|
|
84
98
|
|
|
85
99
|
ここでどちらのパターンを選ぶかは、同じ辺を使うのを避けるとすると、グループID.0で使用されている５と６を結んでいる辺を使っていない前者のパターンを採用するべきです。
|
|
86
100
|
|
|
87
101
|
|
|
88
102
|
|
|
103
|
+
**補足 以下もエッジ５-６が使われているのでそれより１番目の例の方が最適であると言えます。**
|
|
104
|
+
|
|
105
|
+
|
|
106
|
+
|
|
107
|
+
|
|
108
|
+
|
|
89
109
|
次にグループID.2は同じように以下のようになります。
|
|
90
110
|
|
|
91
|
-
|
|
92
112
|
|
|
93
113
|
この場合は５と６の辺以外を通ると他の辺の重複度が増してしまうので５と６をつないでいる辺の重複度は増してしまうがこれが最適である。
|
|
94
114
|
|
1
タグ追加
test
CHANGED
|
@@ -1 +1 @@
|
|
|
1
|
-
グラフ理論最適化問題 辺の重複度最小化
|
|
1
|
+
グラフ理論最適化問題 辺の重複度最小化 解法のアルゴリズムがわかりません。。
|
test
CHANGED
|
@@ -7,6 +7,10 @@
|
|
|
7
7
|
説明が長く、わかりにくい表現もあるかもしれませんが、質問などしてくださればお答えしたいと思っています。
|
|
8
8
|
|
|
9
9
|
よろしくお願いします。
|
|
10
|
+
|
|
11
|
+
|
|
12
|
+
|
|
13
|
+
ちなみに言語はc++です。
|
|
10
14
|
|
|
11
15
|
|
|
12
16
|
|
|
@@ -108,4 +112,8 @@
|
|
|
108
112
|
|
|
109
113
|
|
|
110
114
|
|
|
115
|
+
ネットで似たような解法が見当たらず質問に至りました。
|
|
116
|
+
|
|
117
|
+
|
|
118
|
+
|
|
111
119
|
例えば、先にルーティングしておくと比較的、後の経路が重複しなくなるようなグループの順番でルーティングする方法（どうすればいいか探す必要がありますが。。）や、数理計画法のようなアプローチができるかと考えましたが、他に良い方法がありませんでしょうか？
|