Исследовательская помощь: алгоритм поиска траектории

Question

Не технический вопрос, просто требующий точки в правильном направлении для моих исследований.

Существуют ли какие-либо модели, которые обращаются со следующей проблемой:

Нахождение маршрута, начиная с X, проходящей через А, В, С в наиболее эффективном порядке. В приведенном ниже случае X, A, C, B - оптимальный путь (12).

Благодаря

Answer 1

вы можете посмотреть на коммивояжера. Есть много ресурсов для того, как реализовать это, поскольку это очень распространенная проблема программирования. https://en.wikipedia.org/wiki/Travelling_salesman_problem

Answer 2

Это реализация Dijkstra's Algorithm в Python:

def find_all_paths(graph, start, end, path=[]): 
    required=('A', 'B', 'C') 
    path = path + [start] 
    if start == end: 
     return [path] 
    if start not in graph: 
     return [] 
    paths = [] 
    for node in graph[start]: 
     if node not in path: 
      newpaths = find_all_paths(graph, node, end, path) 
      for newpath in newpaths: 
       if all(e in newpath for e in required): 
        paths.append(newpath) 
    return paths  

def min_path(graph, start, end): 
    paths=find_all_paths(graph,start,end) 
    mt=10**99 
    mpath=[] 
    print '\tAll paths:',paths 
    for path in paths: 
     t=sum(graph[i][j] for i,j in zip(path,path[1::])) 
     print '\t\tevaluating:',path, t 
     if t<mt: 
      mt=t 
      mpath=path 

    e1=' '.join('{}->{}:{}'.format(i,j,graph[i][j]) for i,j in zip(mpath,mpath[1::])) 
    e2=str(sum(graph[i][j] for i,j in zip(mpath,mpath[1::]))) 
    print 'Best path: '+e1+' Total: '+e2+'\n' 

if __name__ == "__main__": 
    graph = {'X': {'A':5, 'B':8, 'C':10}, 
      'A': {'C':3, 'B':5}, 
      'C': {'A':3, 'B':4}, 
      'B': {'A':5, 'C':4}} 
    min_path(graph,'X','B') 

Печать:

All paths: [['X', 'A', 'C', 'B'], ['X', 'C', 'A', 'B']] 
     evaluating: ['X', 'A', 'C', 'B'] 12 
     evaluating: ['X', 'C', 'A', 'B'] 18 
Best path: X->A:5 A->C:3 C->B:4 Total: 12 

В «Кишки» рекурсивно найти все пути и фильтрации только теми путями, которые посещают искомая узлы ('A', 'B', 'C'). Затем пути суммируются, чтобы найти минимальный расход пути.

Есть, конечно, более эффективный подходит, но трудно быть проще. Вы попросили модель, так что вот работающая реализация.