0

私の数学の授業ははるかに遅れており、現在、私が抱えている問題の適切な解決策を見つけるのに苦労しています。ノードがアクションであり、複数の基準に従って「重み付け」されているツリーがあります。言った行動、それがかかる時間、必要な資源、妨害など...

そして、このツリーで、たとえばコストと時間の両方、または外乱とコストと時間などの両方を最小化するパスを見つけたいと思います。私の問題は、立ち上がる以外に、それを行う方法がわからないことです。グローバルコスト関数F(cost、time、resources、...)を使用し、F(...)の結果を唯一の重みとして使用して、通常のツリートラバーサルアルゴリズムを適用します。では、どうすればFを思い付くことができますか?「F(コスト、時間、リソース)=a*コスト+b*時間+c*リソース」のようなものは非常に「専門的ではない」と感じます...

編集:

「合計」という言葉を避けたかったのは、それが実際に進むべき道かどうかわからなかったためですが、本質的には、それが私が行っていることです。そのトップノードをリーフの1つに移動し、コストを最小限に抑える「パス」または「ブランチ」を選択します。問題は、各ノードが必要な時間、財務コスト、リソース使用量などに基づいて重みを持っていることです。

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

だから私の質問は本当にそうだと思います、それはその機能を選択する方法論がありますか?

あなたの答えとコメントをありがとう、それは今私の頭の中でもう少し明確になり始めています。

4

3 に答える 3

1

Fを思いつくことが最も重要なことです。私があなたに6つの費用と5つの時間または5つの時間と6つの費用を与えることができるならば、あなたはどちらを好みますか?コスト関数はそれを考慮に入れる必要があります。残念ながら、その問題を解決するアルゴリズムはありません。座って、作業中の最適化アプリケーション用にFを書く前に、1週間それを否定しました。最悪の場合、ユーザーがいじくり回すためのパラメーターを残します。

于 2009-01-08T10:45:55.907 に答える
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が線形である場合にのみ意味があります。確かに、コスト、時間、リソースなどは、time(node1-> node2-> node3)= time(node1)+ time(node2)+ time(node3)という意味で加法的関数ですが、一般的にはそうではありません。 Fの場合、線形でない限り。(つまり、F(cost(node1-> node2))= F(cost(node1)+ cost(node2))!= F(cost(node1))+ F(cost(node2))。)

非線形グローバルコスト関数を選択する場合、適切な戦略は、各ノードについて、ルートからそのノードまでの合計コスト、合計時間、合計リソースを計算し、ターミナルノードについてのみFを計算(次に最小化)することです。

于 2009-01-08T13:52:25.377 に答える
0

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

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

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

于 2009-01-08T11:27:43.593 に答える