アカウント名:
パスワード:
NP-hard と呼ばれるのは、TSPで予算内に収まるかどうかだけでも既に NPC なので、最安値はいくらかとか、最安経路を求めるなど様々な実用的なバリエーションに予算内判定を帰着できるからでしょう。
で、二分探索を簡単に考えていますが、「解ける」をどう捉えるかが問題です。 非決定性の計算は受理計算が存在するかだけなので、単なる非決定性のチューリング機械では多項式時間で最安値を求めることも、与えられた値が最安値かどうかを判定することもできないと思います。 予算内判定を多項式時間で yes, no を判別できれば最安値判定問題が解けます(Δp 2-completeだったはず)。 あと、最安経路は複数存在しますので、予算内判定問題が簡単でも最安経路を求めるのはそれほど自明ではありません(関数のクラスとしてはΔp 2MVかな?)。
居座りセールスマン問題はどうやって解決すればいいのでしょうか #居直りセールスマン問題とか泣き落としセールスマン問題も
居座りセールスマン問題はどうやって解決すればいいのでしょうか
#居直りセールスマン問題とか泣き落としセールスマン問題も
計算量がうまく見積もれないのですが、「ケーサツ呼びますよ」「ケーサツ呼びましたから」「あー、もしもし、ケーサツですか」といったケーサツアルゴリズムは割と効果的に問題を解決するようです。
>居直りセールスマン問題とか
もしかして、開き直りのつもり?
元AC氏ではありませんが、「居直る」という言葉には「無作法や罪を咎められて態度を荒らげる」、今風に言うと「逆切れ」の意味があります。
ちょうど昨日、我が家に来た野菜訪問販売のおばちゃんが、近隣家庭の情報を我が母上から聞きだそうとし、断ったらなぜか怒り出した(「一軒一軒訪問しなきゃならんのか」とか。当たり前でしょうが)というエピソードがあったそうです。そうした迷惑な「居直りセールスマン問題」を解決するスマートなアルゴリズムがあったら、実用度が高いのではないでしょうか。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
日々是ハック也 -- あるハードコアバイナリアン
TSP は NP 完全問題? (スコア:0)
Re: (スコア:0)
Re:TSP は NP 完全問題? (スコア:2, 参考になる)
NP完全問題が「あらゆるクラスNPの問題より難しく(すなわち、その問題を速く解くアルゴリズムを応用すれば全てのクラスNPの問題がさくさく解ける)」「YesかNoか?を求める問題」と定義できるから。
基本的に完全問題バージョンと困難問題バージョンがある問題の場合は、どっちかを速く解けるアルゴリズムが見つかれば逆もまたしかりなので、厳密な議論をしている場合を除くと意識してない事が多く、慌ててしゃべってるときなんかはちょいちょい言い間違えるorz
ちなみに、逆もまたしかりなのは、「最も安い経路」が求まるなら、「予算内の経路」があるかどうかは自明。 その逆は、コストの最大値を求めて二分探索でもすればよい(線形探索でもかまわない)。まず、全部の道の費用を単純に全部足して架空の「最大コスト」を求める。TSPだと同じ道を2回以上通る経路は解にはならないので、ここで求めた「最大コスト」より費用のかかる解は存在しない(極端な場合を除くと「最大コスト」になる経路も存在しないけど)。そこで、この「最大コストの半分のコストの道はあるかないか?」を判定する。あれば「さらにその半分」・・・とやっていく。酷い話だけど、ここまでやっても、判定に使うのが「TSP判定問題を多項式時間で解くアルゴリズム」なら、最安値を求める問題も「多項式時間で解ける」ことになる。
Re: (スコア:0)
NP-hard と呼ばれるのは、TSPで予算内に収まるかどうかだけでも既に NPC なので、最安値はいくらかとか、最安経路を求めるなど様々な実用的なバリエーションに予算内判定を帰着できるからでしょう。
で、二分探索を簡単に考えていますが、「解ける」をどう捉えるかが問題です。 非決定性の計算は受理計算が存在するかだけなので、単なる非決定性のチューリング機械では多項式時間で最安値を求めることも、与えられた値が最安値かどうかを判定することもできないと思います。 予算内判定を多項式時間で yes, no を判別できれば最安値判定問題が解けます(Δp 2-completeだったはず)。 あと、最安経路は複数存在しますので、予算内判定問題が簡単でも最安経路を求めるのはそれほど自明ではありません(関数のクラスとしてはΔp 2MVかな?)。
Re:TSP は NP 完全問題? (スコア:1)
Re:TSP は NP 完全問題? (スコア:1, おもしろおかしい)
計算量がうまく見積もれないのですが、「ケーサツ呼びますよ」「ケーサツ呼びましたから」「あー、もしもし、ケーサツですか」といったケーサツアルゴリズムは割と効果的に問題を解決するようです。
Re: (スコア:0)
>居直りセールスマン問題とか
もしかして、開き直りのつもり?
Re: (スコア:0)
元AC氏ではありませんが、「居直る」という言葉には「無作法や罪を咎められて態度を荒らげる」、今風に言うと「逆切れ」の意味があります。
ちょうど昨日、我が家に来た野菜訪問販売のおばちゃんが、近隣家庭の情報を我が母上から聞きだそうとし、断ったらなぜか怒り出した(「一軒一軒訪問しなきゃならんのか」とか。当たり前でしょうが)というエピソードがあったそうです。
そうした迷惑な「居直りセールスマン問題」を解決するスマートなアルゴリズムがあったら、実用度が高いのではないでしょうか。