ノート:迷路

最新のコメント:16 年前 | トピック:迷路はNP完全? | 投稿者:218.223.197.211

迷路はNP完全?

編集

迷路はNP完全問題だという記述がありましたが、これは本当でしょうか。 迷路の各分岐点を頂点とするグラフの最短経路問題を解けば迷路が解けるので、多項式時間で十分な気がします。 なのでいったんコメントアウトしました。 勘違いだったらすみません。

Giant2007 2008年2月26日 (火) 15:13 (UTC)返信


迂回路(ループ)についても記述したいですが、思い浮かびません。--218.223.197.211 2008年3月31日 (月) 09:19 (UTC)返信

ページ「迷路」に戻る。