しかし、私の解決策を説明する前に、問題をより正確に定式化する必要があります。 クルーズの最初の段階では、すべての観光客はいくつかの遠足グループ（この場合は15グループ）に分けられましたが、各グループでは10人以下でした。 すべてのグループには順番に番号が付けられ、結果のグループのリストは、クルーズの最後まで変更されませんでした。 このリストは次のようになりました。
毎日、観光客はどのような遠足を行おうとしているかをクルーズディレクターに知らせます。 メインツアーに参加する予定のない人は全員、このリストから削除されます。 修正されたリストを使用して作業する必要があります。 クルーズディレクターは、遠足に行く人の数（通常100〜120人）を考慮し、バスの適切な注文を行います。 海岸の旅行代理店はこの注文を受け入れ、次の情報を報告します。「桟橋には、48、48、50席の3つのバスがあります。」 その結果、タスクは次のようになります。次の要件を順守し、観光客をバスに乗せることが重要です。
1.グループを分割しないでください。
2.バスをできるだけ均等に埋めます。
3.同じバスに座っているグループが連続して行くことをお勧めします。 つまり 最初のバス-グループ1〜5、2番目のバス6〜10など。
自動化に向けた最初のステップは、Excelとアドオン「ソリューションの検索」を使用して行われました（驚いたことに、この設定について知っている人はほとんどいませんが、非常に便利です）。
もちろん、最初の要件は満たされましたが、2番目と3番目の要件は忘れなければなりませんでした。 古いラップトップでソリューションの検索に約15秒かかったことを考えると、自転車を書くことにしました。 しかし、ここでも疑問が生じました。これをすべて行う方法：シンプレックス法、ダイナミックプログラミング、ブランチアンドバウンド法、ヒューリスティック？ 確かに、この問題を解決するのに役立つ何らかの種類の複雑なアルゴリズムがありますが、休暇中に難しいものを書いてから、小さな画面のラップトップでデバッグするのですか？ 何らかのヒューリスティックを試すことにしました。 少し考えてすぐに丘への上昇を延期しました。また、最小コストとバランスの取れた利益のヒューリスティックも考慮しました。
そして、ランダム検索のヒューリスティックを思い出しました。 正直に言うと、私はそれを使用したことがなく、ランダム検索が効果的な解決策につながらないことを確信していました。 しかし、好奇心がpre延していました。 その結果、次の座席アルゴリズムが得られました。
1.ランダムグループとランダムバスを選択する
2.選択したグループを選択したバスに配置できるかどうかを確認します（このグループが別のバスに座っているかどうか、および十分な座席があるかどうかを確認します）
2.1。 できない場合は、失敗した試行のカウンターを1つ増やします
2.2。 可能であれば、失敗した試行のカウンターをリセットします
3.失敗した試行の数が50を超えた場合、ループを終了します。それ以外の場合は、ステップ1に進みます
4.すべてのグループが座っているかどうかを確認します
4.1。 それだけの場合は、バスの空席数の最大差を計算します（これは推定と見なされる数です）
4.2。 すべてではない場合、座席の配置に失敗したことを報告します。
この手順を何百回も実行すると、最も評価の高い座席計画を選択できます。 このアルゴリズムは驚くほどうまく機能しました。 少なくとも要件の最初と2番目の段落は完全に満たされました。
3番目のポイントを満たすために、アルゴリズムを少し変更する必要があります。 座席アルゴリズムを開始する前でも、各バスに5つのグループ（1〜5、6〜10、11〜15）を配置し、座席を実行します。 彼女が成功した場合、最高のスコアを記憶し、結果が表示されます。 次に、各バスに4つのグループ（1〜4、5〜8、...）を配置して、再び座席を配置します。 得られた推定値が前の段階よりも良いことが判明した場合、それを覚えて、結果を再度表示します。 次に、最初に3つのグループ、2、1でバスに乗ろうとします。最後に、事前の情報なしで座席の手続きを行います。 何らかの段階で評価が改善された場合、結果のソリューションが表示されます。
もちろん、アクションはより多く実行されますが、得られる結果の価値ははるかに高くなります。 最後に、プログラムの小さな例を示します。
ほとんどの人がすでにランダム検索ヒューリスティックについて知っていることは明らかですが、突然、この投稿はそれについて知らないか、何らかの理由でそれを使用することを恐れた人々によって読まれました。 このヒューリスティックをもう少しよく学んだところで、少なくともいくつかの問題の解決策を単純化できることを願っています。