3

私は解決するのが非常に難しい問題を抱えており、最速のルートを見つけるためにどのアルゴリズムを使用できるのか疑問に思っています。無向グラフは正と負の調整で構成され、これらの調整は迷路をナビゲートするボットまたは物に影響を与えます。私が抱えている問題は、+または-のループを含む迷路です。例が役立つかもしれません：-

  1. ノードAはオブジェクトに10ポイントを与えます

  2. ノードBはオブジェクトから15を取得します

  3. ノードCはオブジェクトに20ポイントを与えます

route = ""

開始ノードはAで、終了ノードはCです。

グラフ構造を次のように与えます：-

a(+10)-----b(-15)-----c+20

 node() means the node loops to itself   - and + are the adjustments

ループのないノードはc+20であるため、ノードcの正の調整は20ですが、ループはありません。

ボットまたはオブジェクトのリソースに10ポイントがある場合、最適なパスは次のようになります：-

a > b > c    the object would have 25 points when it arrives at c

route = "a、b、c"

これは実装が非常に簡単です。次の課題は、適切なノードに戻る方法を知ることです。各ノードで、隣接するノードとその調整レベルのいずれかを見つけることができると仮定します。これが次の例です：-

ボットが5ポイントのみで開始した場合、最適なパスは次のようになります。

a > a > b > c the bot would have 25 points when arriving at c

route = "a、a、b、c"

これは非常に単純なグラフでしたが、ノードがたくさんある場合、ボットは、可能なルートを追跡しながら、適切なノードでループするか、ある適切なノードから別のノードに移動するかを判断するのが非常に困難になります。

そのようなルートはバックトラックキューになります。

より難しい例では、多くの行き来が発生します

ボットには10​​ポイントあります

a(+10)-----b(-5)-----c-30

a> b> a> b> a> b> a> b> a>b>c残り5ポイント。

ボットがそれを行うことができる別の方法は次のとおりです：-

a> a> a> b> c

これはより効率的な方法ですが、これをどのようにプログラムできるかは、部分的に私の質問です。

これを解決するための優れたアルゴリズムを知っている人はいますか。iveはすでにベルマンフォード法とダイクストラ法を調べましたが、これらはループパスではなく単純なパスを提供するだけです。

何らかの形で、または何らかの形のヒューリスティックで再帰的になる可能性がありますか？

あなたのアナロジーを参照してください：-

私はあなたが言っていることを理解していると思います、これまでのところ、少し疑似がより明確になるでしょうroute（）

q.add(v)
best=v
hash visited(v,true)

while(q is not empty)
    q.remove(v)
    for each u of v in G

        if u not visited before
            visited(u,true)
            best=u=>v.dist
        else
            best=v=>u.dist
4

3 に答える 3

2

これは単純な動的計画問題です。

パスの特定の長さについて、ノードごとに、そのノードで終了する最適なコストと、そのルートがどこから来たのかを知りたいとします。（その長さのデータはハッシュに保存でき、ルートはリンクリストに保存できます。）

このデータがnステップあるとします。次に、n + 1番目の場合は、白紙の状態から始めて、n番目の各回答を取得し、それを1ノード前方に移動します。ノードに到達した場合は、データがありません。最良の結果よりも優れている場合は、そのノードのデータを改善されたスコアで更新し、ルートを追加します（このノードが前のリンクリストにリンクしているだけです）。

必要なステップ数でこれを取得したら、既存の最適なルートを持つノードを見つけ、スコアとルートをリンクリストとして取得します。

========

アルゴリズムを実装する実際のコードは次のとおりです。

class Graph:
    def __init__(self, nodes=[]):
        self.nodes = {}
        for node in nodes:
            self.insert(node)

    def insert(self, node):
        self.nodes[ node.name ] = node

    def connect(self, name1, name2):
        node1 = self.nodes[ name1 ]
        node2 = self.nodes[ name2 ]
        node1.neighbors.add(node2)
        node2.neighbors.add(node1)

    def node(self, name):
        return self.nodes[ name ]

class GraphNode:
    def __init__(self, name, score, neighbors=[]):
        self.name = name
        self.score = score
        self.neighbors = set(neighbors)

    def __repr__(self):
        return self.name

def find_path (start_node, start_score, end_node):
    prev_solution = {start_node: [start_score + start_node.score, None]}
    room_to_grow = True
    while end_node not in prev_solution:
        if not room_to_grow:
            # No point looping endlessly...
            return None
        room_to_grow = False
        solution = {}
        for node, info in prev_solution.iteritems():
            score, prev_path = info
            for neighbor in node.neighbors:
                new_score = score + neighbor.score
                if neighbor not in prev_solution:
                    room_to_grow = True
                if 0 < new_score and (neighbor not in solution or solution[neighbor][0] < new_score):
                    solution[neighbor] = [new_score, [node, prev_path]]
        prev_solution = solution
    path = prev_solution[end_node][1]
    answer = [end_node]
    while path is not None:
        answer.append(path[0])
        path = path[1]
    answer.reverse()
    return answer

そして、これがそれを使用する方法のサンプルです：

graph = Graph([GraphNode('A', 10), GraphNode('B', -5), GraphNode('C', -30)])
graph.connect('A', 'A')
graph.connect('A', 'B')
graph.connect('B', 'B')
graph.connect('B', 'B')
graph.connect('B', 'C')
graph.connect('C', 'C')

print find_path(graph.node('A'), 10, graph.node('C'))

各ノードをそれ自体に明示的に接続したことに注意してください。問題によっては、それを自動化することもできます。

（無限ループが1つ残っている可能性があることに注意してください。開始ノードのスコアが0で、そこから抜け出す方法がないとします。その場合、永久ループになります。この場合のチェックを追加するには作業が必要です。 。）

于 2012-04-25T16:09:17.893 に答える
0

あなたの説明に少し混乱しています。あなたは最短経路アルゴリズムを探しているようです。その場合、グーグルはあなたの友達です。

与えた例では、-veの調整があります。これは、グラフトラバーサルの通常の用語では実際には+veのコストになるはずです。つまり、コストが最も低いパスを見つけたいので、より多くの+ve調整が必要です。

グラフにトラバースするのに有益なループがある場合（つまり、調整によってコストを削減するか、ポイントを増やす）、ループをもう一度通過するとスコアが向上するため、最適なパスは定義されていません。

于 2012-04-25T16:02:31.750 に答える
0

ここにいくつかの擬似コードがあります

steps = []
steps[0] = [None*graph.#nodes]
step = 1
while True:
     steps[step] = [None*graph.#nodes]
     for node in graph:
         for node2 in graph:
             steps[step][node2.index] = max(steps[step-1][node.index]+node2.cost, steps[step][node2.index])

     if steps[step][lastnode] >= 0:
         break;
于 2012-04-25T16:30:08.577 に答える