| 決定問題 |
|
|
|
|
|
|
|
|
|
|
|
| • | 決定問題：YES/NOで答える問題 |
|||||||||
| • | （最適化問題） |
|||||||||
| 最適加工順序を求めよ |
||||||||||
| • | （決定問題） |
|||||||||
| 22時間以内に終了する加工順序はある？ |
||||||||||
| • | 最適化問題←（変換可能）→決定問題 |
|||||||||
|
|
|
|
|
| それ以上減らすと答 |
||||
| えがNOになるぎりぎ |
||||
| りのkを見つける |
||||
|
|
|
| 決定問題を何回か解け |
||
| ば最適解を得る |
||
| k=適当な数 |
| ｋを増やす |
| kを減らす |
| k時間以内？ |
| YES |
| NO |