0

次のアプローチを使用して CSP の問題を解決しました。

  1. AC3 を実行して可変ドメインを減らす
  2. 単純なバックトラックを使用して解決策を見つけます。

それは私のすべてのテストケースで非常にうまく機能し、高速ですが、私の友人は私にこう尋ねました: バックトラッキングのすべてのステップで AC-3 を実行することを暗示しています。

そのような場合はあまり役に立たない気がしますが、どこかでAC-3が両方の方法で使用できることを見たことがありますが、それ以上の説明はありません. これについてさらに情報を得ることができますか?

PS: 実際、AC-3 は約 2 秒間実行されるため、毎回実行するのは私の場合は耐えられません。しかし、私は好奇心からこの質問をしています。他の問題を解決するときに役立ちます。

4

1 に答える 1

1

この質問は約 1 か月間死んでいるので、自分で答えようと思います。バックトラッキングのすべてのステップで AC-3 を実行すると、本当にメリットがあります。最初の AC-3 ではあまり改善されなかったが、いくつかの変数を修正した次の AC-3 でははるかに成功したというような問題に遭遇しました。

于 2013-04-13T08:22:10.210 に答える