回答編集履歴
1
近似解であることを追記
test
CHANGED
@@ -1,6 +1,8 @@
|
|
1
1
|
最短経路問題を解くためには、いろいろな解法が知られていますが、
|
2
2
|
|
3
3
|
どれもたいてい「試したこと」の全探索よりは、探索時間が短くなると思います。
|
4
|
+
|
5
|
+
(ただし、巡回セールスマン問題のようにNP困難の場合は、近似解になります)
|
4
6
|
|
5
7
|
|
6
8
|
|
@@ -22,8 +24,10 @@
|
|
22
24
|
|
23
25
|
|
24
26
|
|
25
|
-
|
27
|
+
ヒューリスティックな解法だと、全探索のように最善の解が得られる保証はありません。
|
26
28
|
|
27
29
|
が、ノード数が増えていくと、全探索では実時間ですべて探しきれなくなってきます。
|
28
30
|
|
29
31
|
そこで、ビジネスでは効率が大事なので、ベストでなくてもベターな解で満足します。
|
32
|
+
|
33
|
+
|