[PYTHON] Problème de voie de livraison de lait Codeiq

Une version qui résout récursivement avec une structure arborescente

Pratiquez l'utilisation d'une structure en bois.

#!/bin/env python
# coding:utf-8

import csv
import sys

"""
La recherche est également effectuée lors de la création récursive d'une structure arborescente à partir du nœud racine avec la priorité donnée à la profondeur.
L'agrégation des coûts est également effectuée à mi-chemin et lorsque le coût minimum est dépassé, la recherche ultérieure des nœuds descendants est arrêtée.
Je ne suis pas habitué à écrire des programmes structurés en arborescence, alors je les ai codés simplement.
"""


class Accumulator(object):
    def __init__(self, sum=sys.maxsize, route=[]):
        self.sum = sum
        self.route = route


class Node(object):
    def __init__(self, id, parent=None, cost_from_root=0, children=[]):
        self.id = id
        self.parent = parent
        self.cost_from_root = cost_from_root
        self.children = children

    def __repr__(self):
        return "%i, cost: %i -> %s\n" % (self.id, self.cost_from_root, repr(self.children))


class DeliveryCostCalculator(object):

    def __init__(self, filename):
        self.filename = filename
        self.cost_table = self.get_table()
        self.acc = Accumulator(sys.maxsize, [])

    def get_table(self):
        cost_table = []
        with open(self.filename, 'r') as f:
            reader = csv.reader(f)
            for row in reader:
                cost_table.append([int(col) for col in row])
        return cost_table

    def calc_total_cost(self, current):
        #S'il n'y en a plus, coût total
        tmp = Node(0, current, current.cost_from_root + self.cost_table[current.id][0], None)
        current.children.append(tmp)
        if tmp.cost_from_root < self.acc.sum:
            #Si le coût est le plus bas, agréger également la liste des itinéraires et la transmettre à l'accumulateur
            self.acc.sum = tmp.cost_from_root

            def _min_r(n, acc):
                if n.parent is None:
                    acc.append(n)
                    return acc
                acc.append(n)
                return _min_r(n.parent, acc)
            self.acc.route = _min_r(tmp, [])
            self.acc.route.reverse()

    def main(self):
        def _f(slot, current):
            if len(slot) <= 0:
                self.calc_total_cost(current)
                return
            for i in slot:
                #Enregistrer le nœud suivant dans l'enfant
                tmp = Node(i, current, current.cost_from_root + self.cost_table[current.id][i])
                if self.acc.sum < tmp.cost_from_root:
                    #Si le coût à ce stade dépasse le coût minimum, arrêtez toute exploration supplémentaire
                    return
                current.children.append(tmp)
                #Supprimer le numéro ajouté de la liste et se répéter
                a = list(slot)
                a.remove(i)
                _f(a, tmp)
        _f(range(1, len(self.cost_table)), Node(0))
        return self.acc.sum, self.acc.route


if __name__ == "__main__":
    c = DeliveryCostCalculator(sys.argv[1])
    (sum, route) = c.main()
    print(sum)
    print(" -> ".join([str(n.id + 1) for n in route]))
    # print([(n.id + 1, n.cost_from_root) for n in route])

Une version qui répertorie les combinaisons à l'avance

Créez une séquence qui n'autorise pas la répétition avec des «permutations», puis utilisez «pour» pour regrouper les coûts. Je voulais aussi faire quelque chose de cool avec functools.reduce, mais je ne pouvais pas bien le faire.

#!/bin/env python
# coding:utf-8

import csv
import sys
from itertools import permutations

def get_table(filename):
    cost_table = []
    with open(filename, 'r') as f:
        reader = csv.reader(f)
        for row in reader:
            cost_table.append([int(col) for col in row])
    return cost_table


def main(filename):
    cost_table = get_table(filename)
    min_cost = sys.maxsize
    min_route = ()
    for p in permutations(range(1, len(cost_table))):
        # add an initial and a last node
        p = (0,) + p + (0,)
        total_cost = 0
        for i in range(len(p)):
            if i == len(p) - 1:
                continue
            # get a cost between a current and next
            total_cost += cost_table[p[i]][p[i + 1]]
            if min_cost < total_cost:
                break
        # print(total_cost, p)
        if total_cost < min_cost:
            min_cost = total_cost
            min_route = p
    return min_cost, min_route


if __name__ == "__main__":
    c, r = main(sys.argv[1])
    print(c)
    print(" -> ".join([str(n + 1) for n in r]))