Исследовательский потенациал молодых ученых: взгляд в будущее - 2017

«Исследовательский потенциал молодых ученых: взгляд в будущее» 197 2017 ляется к уже имеющемуся множеству. Когда такие ребра кончаются, алгоритм прекращает свою работу. Рассмотрим пример реализации данного алгоритма. city(DistanceCities,ResultConfiguration):‐ city(DistanceCities,[],ResultConfiguration). city(Distances,Existing,ResultConfiguration):‐ pick_minimum_edge_wo_cycle(Distances,Existing,Edge), city(Distances,[Edge|Existing],Result), ResultConfiguration=[Edge|Result]. city(Distances,Existing,ResultConfiguration):‐ not(pick_minimum_edge_wo_cycle(Distances,Existing,Edge)), ResultConfiguration=[]. pick_minimum_edge_wo_cycle(Distances,Existing,Edge):‐ pick_minimum_edge_wo_cycle(Distances,Existing,[],Edge), not(Edge=[]). pick_minimum_edge_wo_cycle([],_,ToCompare,ToCompare). pick_minimum_edge_wo_cycle([Edge|L],Existing,ToCompare,Result):‐ less_edge(Edge,ToCompare), no_cycle(Edge,Existing), pick_minimum_edge_wo_cycle(L,Existing,Edge,Result). pick_minimum_edge_wo_cycle([Edge|L],Existing,ToCompare,Result):‐ not(less_edge(Edge,ToCompare)), pick_minimum_edge_wo_cycle(L,Existing,ToCompare,Result). less_edge(edge(_X1,_Y1,Z1), edge(_X2, _Y2, Z2)):‐ Z1<Z2. less_edge(edge(_X1,_Y1,_Z1),[]). no_cycle(edge(X,Y,_),Existing):‐ not(search(X,Y,Existing,[])). search(X,Y,Edges,_):‐ member(edge(X,Y,_),Edges). search(X,Y,Edges,_):‐ member(edge(Y,X,_),Edges). search(X,Y,Edges,PassedVertices):‐ member(edge(X,Z,_),Edges), not(member(Z,PassedVertices)), search(Z,Y,Edges,[Z|PassedVertices]). search(X,Y,Edges,PassedVertices):‐ member(edge(Z,X,_),Edges), not(member(Z,PassedVertices)), search(Z,Y,Edges,[Z|PassedVertices]). Изначально, текущее множество ребер результирующего под‐ графа устанавливается пустым. После чего выбирается ребро мини‐