# 2020最適化技術実験 第3部 質問回答ページ
## 質問&回答について
「質問番号n」の形で見出しをつけます．
基本的には新しい回答ほど上位に表示されます．
回答状況ページで回答状況を確認後，
Ctrl+F，Cmd+Fで自分の質問番号をページ内検索してください．
ただし，回答状況の「回答者」列は「回答書き込み完了」ではなく「今から回答を行います」の印です．
質問量に依っては「重複した質問」欄の更新が止まる場合があります．
そのため，重複した質問は回答の場所を検索出来ないことがあります．
また，質問する前に必ずこのページを見て，類似の質問がないことを確認してからGoogleフォームで質問を投稿してください．
質問と回答の例は以下の通りです．
質問番号0
> hogeがhogehogeの場合，hogehogehogeはhogeですか？
```[python]
import numpy as np
if __name__ == "__main__":
print('hoge hoge hoge')
```
XXXがYYYなのでZZZをAAAするとBBBがCCCです．
重複した質問：質問番号i, 質問番号j,質問番号k
----------
質問番号35
> 課題4の動作確認のプログラムでは、初期解や近傍に関係なく，近傍の中の1つ目の解の順列とメイクスパンとガントチャートが出力されるという認識で良いのでしょうか．
いいえ．無作為にシャッフルされた初期解seqから、暫定解よりも良い解が見つかり次第すぐ移動するという戦略で見つかる局所最適解を出力するコードになっています．つまり，近傍に暫定解よりも良い解が存在しなくなるまで探索しています．
余力があるようであれば，暫定解を逐次print()などで出力してみると理解が深まるかと思います．
----------
質問番号33
> タブー探索法について調べたところ、S→S'という表記がありますがこの矢印はどのような意味で用いられていますか。
「解S（今回だと順列S）から解S'への遷移」かなぁ．．と思います（が，文脈がわからないのでなんとも言えないです．．）
また，一般的には矢印は写像を表すと思います．
（追記）ちなみに見たページはWikipediaですか？
Wikipediaなら，「解S（今回だと順列S）から解S'への遷移」だと思います．
[1,2,3,4]から[1,2,4,3]への遷移が既にタブーリストにあるなら（既にこの遷移をしたことがあるなら），
という意味で使われています．
（追記の追記）また，タブーサーチでは「SからS'への遷移」をタブーリストに入れるのではなく，「解S'」をタブーリストに入れる方が一般的なのではないかなと思います．
つまり，SからS'への遷移だけでなく，タブーリストにS'が既に入っているなら他の解S''やS'''からもS'には遷移不可能とするのが一般的だと思います．
----------
質問番号29
> 出力結果は課題3,4ともに同じbest_msの値を取りますか？
局所探索では，得られる（局所）解は，初期解や近傍によって異なることがあります．ですので，必ずしも同じスケジュール（やメイクスパン）が得られるとは限りません．
----------
質問番号28
> copyモジュールを使用したのですが、モジュールは自由に使用して良いのでしょうか。
copyモジュールをinportして使用してもよいと思いますが、seqがリストとして定義されているので、デフォルトでリスト型変数に対して用意されているcopy()メソッドでも対応できるかと思います。
標準ライブラリに関するPythonのリファレンスを貼っておきますのでご参照ください。
https://docs.python.org/ja/3/library/stdtypes.html#mutable-sequence-types
類似の質問：質問番号34
----------
質問番号26
> 課題3の出力が正しいか確認したいのですが、なにが出力されればよいでしょうか？？ちなみに、交換近傍を使用して、下のようにコードを作成し、出量結果乱のように表示されました。
最終的に出力されるものは，局所探索の結果出てきた解（1つの順列）と，その解の目的関数値（その順列通りに処理した時のメイクスパン），ガントチャートです．
探索の過程で，交換近傍/挿入近傍で作られうる全ての順列の中での最良解に移動出来ているかは，```local_search_a()```メソッドの中で適宜```print()```して
「何を見つけたか」と「見つけた中で最良のものを選んでいるか」を確認するのが良いかと思います．``
----------
質問番号21
> 課題4なのですが、「集合SからLB最小のノードを1つ取り出し、それをノードSとする」、という擬似コードの3行目の部分が、良い方法が思いつかず、下にコピペしたようにやってみたのですがうまくいきません。どうすればうまくいくかアドバイスいただきたいです。
```[python]
def search_bab(self):
UB=sys.maxsize
while self.nodes:
node=self.nodes.remove(min([self.nodes[i] for i in len(range(self.nodes))],key=self.nodes[i].makespan))
if node.is_complete():
if node.makespan<UB:
best_seq=node.seq
UB=node.makespan
for node in reversed(self.nodes):
if node.makespan>=UB:
self.nodes.remove(node)
else:
for j in node.rest:
child=Node(node.jobs,node.seq)
child.assign(j)
if child.makespan<UB:
self.nodes.append(child)
```
remove() をお使いになる意図をお聞きしていないのですが、enumerate_all() 同様に、pop() を使う方が良いかと思います。
しかし、最初の要素を pop するのであれば、ノードが LB の昇順になっている必要があるので、pop する前に、ソートしておきましょう。
----------
質問番号なし
> Googleフォーム以外でもらった質問です．self.nodesから.remove()で要素を削除する際に，普通にfor文を使うとうまく行かないことについて．
下のように，self.nodesのリストの要素をfor文で前から順に見ていって，それをremove()で削除しようとすると，うまくいきません．
```[python]
for node in self.nodes:
self.nodes.remove(node)
```
要素を削除することでself.nodes自体が変化してしまうからです．例えば，0番目の要素を削除すると，次のループで1番目の要素を見たときに，それが元のリストの2番目の要素になってしまう（0番目がなくなって，1番目が0番目に繰り上がっているので）といったことが起こってしまうわけです．
この問題の解決策の1つとして，
```[python]
for node in reversed(self.nodes):
self.nodes.remove(node)
```
とする手があります．reversed()はリストから要素を逆順に取り出すイテレータを返す関数です．
----------
質問番号19
> 課題４は何を基準に枝刈が完成したとみなされるのでしょうか。
自分でカウントする変数を置いて、何回while文が回ったかを判断すればよいのでしょうか。もし、この方法で判断するのならば、カウントの値はどのくらいになるのが理想でしょうか。
ご指摘の方法を適用した場合、
search_all() の場合ですと、326、search_bab() （下界は、node.makespan）にすると、
125 となりました。下界の精度を上げることを目指して、下界を変更した場合は、結果が変わる
かもしれません。
----------
質問番号18
> 質問番号16の回答を見て、課題2をおそらく解くことができました。しかし、表示順が逆になってしまいました。これは何かしらの方法で直した方が良いのでしょうか？それともこのままでも良いのでしょうか？
これも，少しコードは違いますが，質問番号17とほぼ同じ原因です．こちらは普通に子ノードを後ろに追加していって，取り出すときも末尾から取り出しています．子ノードを格納した時点でリストは，
[0,1,2,3,4]
となっていて，取り出すときに後ろから取り出しているので，最初に4が出てくるわけです．もうひと工夫すれば0から取り出せるようにできますよ．
----------
質問番号17
> 課題2についてなのですが、作成した下にコピペしてあるプログラムを実行したら、０，１，２，３，４の順に深さ優先探索が行われると思ったら、４，３，２，１，０の順で実行されました。どうしてそうなったのかわからないので教えていただきたいです。
実はこれは期待していた質問です．0, 1, 2, 3, 4の順で子ノードを作成して前からリストに入れていますよね．そうするとリストは
[] -> [0] -> [1,0] -> --- -> [4,3,2,1,0]
となります．これが原因ですね．なので，関数の再帰呼び出して順列を列挙していたときと全く同じ順にノードを走査していくようにするためには，もう少しだけ工夫が必要です．
----------
質問番号16
> 課題2で苦戦しています。どのようなイメージ（構造）で作成するのか、ヒントをいただけますと嬉しいです。
ほんの微修正で実装できます．答えは１つではありませんが，例えば，未分枝ノードの集合self.nodesから要素を取り出す順序を変える（今は前から順に取り出していると思います）など．．．
----------
質問番号15
> 課題１で作成したenumerate_allが前回作成した再帰を使ったenumerate_allと同じ順序で出力されているように見えます。よって課題２で何をすれば良いのかわかりません。
どちらも，最終的な順列が出力される（葉ノードがチェックされる）順序は同じです．違いは，途中のノードがどのような順でチェックされていくかにあります．
```[python]
def enumerate_all(self):
while self.nodes:
node = self.nodes.pop(0)
# print(node.seq)
pass
```
うえのサンプルコードの4行目のコメントを外して走らせてみてください．葉ノード以外の中間ノードもチェックされたタイミングで出力されるようになります．それで順序が幅優先になっていることが確認できると思います．
----------
質問番号14
> 前回の演習の提出なんですが、ipynb形式で保存がうまくできなくて、とりあえずpyのままで提出してしまったのですが、ipynb形式の保存方法を教えて欲しいです
Google Colaboratoryであれば、「ファイル」->「.ipynbをダウンロード」でipynb形式で保存することができます。
----------
質問番号13
> 今回使用する集合Sとはノードから生成される配列seqを格納したものという認識で大丈夫ですか。
集合Sはノード（Nodeクラスのオブジェクト）の集合です．\_\_init\_\_()をみてみると，最初は，根ノードのみを含む形で初期化されていることがわかります．
----------
質問番号12
> 課題2で出力結果のエラーが出るのですが、どこを修正すればいいのかわかりません。新しい子ノードn'(自分のプログラムだとn2)を作る際に、Nodeの引数にはnode.jobsとnode.seqを更新したものを与えるという考えは正しいですか？
その考え方はOKです．エラーは，
```[python]
seq = node.seq.append(j)
```
のところだと思います．
.append(j)は戻り値がありませんので，これではseqに所期のリストは代入されません．やりたいことは多分
```[python]
node.seq.append(j)
seq = node.seq
```
ということなのかな？という気がします．
----------
質問番号11
>課題1が正しくできているのか確認する方法はありますか？
2020/12/01 18:00 にお答えするのが適切かわかりませんが、
以下のコードの出力結果が True になるはずではないかと思います。
追記：質問番号5 が同様の質問でした。次回以降、質問前にご確認お願い致します。
```
pt = [
[35, 7, 18, 20],
[4, 60, 12, 10],
[15, 15, 20, 30],
[11, 25, 10, 35],
[33, 1, 45, 12]
]
jobs = Jobs(pt)
seq = [2, 3, 4]
rest = [1, 0]
best_seq = [2, 3, 4, 1, 0]
node1 = Node(jobs, best_seq)
node2 = Node(jobs, seq)
node2.assign(rest[0])
node2.assign(rest[1])
node3 = Node(jobs, seq)
node3.set_seq(rest)
print('課題1-1:' + str(node1.makespan == 173))
print('課題1-2:' + str(node2.makespan == 173))
print('課題1-3:' + str(node3.makespan == 173))
print('課題1-4:' + str(node1.is_complete()))
```
質問番号10
> 課題3において、「enumerate_all()関数を拡張する」という意味を理解しておらず、以下のようにプログラムを書いてしまいました。実行結果としては正しいものが出力されているのですが、質問番号9の回答を見て、課題の意図と異なる作り方をしていると気づきました。その場合、条件を満たしていないこととなり、評価は低くなってしまいますか？
苦戦しつつもちゃんと解が得られるようになんとか工夫をこらしてコーディングしたのがわかります．動くコードを期限内に提出しているのでxにはなりません．安心してください．ただし，この作り方では最高評価を得るのは難しいかもしれませんので，もし質問9の回答を参考に修正している場合はそちらを再提出してもらってもOKです．
----------
質問番号９
> best_msとbest_seqを更新しつつ再帰を行なっていくプログラム構成のイメージが湧かず詰まっています。
ざっくりしたイメージでもいいのでどのような感じで更新していくのか教えていただきたいです。
enumerate_all() の拡張であるという点に注意しましょう。
新たなメイクスパンが計算できるのは、新しい完全な順列が見つかった時です。
そのときに、best_seq, best_ms が更新されるか検討し、
新しい完全な順列が、best_seq, そのメイクスパンが、best_ms となるときは、
best_seq, best_ms を更新します
（Node クラスのコンストラクタに注目してください）。
しかし、そのためには、暫定的な best_seq, best_ms を保持しておく必要があります。
best_seq, best_ms は、recursive_search() の引数ですが、戻り値でもあります。
ゆえに、recursive_search() を呼び出すたびに戻される best_seq, best_ms の値を
変数（best_seq, best_ms）に代入しておく必要があります。
（宋先生が担当された９回目の課題の解答にも
p, c, cc = d.get()
のような記述がありました。参考にしてください。）
これにより、再帰的に recursive_search() を呼び出す回数だけ、
best_seq, best_ms が更新されうることに対応でき、
最終的に戻される best_seq, best_ms が最適になります。
質問番号８
> 講義資料にある、順列を再帰呼出しで列挙する関数の擬似コードにて、「ジョブ j をノード n の割付済みジョブの順序 seq の末尾に追加して新しい子ノード n’を生成する」とありますが、これは引数nに対してジョブjのassignを行うこととは異なるのでしょうか？
また、講義資料の最後行enumerate_all (ノード n’ )以下に、n.seqやn.restに対して要素の削除や追加を行う必要はないのでしょうか？
引数nに対してジョブjのassignを行うこととは異なると思います。
講義資料、「探索木とその構成（J=4の場合）」記載の図におけるノード 「0, 1, ...」をノード n としてみると、
ノード n 、seq = (0, 1), rest = (2, 3) において、次に割り付けるジョブ j を j = 2 とするとしたとき、seq = (0, 1, 2), rest = (3) となるわけですが、
これはノード n の 子ノード（のひとつである）ノード 「0, 1, 2, ...」（これをノード n’ とする）を意味しています。
このノード n’ に対して、enumerate_all (ノード n’ ) が適応されれば、
ノード n’ 、seq = (0, 1, 2), rest = (3) において、次に割り付けるジョブ j が、j = 3 となり、
seq = (0, 1, 2, 3), rest = () となるわけですが、
これはノード n’ の 子ノード「0, 1, 2, 3」を意味しています。
この子ノードは葉ノードであるため、新しい完全な順列 seq = (0, 1, 2, 3) が見つかったということになります。
forジョブj inノードnで未割付のジョブの集合: の次のループでは、
ノード n 、seq = (0, 1), rest = (2, 3) において、
次に割り付けるジョブ j を j = 3 とする場合となり、
新しい完全な順列 seq = (0, 1, 3, 2) が見つかることになります。
このような再帰的な考えから、n.seqやn.restに対して要素の削除や追加を行う必要性の有無を考慮してください。
質問番号７
> 課題１の確認を他の質問の回答として載せられていたもので行ってみたのですが、node.assign([1,2,3])の方で、self.rest.remove(self.jobs.M)に対して、下の出力結果に書いたようなエラーが出ました。何が問題なのでしょうか？？
この部分は，node.assign()じゃなくてnode.set_seq()でした．下の回答中のコードも修正しました．
質問番号6
> 課題１−３の戻り値はjobクラスのオブジェクトですか？中の操作としてはseqの順序でjobオブジェクトのリストを構成するということですか？
set_seq()の戻り値はありません．
メソッド内では，seqの順序でリストを作成し，
課題1-1，1-2で作ったメソッドを用いるなどして
その他必要な操作（未割り当てジョブリストrestの更新，完了時刻last_ctの設定など）を行ってください．
質問番号5
> 課題1が正しくできているのか確認する方法はありますか？
例えば，上の方にある下のコードをまずコピーして実行してください．
```
pt = [
[35, 7, 18, 20],
[4, 60, 12, 10],
[15, 15, 20, 30],
[11, 25, 10, 35],
[33, 1, 45, 12]
]
jobs = Jobs(pt)
```
その後，
```
node = Node(jobs)
```
でNodeクラスのインスタンスを作って，
```
node.assign(0)
print(node.makespan)
node.set_seq([1,2,3])
print(node.is_complete())
```
のようにメソッドを実行した結果を確認してみるといいと思います．
質問番号4
> enumerate_all(Node(jobs))を実行するとき、「jobs」を「0」などに置き換えれば良いのでしょうか？
変数jobsを宣言及び初期化する必要があるので、ノートブック内のこちらのセルを実行後に、そのまま実行してみてください。
```
jobs = Jobs() # create an empty instance
jobs.set_randomly(5, 4) # arguments are (the number of jobs: J, the number of machines: M)
print(jobs.pt)
```
質問番号3
> 1-1なのですが、last_ct[3]を返せば、割り付けられているジョブのメイクスパンを返せると考えているのですが、ノートブックの中の「各self.last_ct[m]には，機械mが，self.seqに含まれる割付済みジョブをすべて処理し終える時刻を格納します．」というのは、last_ct[]の値はseqが入力されたら自動で更新されていくということなのか、格納するための変数を準備したから、makespan()内でlast_ct[]の各値を足していくコードも作らないと動かないということなのかどうなのでしょうか？
課題1-1の段階では，last_cmにはすでに正しい値が入っていると考えてコーディングしてもらえればOKです．この値の更新は課題1-2で行います．
もう一つ追加でアドバイスですが，last_ct[3]を使ってしまうと，機械数M=4でないとうまく動かないコードになってしまいます．Mの値が変化してもうまく動くように工夫してみましょう．
Sign in with Wallet
Connect another wallet