首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何找到拾取多个对象的最短路径?

问如何找到拾取多个对象的最短路径?
EN

Stack Overflow用户
提问于 2019-02-10 07:08:56
回答 1查看 50关注 0票数 0

我想找出机器人从特定空间中挑选一些物体的最佳路径,我问用户他要挑选的东西的名称,当他键入2时,问题已经解决了,但当他键入更多时,例如,当他键入3时,我的程序会给他两个物体之间的最短路径,然后将该路径添加到列表中,机器人以相同的顺序挑选对象,这不是我想要的,我希望它找到最短的方法来挑选所有对象

代码语言:javascript
复制
from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = float('inf')
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

thing = [
    ["a0", "b0", 2], ["a0", "a1", 1],
    ["a1", "a2", 1], ["a2", "a3", 1],
    ["a3", "a4", 1], ["a4", "b4", 2],

    ["b0", "c0", 2], ["b0", "b1", 1],
    ["b1", "b2", 1], ["b2", "b3", 1],
    ["b3", "b4", 1], ["b4", "c4", 2],

    ["c0", "c1", 1], ["c1", "c2", 1],
    ["c2", "c3", 1], ["c3", "c4", 1],


    ["a4", "b4", 2], ["a4", "a5", 1],
    ["a5", "a6", 1], ["a6", "a7", 1],
    ["a7", "a8", 1], ["a8", "b8", 2],

    ["b4", "c4", 2], ["b4", "b5", 1],
    ["b5", "b6", 1], ["b6", "b7", 1],
    ["b7", "b8", 1], ["b8", "c8", 2],

    ["c4", "c5", 1], ["c5", "c6", 1],
    ["c6", "c7", 1], ["c7", "c8", 1]
]
other=[]

for i in thing:
    a=[]
    a.append(i[1])
    a.append(i[0])
    a.append(i[2])
    other.append(a)

result = thing + other


graph = Graph(result)

NumberOfThings = int(input('how many things would you like to pick ? '))

ThingsToPick=[]

for i in range(0, NumberOfThings):
    name=input(' - ')
    ThingsToPick.append(name)

len=len(ThingsToPick)

way=[]

for i in range(0,len-1):
    for j in list(graph.dijkstra(ThingsToPick[i], ThingsToPick[i+1])):
        way.append(j)

print(way)
EN

回答 1

Stack Overflow用户

发布于 2019-02-10 08:05:57

我不熟悉python中的顶点和边。下面的代码有一个在顶点之间的距离函数(a,b),你需要用真实的距离函数来替换它。

代码语言:javascript
复制
import itertools

def distance(alist)
   pairs=[[l[i],l[i+1]] for i in range(0,len(l)-2)]
   d=0
   for pair in pairs:
      d += distancebetweenvertices(pair)
   return d

l=['a','b','c','d']
ways=itertools.combinations(l)
bestdistance=distance(l)
bestway=l
for way in ways:
   if distance(way) < bestdistance:
      bestway=way

首先,我们为列表中顶点之间的总距离定义一个函数。distance函数将列表分成两对,使用(占位符) distancebetweenvertices函数计算两个列表之间的距离,并对其求和。

然后,它通过itertools创建一个所有可能方法的列表,将bestway和bestdistance的起始值设置为用户输入的顺序和相应的距离。现在,如果总距离较小,它会检查所有可能的方式。如果是,它用这个方式和这个距离替换bestway和bestdistance。最后,你将在bestway和best distance变量中得到最佳方式和对应距离。

希望这能有所帮助。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/54611724

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档