的訪問每一個「特殊」的點上一格

Question

我停留在這個問題所需的步驟最少人數：

---

假設我們有以下米乘ñ網格配置（或矩陣）g^在字母表{0，X，Y}

G =
0 0 X .. X
0 0 X 0 ..
XY 0 .. X
： ： ：         ：
0 X 0 .. 0

查找在最小一些步驟要求有良好下界 Y訪問網格中的每個X的格子（矩陣中的X的Ieeach）至少一次，其中Ÿ可以移動離開，右，了和下一個細胞在一個時間？

（該ÿ和X'在網格ģ小號被任意放置，該ÿ和X的可以是對矩陣，所述的同樣數量的任何地方在矩陣上的X是任意的，並且在矩陣上必須有正好一個Y）。

---

當然沒有某種數學公式的，可以給臺階的確切數量（由於它是一個TSP問題）。

但我們怎樣才能找到一個足夠緊下界爲實際步數（即相對容易使用的算法來計算，例如）？

我所看到的建議上：

Using A* to solve Travelling Salesman

，並建議有該最小生成樹的總成本可以是TSP問題的一個很好的下限。

但與此相反的問題有，在這裏，在這個問題上，我們是不訪問每個對電網的點的，但我們需要訪問每個需要的「特殊」點上網至少一次，並得到他們我們可能需要在網格上訪問一些「非特殊」點，所以我不知道最小生成樹看起來像對於這個問題（也許如何調整Kruskal的alg算法找到它）。

（注：我以前遇到過，而試圖找出一個啓發式的計算爲Ÿ必須在網格上參觀各X「s的路徑A *網格搜索這個問題至少一次）

感謝您的任何提示或幫助。

Answer 1

如果我正確地理解了這個問題，就要求對所述問題的目標有一個嚴格的下限。這種邊界實際上是實例的最小生成樹;距離將是X和Y節點（在這種情況下是一些離散的Euklidean距離）之間的成對最短路徑。結合的緊密度可以看出考慮它看起來像

YXXXXX...X 

在生成樹的重量（節點即數量參觀減一）的最短路徑的權重從Y相匹配的一個實例最右邊的X節點。總之，Kruskal的算法不需要修改來計算最小生成樹。