提供一個電腦能理解的思路吧。
抓貓的時候,和這個貓之前的生活毫無關系,只和這只貓現在有可能在哪兒有關。開哪個門,決定了這只貓明天可能在哪兒。只要你可以不斷壓縮這個可能性,最後壓縮到一個門裏,這問題就解決了。
最開始的時候,這只貓的可能性是1 2 3 4 5 6 7。
如果抓1號門,確定了它不在1,那接下來一天它的可能性還是1 2 3 4 5 6 7。所以這一下是沒意義的。因為貓可以從3到2。
如果抓2號門,確定了它不在2,那接下來一天它的可能性就變成了2 3 4 5 6 7。因為它不在2,所以沒辦法跑到1去。這就壓縮了可能性。
第二天如果抓2,那結果還是2 3 4 5 6 7,毫無進展,所以沒意義。
抓3,結果會變成1 3 4 5 6 7,變個形式,給接下來的一天提供方便。
第三天,抓4,可以確保接下來一天沒有3,然後可能性變成2 4 5 6 7。以此類推,最後就能把門數減少到1個。核心技巧就是如果有一個門,它左邊不可能右邊可能,抓右邊,這樣這個門下次就不可能了。
當然怎麽抓更快這是人類的思路,這個演算法有個好處就是對於電腦來說足夠暴力。你並不需要去教電腦應該抓哪個門,你讓它全抓了然後剪枝加BFS即可。由於結果只和當前狀態有關,所以最多出現
2^n
種可能性,可以有效地剪枝,避免無限深度。配合BFS,總可以最快速度地找到最優解。
import
queue
class
Solution
:
def
__init__
(
self
,
doors
,
path
=
[],
possible
=
set
()):
self
.
path
=
path
self
.
possible
=
possible
self
.
doors
=
doors
def
generate_next_steps
(
self
):
if
not
self
.
possible
:
return
None
next_steps
=
[]
for
i
in
self
.
possible
:
path
=
self
.
path
+
[
i
]
possible
=
set
()
for
elem
in
self
.
possible
:
if
elem
!=
i
:
if
elem
-
1
>=
1
:
possible
.
add
(
elem
-
1
)
if
elem
+
1
<=
self
.
doors
:
possible
.
add
(
elem
+
1
)
s
=
Solution
(
doors
=
self
.
doors
,
path
=
path
,
possible
=
possible
)
next_steps
.
append
(
s
)
return
next_steps
def
find_cat
(
n
):
checked_combination
=
set
()
solutions_queue
=
queue
.
Queue
()
solutions_queue
.
put
(
Solution
(
doors
=
n
,
path
=
[],
possible
=
set
(
i
for
i
in
range
(
1
,
n
+
1
))))
while
True
:
s
=
solutions_queue
.
get
()
next_steps
=
s
.
generate_next_steps
()
if
next_steps
is
None
:
return
s
.
path
for
n
in
next_steps
:
if
tuple
(
n
.
possible
)
not
in
checked_combination
:
checked_combination
.
add
(
tuple
(
n
.
possible
))
solutions_queue
.
put
(
n
)
print
(
find_cat
(
7
))
這裏提供一個隨手寫的程式碼,核心思路就是上面說的,對於每種可能性,分別測試開其中某扇門之後的結果,然後剪去已經試過的狀態,BFS。
python find_cat.py
[2, 3, 4, 5, 6, 2, 3, 4, 5, 6]