Hatena Blog Tags
はてなブログ トップ
局所探索
このタグでブログを書く
言葉の解説
ネットで話題
関連ブログ

局所探索

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。
dd50ee70’s blog•4年前

膜アルゴリズム(その2)

今回は膜アルゴリズムを使い巡回セールスマン問題を解きます。 巡回セールスマン問題は、都市がいくつか(nとします)あり、それらを全てちょうど一回ずつ訪れて出発都市に戻る、距離が最短の経路を見つける問題です。詳しいことは例によってWikipediaにお任せしましょう。巡回セールスマン問題の解はn都市からなる系列です。出発都市は固定してよく、距離は幾何学的距離とすれば逆に回っても距離は同じなので、可能な解の候補は(n-1)!/2となります。!は階乗で、3!=6, 4!=24, 5!=120, 6!=720, とnが大きくなるとすごい勢いで大きくなります。だから可能な解を全部調べて・・・というやり方は…

#膜アルゴリズム#巡回セールスマン問題#遺伝的アルゴリズム#局所探索

関連ブログ

yunix_kyopro’s blog•7ヶ月前

AtCoderのジャッジ環境と同じEC2インスタンスを借りる件

はじめに こんにちは。競技プログラミングのコンテストに参加しているyunixです。 AHC033楽しかったですね。盤面が小さなゲームなのにこんなに難しいなんて最初に見た時には思いもよらなかったです。組み合わせの偉大さを身に沁みて感じました。 さて、今回のコンテストではビームサーチを使用しました。ビームサーチは一般的に速度の調整が焼きなましのような局所探索系の手法より難しく、TLEしないか心配でした。 一応今までの処理にかかった時間からビーム幅を変更するような処理は入れていたのですが、念のためにAtCoderのジャッジ環境と同じ環境をAWSに借りて実行して時間を計測してみました。 今回と同じよう…

tomboのブログ•8ヶ月前

初心者から初心者に向けた焼きなましのすすめ

どうも、tomboです。初めてブログを書きます。この記事では、焼きなまし初心者が、AtCoderのアルゴやヒューリスティックの問題に焼きなましを適用して解いてみた、ということを書きます。厳密なことはよく分からないので、焼きなましの知識が全くない初心者に、直感的に伝えるみたいなことが目標になっています。それではどうぞ（？） 焼きなましとは 焼きなましとは、ある状態Xに少しの変化を加えてX'（近傍）にして、評価値を計算し、評価値と温度からその近傍を採用するかしないかを決める、ということを繰り返して、大域最適解に近づいていくという感じのアルゴリズムです。これは、山登りと呼ばれるアルゴリズムの拡張です…

eijirouの競プロ参加記•10ヶ月前

AHC030 参加記

公式ビジュアライザ (Seed=19, Cost=100.837210) THIRD プログラミングコンテスト2023（AtCoder Heuristic Contest 030） お疲れ様でした。 システムテストの得点が 2,050,795,126,975 で 3 位でした。 最終順位表 問題概要 クエリを通して、石油がある場所を特定する問題です。 油田の個数と形は入力で与えられますが、各油田がどこにあるかは与えられません。 詳しくは公式の問題文を参考にしてください。 atcoder.jp 方針 毎ターン次のことを行いました。 焼きなまし法を用いて、油田配置の中で対数尤度が大きいものを 32…

wtr_hshjmのブログ•1年前

数理最適化ソルバー SCIP を用いてあなたの理想のミリオン10th Act-4 セットリストをつくってみよう

1. はじめに 2. 先に結果の一例だけ 3. 使用した一次データについて 4. コードおよび二次データの置き場所 5. 背景： Act-4楽しみ 6. 目的：『理想』のセットリストを考えてみたい 7. 手法：数理最適化 8. 定式化の準備 8-1. 各楽曲の「披露期待ポイント」の定義 8-2. 最適化対象の最終候補曲の絞り込み 9. （制約条件以外の）定式化 9-1. 定数 9-2. 変数 9-3. 目的関数 10. 制約条件の定式化、実験 10-1. 「制約01：ある日のある曲順では1曲のみが披露される」 10-2. 「制約02：すべての候補楽曲はAct-4を通じて1回以下だけ披露される」…