数学@ふたば保管庫 [戻る]

90021 B


巡回セールスマンの変形で
「とある拠点に着いたらa%の判定で商談成立して、その時点で仕事は終了。
そこまでの時間を競う」って問題を作りたいんだけど
もう既存でそういうのありますか?

1111027 B
ぶっちゃけ、スレ表題だけでは数学命題とするにはあまりにも漠然過ぎるのですが、
「a%の判定」に厳格な達成基準なりアルゴリズムなりが与えられるのであれば、例えばΟ(2^n)やΟ(n!)といった具合に時間(ここでは何分何秒という時刻ではなく「計算時間(時間計算量)」)での評価を示すことができるかもなのですよ。vid. アルゴリズムデータベースhttp://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/

>そこまでの時間を競う
運が悪いと永遠に彷徨うの?

グラフの各頂点ごとにa%という終了判定のパラメータがひっついてるの?
それで、各頂点の終了判定の%は異なっていてもいいのか、それとも全頂点で同じa%?

頂点間の移動に重み付け(かかる時間やコストの差)などの条件は?

>「とある拠点に着いたらa%の判定で商談成立して、その時点で仕事は終了。そこまでの時間を競う」
そのとある拠点まで最短で移動して、商談が成立するまで近くの拠点との間をいったり来たりする
が、正解かな?

無限に成立しない場合があるね