新しいヴィラのACMソリューション戦略

Question

私はこのACM問題The New Villa

を解決しようとしていると私は間違いなく、そのグラフの問題ではなくドアを、この問題にアプローチする方法を考え出すていないですし、他の部屋へのスイッチを持っている部屋は非常にありますジェネリックソリューションを作るのが混乱します。この問題のための戦略を定義する上で私の身体を助けることができますか？ また、ACM問題のディスカッションフォーラムが必要です。

おかげ A.S

Answer 1

それは状態の経路探索問題のように思えます。

各頂点をサイズn +識別子のバイナリベクトルで表すことができます。瞬時にどの部屋にいるかは[n]です。 V = {all binary vectors of size n and a recored for which room you are in}とE = {(u,v) | you can switch from binary vector u to v by clicking a button in the room you are in, or move to adjacent lights on room }

は今、あなたが唯一の可能なパスの検索アルゴリズムを実行する必要が

G=(V,E)。

可能な検索アルゴリズム：

1. BFS - 唯一つのターゲットノードがあるので、 双方向の検索はここで動作します、 - 、最も遅い実行時間しかし
2. bi - directional BFSプログラムへの最も簡単な が速く、BFS
3. A* - admissible heurstic functionを見つけ、問題をA *に通知してください。残りの部分をプログラムするのは難しいですが、良い発見を見つけたら、それはずっとうまくいくでしょう。

（*）上記のすべて共に完全【が存在する場合は解決策を見つけるであろう]と最適【が存在する場合、最短の解決策を見つける]

（*）このソリューションは部屋数の指数関数的な時間で実行されますが、問題が合理的な時間内に示されているように、d <= 10になるはずです。