バックトラックアルゴリズム

アルゴリズムとデータ構造 補足資料 10-3

「ナップザック問題」

横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

バックトラックアルゴリズム

• とりあえずやってみる

• ダメなら戻って別の道を探る

– あのとき別の道を選んでいたら、、、

• 試行錯誤（ trial and error ）

– 結局全部のケースをやってみる（完全解）

– その中で最適な解を選ぶ

（最適解を覚えておく）

ナップザック問題（ Knapsack problem ）

A) n 個の品物を旅行カバンの中に入れて旅行す る．持って歩ける重量には制限がある

B) 個々の品物には，重さ と 価値（重要度） の 情報が与えられている．

C) n 個の品物からいくつか選択して，制限重量

以下で価値の総和が最大になるようにする．

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

100

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

重量制限が

のとき 現在の最大総価値

点

ナップザック問題（ Knapsack problem ）

本

点

傘

90

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

100

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

500g

； あと一つ載せたら

重量制限が

のとき 現在の最大総価値

点

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

100

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

500g

； あと一つ載せたら

重量制限が

のとき 現在の最大総価値

点

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

100

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

重量制限が

のとき 現在の最大総価値

点

1,300g

；

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

320g

；

重量制限が

のとき 現在の最大総価値

点

1,300g

；

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

320g

；

重量制限が

のとき 現在の最大総価値

点

1,300g

；

720g

；

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

320g

；

重量制限が

のとき 現在の最大総価値

点

1,300g

；

720g

；

；

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

320g

；

重量制限が

のとき 現在の最大総価値

点

1,300g

；

720g

；

；

330g

；

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

点

地図

点

宿チケット

100

点

10g ^航空券

100

点

洗面用具

50

点

320g

；

重量制限が

のとき 現在の最大総価値

点

1,300g

；

720g

；

；

330g

；

340g

；

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

点

地図

点

宿チケット

100

点

10g ^航空券

100

点

10g ^洗面用具

50

点

；

重量制限が

のとき 現在の最大総価値

点

1,300g

；

720g

；

；

330g

；

340g

；

640g

；

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

点

地図

点

宿チケット

100

点

10g ^航空券

100

点

10g ^洗面用具

50

点

；

重量制限が

のとき 現在の最大総価値

点

1,300g

；

720g

；

；

330g

；

340g

；

640g

；

解候補 現在の最大総価値

点

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

100

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

重量制限が

のとき 現在の最大総価値

点

1,300g

；

ナップザック問題（ Knapsack problem ）

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

100

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

1 1 1 1 1 1 1 1 1 1

～

本

点

傘

点

下着

点

ジャケット

30

点

MDプレー ヤ

20

点

薬

100

点

地図

点

宿チケット

100

点

航空券

100

点

洗面用具

50

点

0 0 0 0 0 0 0 0 0 0

最悪時： 上記の全とおりの組み合わせについて、総重量と総価値を計算して、

一番良いものを選ぶ。

O(2

)

バックトラックアルゴリズム

• とりあえずやってみる

• ダメなら戻って別の道を探る

– あのとき別の道を選んでいたら、、、

• 試行錯誤（ trial and error ）

– 結局全部のケースをやってみる（完全解）

– その中で最適な解を選ぶ

（最適解を覚えておく）