これは自己定式化された質問の一部であるため、「グーグル」することができず、今まで自分の試みは無駄でした.
グラフG(V,E)が与えられ、 Vの各ノードには利益wiがあり、 Eの各エッジに はciのコストがあります。ここで、バジェットCが与えられます。見つける必要があるのは、 wiの合計が最大である場合に、コストの合計がCよりも小さくなるような単一のパスです。パスには、ここで通常の定義があります。つまり、パスには繰り返し頂点が含まれません。 (単純なパス)。
ハミルトニアン パスがこれの特殊なケースであることは明らかです (設定コスト = |N-1| および各エッジのコスト = 1)。したがって、これは NP 困難な問題であるため、近似解とヒューリスティックスを探しています。 .
数学的に
与えられたグラフG(V,E)
各エッジeに対してci >=0
各頂点vに対してwi >=0
となるような単純なパスPを見つける
P <= Cのすべてのエッジeの合計ci
Pのすべてのvの合計 wiを最大化する
これは、選択的巡回セールスマン問題、または利益のある巡回セールスマンとして知られています。Google Scholar は参考文献を提供できるはずです。遺伝的プログラミングやタブー検索などのメタヒューリスティックがよく使用されます。問題を最適に解決したい場合は、線形計画法の手法がおそらく有効でしょう (残念ながら、扱っているインスタンスのサイズは明示されていません)。パスの長さが短い場合 (たとえば 15 頂点)、色分けも機能する可能性があります。
頭に浮かぶ単純なヒューリスティックの 1 つは、確率論的ヒル クライミングと貪欲なアルゴリズムのバリエーションです。
重みが増加し、コストが減少する価値関数を定義します。例えば：
value(u,v) = w(v) / [c(u,v) + epsilon]
(+ epsilon for the case of c(u,v) = 0)
今、アイデアは次
のとおりです。頂点から、確率で
頂点uに進みます：v
P(v|u) = value(u,v) / sum(u,x) [ for all feasible moves (u,x) ]
続けられなくなるまで繰り返します。
このソリューションは、すぐに 1 つのソリューションを提供しますが、おそらく最適とは言えません。ただし、これは確率的です。時間がある限り、いつでも何度でも再実行できます。
これにより、この問題のいつでもアルゴリズムが得られます。つまり、時間があればあるほど、解決策が改善されます。
いくつかの最適化:
max{value(u,v)}