複数値ノードを持つツリー内の最小パスを見つける

Question

数学の授業はかなり遅れており、現在、次の問題に対する適切な解決策を見つけるのに苦労しています。ノードがアクションであり、複数の基準に従って「重み付け」されているツリーがあります。上記の行動にかかる費用、それにかかる時間、必要なリソース、混乱など...

そして、このツリーで、コストと時間の両方を最小化するパス、または外乱とコストと時間などを最小化するパスを見つけたいと考えています。私の問題は、グローバルコスト関数 F(コスト、時間、リソース、...) を思いつき、F( の結果を使用して通常のツリー走査アルゴリズムを適用すること以外に、その方法がわからないことです。 ..) 私の唯一の体重として。では、どうやって F を思いつくのでしょうか?「F(コスト、時間、リソース) = a * コスト + b * 時間 + c * リソース」のようなものは、非常に「プロフェッショナルではない」ように感じます...

編集：

それが実際に行うべき方法であるかどうかわからないため、「要約」という言葉を避けたかったのですが、本質的にはそれが私がやっていることです。その最上位ノードからいずれかのリーフに至る「パス」または「ブランチ」ごとの総コストを計算し、コストを最小化する「パス」または「ブランチ」を選択します。問題は、各ノードが必要な時間、経済的コスト、リソース使用量などに基づいて重み付けを行っていることです。

したがって、Stephan 氏が言うように、これらすべてのパラメーターをノードごとに 1 つのグローバル コストに削減する式を考え出す必要があるのは避けられないようです。その後、ツリーを下降しながらノード間で合計を合計し、次のパスを選択します。総コストを最小限に抑えます。

それで、私の質問は実際には、その関数を選択する方法論はあるのか、ということだと思います。

ご回答とコメントをありがとうございます。頭の中で少しずつ明確になり始めています。

Answer 1

(1, 4)、(1, 5)、(2, 3)、(3, 3) のような 4 つのペア (x, y) があるとします。ここで、「x と y の両方」を最小化したいとします。どういう意味ですか？最初に x を最小化し、次に y を最小化すると、(1, 4) になります。最初に y を最小化し、次に x を最小化すると、(2, 3) が見つかります。

あなたの観察のように、グローバルコスト関数 F(x, y) を選択しない限り、「両方」の意味がわかりません。(いずれにせよ、F が選択されると、依然として複数の最小点が存在する可能性があります。) ところで、私の意見では、線形結合 (正の乗数 a、b、c は「重み」として理解される) はまったく「専門的ではない」わけではありません。少なくとも、より適切なコスト関数が何であるかわからない場合には。

編集：

したがって、Stephan 氏が言うように、これらすべてのパラメーターをノードごとに 1 つのグローバル コストに削減する式を考え出す必要があるのは避けられないようです。その後、ツリーを下降しながらノード間で合計を合計し、次のパスを選択します。総コストを最小限に抑えます。

注意。実際、この戦略は F が線形の場合にのみ意味を持ちます。確かにコスト、時間、リソースなど。は、時間(ノード1 -> ノード2 -> ノード3) = 時間(ノード1) + 時間(ノード2) + 時間(ノード3)という意味で加算関数ですが、一般に、これは線形でない限り、Fには当てはまりません。(すなわち、F(コスト(ノード1 -> ノード2)) = F(コスト(ノード1) + コスト(ノード2)) != F(コスト(ノード1)) + F(コスト(ノード2))。)

非線形グローバル コスト関数を選択した場合、正しい戦略は、ノードごとに総コスト、総時間、ルートからそのノードまでの総リソースを計算し、終端ノードについてのみ F を計算 (その後最小化) することです。

Answer 2

Fを考えることが最も重要です。 6コストと5時間、または5時間と6コストを提供できる場合、どちらを選びますか？コスト関数はそれを考慮する必要があります。残念ながら、この問題を解決するアルゴリズムはありません。私が座っていて、作業中の最適化アプリケーションのためにFを書く前に、私はそれを1週間拒否しました。最悪の場合は、ユーザーがパラメータを調整できるようにしておきます。

Answer 3

A * のような通常のグラフ検索アルゴリズムが機能しないのはなぜですか？

パスコスト関数では、関連する基準の現在の合計を使用できます。目標までの距離はもっと難しい...

それは、すべてまたは一部のノードについて事前に計算された、最も近い葉までの距離である可能性がありますが、非常に高価に聞こえます。ツリーの構造によっては、より安価に過小評価することもできます。たとえば、完全にバランスが取れていれば、ささいなことです。