みんな。私は大学のタイムテーブル スケジューラ プロジェクトに取り組んでいます。主にタブー検索をしていますが、お聞きしたいのですが、
一般的な検索では、現在の状態のすべての近傍を探索し、フィットネスまたは評価関数に従って最適な状態を取ることができますが、そのようなプロジェクトでは、すべての近傍を生成するとパフォーマンスが低下します。私はそのような問題をバイパスしますか？たとえば、1 つの州に対してのみ子を生成し、検索プロセス中に他のすべての州に対してこの生成の恩恵を受けることはできますか?
私はそのような問題に一生懸命取り組んできたので、そのようなアルゴリズムの専門家がいる場合は教えてください。
shoosh のコメントへの補遺:剪定をお探しですか? これを含め、そのような戦略は数多く存在します。1 つのサイズですべてに対応できるわけではないことを忘れないでください。そのため、おそらくニーズに合わせてヒューリスティックを設計する必要があります。
以前のコメントへの補足：パフォーマンスとメモリの制約に応じて、プルーニングは複数のレベルで実行することもできます。例えば：
初期状態を優先キューに入れます。
終了するまで（たとえば、キューが空である、適切なソリューションが見つかった、期限が切れた、...）、次の手順を繰り返します。
2.1。キューから一番上のエントリを取得します。
2.2。その子を生成します（可能であれば、推定量を使用して最初に最も価値の高い子を取得します）。
2.3。各子が生成されたら、それを優先キューに入れます。キューがサイズ制限に達すると（おそらく試行錯誤によって経験的に決定されます）、キューへの各挿入には、キュー内の最も低い値の要素の削除が伴う必要があります。
明らかに、これを機能させるには、優れた推定/評価関数を持つことが重要です。キュー評価関数を調整して、「生成」を考慮に入れ（たとえば、初期状態に近い、より浅い深度の状態に加重ボーナスを与える）、深度優先と幅優先の間のバイアスを調整できます。
私は専門家ではありませんが、通常、そのような計算の最適化について考えるのは難しくありません。
使用するフィットネス機能に大きく依存します。通常、ノードの適合度がわかれば、子供の適合度の範囲、または最悪から最高の範囲までを推測できます。
単純な関数を使用すると、明示的に生成しなくても実際に子のフィットネスを計算し、価値がある場合にのみ生成することができます。