アカウント名:
パスワード:
巡回セールスマン問題は、配達員では重要そうですが私の場合、巡回セールスマン問題は仕事であまり使うことはないのですがジョブショップスケジュール問題はよく必要に迫られます。
ジョブショップスケジューリング問題を古典コンピュータで解かせるアルゴリズムについて知っている方がいらしたら教えて下さい。
巡回セールスマン問題もジョブショップスケジューリング問題も NP 完全なので、評価関数を用意して総当たりor焼き鈍しor遺伝的アルゴリズムしかないんじゃないかな評価関数を組めれば、実現自体は出来ると思いますなお「特定の問題に関して量子コンピュータが圧倒的に高速」なだけで、古典コンピュータで解けない問題を量子コンピュータが解けるようになるわけではないです
巡回セールスマン問題はNP困難だけどNP完全ではない(NP完全問題より難しいかもしれない)のでは? (そもそも「はい」「いいえ」で答えられる問題でなければNP問題という概念が適用できないが巡回セールスマン問題は「最短経路を求めよ」という問題)
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
Stay hungry, Stay foolish. -- Steven Paul Jobs
ジョブショップスケジューリング問題 (スコア:1)
巡回セールスマン問題は、配達員では重要そうですが
私の場合、巡回セールスマン問題は仕事であまり使うことはないのですが
ジョブショップスケジュール問題はよく必要に迫られます。
ジョブショップスケジューリング問題を古典コンピュータで解かせるアルゴリズムについて
知っている方がいらしたら教えて下さい。
Re: (スコア:1)
巡回セールスマン問題もジョブショップスケジューリング問題も NP 完全なので、評価関数を用意して総当たりor焼き鈍しor遺伝的アルゴリズムしかないんじゃないかな
評価関数を組めれば、実現自体は出来ると思います
なお「特定の問題に関して量子コンピュータが圧倒的に高速」なだけで、古典コンピュータで解けない問題を量子コンピュータが解けるようになるわけではないです
Re:ジョブショップスケジューリング問題 (スコア:0)
巡回セールスマン問題はNP困難だけどNP完全ではない(NP完全問題より難しいかもしれない)のでは? (そもそも「はい」「いいえ」で答えられる問題でなければNP問題という概念が適用できないが巡回セールスマン問題は「最短経路を求めよ」という問題)