LINUX.ORG.RU
решено Форум — Development  

Не могли бы вы, ребята, помочь мне, переделав этот Python-код для использования NetworkX вместо OR-инструментов Google? Заранее спасибо!

 ,


0

0

Здравствуйте, я запутался в этом коде, не мог бы кто-нибудь переписать его для меня. Буду очень признателен!

Вот код:

from ortools.graph.python import min_cost_flow

def main():
    smcf = min_cost_flow.SimpleMinCostFlow()

    team_a = [1,3,5]
    team_b = [2,4,6]

    start_nodes = ([0,0] + [11,11,11] + [12,12,12] + [1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6] + [7,8,9,10])
    end_nodes = ([11,12] + team_a + team_b + [7,8,9,10,7,8,9,10,7,8,9,10,7,8,9,10,7,8,9,10,7,8,9,10] + [13,13,13,13])
    capacities = ([2,2] + [1,1,1] + [1,1,1] + [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] + [1,1,1,1])
    costs = ([0,0] + [0,0,0] + [0,0,0] + [90,76,75,70,35,85,55,65,125,95,90,105,45,110,95,115,60,105,80,75,45,65,110,95] + [0,0,0,0])

    source = 0
    sink = 13
    tasks = 4
    supplies = [tasks,0,0,0,0,0,0,0,0,0,0,0,0,-tasks]

    for i in range(0, len(start_nodes)):
        smcf.add_arc_with_capacity_and_unit_cost(start_nodes[i], end_nodes[i],
                                                 capacities[i], costs[i])
    for i in range(0, len(supplies)):
        smcf.set_node_supply(i, supplies[i])

    status = smcf.solve()

    if status == smcf.OPTIMAL:
        print('Total cost = ', smcf.optimal_cost())
        print()
        for arc in range(smcf.num_arcs()):
            if (smcf.tail(arc) != source and smcf.tail(arc) != 11 and
                    smcf.tail(arc) != 12 and smcf.head(arc) != sink):

                if smcf.flow(arc) > 0:
                    print('Worker %d assigned to task %d.  Cost = %d' %
                          (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc)))
    else:
        print('There was an issue with the min cost flow input.')
        print(f'Status: {status}')


if __name__ == '__main__':
    main()

И вывод кода:

Total cost =  250

Worker 1 assigned to task 9.  Cost = 75
Worker 2 assigned to task 7.  Cost = 35
Worker 5 assigned to task 10.  Cost = 75
Worker 6 assigned to task 8.  Cost = 65

Сомневаюсь что тебе кто-то поможет

    team_a = [1,3,5]
    team_b = [2,4,6]

    start_nodes = ([0,0] + [11,11,11] + [12,12,12] + [1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6] + [7,8,9,10])
    end_nodes = ([11,12] + team_a + team_b + [7,8,9,10,7,8,9,10,7,8,9,10,7,8,9,10,7,8,9,10,7,8,9,10] + [13,13,13,13])
    capacities = ([2,2] + [1,1,1] + [1,1,1] + [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] + [1,1,1,1])
    costs = ([0,0] + [0,0,0] + [0,0,0] + [90,76,75,70,35,85,55,65,125,95,90,105,45,110,95,115,60,105,80,75,45,65,110,95] + [0,0,0,0])

    source = 0
    sink = 13
    tasks = 4
    supplies = [tasks,0,0,0,0,0,0,0,0,0,0,0,0,-tasks]

Это невозможно прочитать. Что вообще все эти числа обозначают?

Total cost =  250

Worker 1 assigned to task 9.  Cost = 75
Worker 2 assigned to task 7.  Cost = 35
Worker 5 assigned to task 10.  Cost = 75
Worker 6 assigned to task 8.  Cost = 65

А ну тогда все просто. Я переписал скрипт:

msg = """
Total cost =  250

Worker 1 assigned to task 9.  Cost = 75
Worker 2 assigned to task 7.  Cost = 35
Worker 5 assigned to task 10.  Cost = 75
Worker 6 assigned to task 8.  Cost = 65
"""
print(msg)
Aswed ★★★★★
()

Мне удалось сделать это самому xax:

import networkx as nx

def main():
    G = nx.DiGraph()

    team_a = [1,3,5]
    team_b = [2,4,6]
    start_nodes = ([0,0]+[11,11,11]+[12,12,12]+[1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6]+[7,8,9,10])
    end_nodes = ([11,12]+team_b+team_a+[7,8,9,10,7,8,9,10,7,8,9,10,7,8,9,10,7,8,9,10,7,8,9,10]+[13,13,13,13])
    capacities = ([2,2]+[1,1,1]+[1,1,1]+[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]+[1,1,1,1])
    costs = ([0,0]+[0,0,0]+[0,0,0]+[90,76,75,70,35,85,55,65,125,95,90,105,45,110,95,115,60,105,80,75,45,65,110,95]+[0,0,0,0])
    source = 0
    sink = 13
    tasks = 4
    supplies = [tasks,0,0,0,0,0,0,0,0,0,0,0,0,-tasks]

    for i in range(len(start_nodes)):
        G.add_edge(start_nodes[i], end_nodes[i], capacity=capacities[i], weight=costs[i])

    for i in range(len(supplies)):
        G.nodes[i]['demand']=-supplies[i]

    flowDict=nx.min_cost_flow(G)

    total_cost=0
    for u in flowDict:
        for v in flowDict[u]:
            flow = flowDict[u][v]
            if flow > 0:
                edge = G.edges[u, v]
                cost = edge['weight'] * flow
                if cost > 0:
                    total_cost += cost
                    if u != source and v != sink:
                        print(f'Worker {u} assigned to task {v}. Cost = {edge["weight"]}')
    print(f'\nTotal cost: {total_cost}')

main()
habanero
() автор топика
Development