動的な防御コストを持つ消防士問題

科学分野:

• グラフ理論;計算複雑性理論;ゲーム理論

背景:

• 古典的な消防士問題は、グラフ上の伝染の広がりをモデル化し、頂点を保護することを目指しています。 計算上困難ですが、制限されたグラフクラスでは解決可能です。

研究 の 目的:

• 時間依存および状態依存の頂点防御コストを持つバリアントであるコスト関数消防士問題を導入および分析します。 さまざまなグラフクラスにおける計算複雑性と扱いやすさを調査します。

主な方法:

• コスト関数消防士問題を定義し、その複雑さを分析します。 単項二階述語論理を使用して固定パラメータ扱い可能性を証明します。 さまざまなヒューリスティック戦略を比較する経験的調査を実施します。

主要な成果:

• コスト関数問題は、古典的な問題が扱いやすい木であっても、計算上困難です。 完全グラフ、パス長が制限されたグラフ、および特定の木では扱いやすいです。 ツリー幅、予算、および最大時間ステップに関する固定パラメータ扱い可能性を証明しました。 経験的結果は、ヒューリスティックの有効性がグラフ構造によって異なり、状態ベースの戦略が次数ベースの戦略よりも優れていることを示しています。

結論:

• コスト関数消防士問題は、新たな計算上の課題をもたらしますが、特定のパラメータとグラフ構造にとっては管理可能です。 ヒューリスティックの選択は重要であり、伝染モデリングに関わる特定のグラフとコスト関数に依存します。