[PYTHON] Problem mit der Codeiq-Milchlieferroute

Eine Version, die rekursiv mit einer Baumstruktur gelöst wird

Übe mit einer Holzstruktur.

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

import csv
import sys

"""
Die Suche wird auch durchgeführt, während rekursiv eine Baumstruktur aus dem Wurzelknoten erstellt wird, wobei der Tiefe Priorität eingeräumt wird.
Die Kostenaggregation wird ebenfalls zur Hälfte durchgeführt, und wenn die Mindestkosten überschritten werden, wird die nachfolgende Suche nach untergeordneten Knoten gestoppt.
Ich bin es nicht gewohnt, baumstrukturierte Programme zu schreiben, deshalb habe ich es einfach codiert.
"""


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):
        #Wenn keine verbleibenden Kosten anfallen
        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:
            #Wenn die Kosten am niedrigsten sind, aggregieren Sie auch die Liste der Routen und übergeben Sie sie an den Akku
            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:
                #Registrieren Sie den nächsten Knoten im untergeordneten Knoten
                tmp = Node(i, current, current.cost_from_root + self.cost_table[current.id][i])
                if self.acc.sum < tmp.cost_from_root:
                    #Wenn die Kosten zu diesem Zeitpunkt die Mindestkosten überschreiten, beenden Sie die weitere Exploration
                    return
                current.children.append(tmp)
                #Entfernen Sie die hinzugefügte Nummer aus der Liste und wiederholen Sie den Vorgang
                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])

Eine Version, die Kombinationen im Voraus auflistet

Erstellen Sie eine Sequenz, die keine Wiederholung mit "Permutationen" zulässt, und verwenden Sie dann "für", um die Kosten zu aggregieren. Ich wollte auch etwas cooles mit functools.reduce machen, aber ich konnte es nicht gut machen.

#!/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]))