如何实现一圈的随机对成对交换和最陡下降成对交换(SDPI)？

Question

我正在努力解决这些问题(提供了代码)：

1. 使用lap.py代码(以及需要的lap_h1.py和lap_h2.py )，为LAP实现随机对成对的交换启发式。在您的过程中使用100,000个随机对。
2. 使用作为问题1的一部分开发的代码，为LAP实现最陡峭的下降，成对的交换(SDPI)启发式。

任何帮助都将不胜感激！谢谢!

#parseCSV.py
#
def parseCSV(filename, dataType='float', returnJagged=False, fillerValue=0, delimiter=',', commentChar='%'):
    # define the matrix
    matrix = []
    # open the file
    with open(filename, 'U') as csvfile :
        # read all the lines
        csvFile = csvfile.readlines()
        maxSize = 0
        # iterate through each line
        for line in csvFile :
            # check for comments, go to next line if this is a comment
            if(line.startswith(commentChar)):
                continue
            # make sure it's not a blank line
            if line.rstrip():
                # Check for the data type (float or int)
                if dataType == 'float':
                    row = map(float, filter(None, line.rstrip().split(delimiter)))
                elif dataType == 'int':
                    row = map(int, filter(None, line.rstrip().split(delimiter)))                
                matrix.append(row)
                if len(row) > maxSize :
                    maxSize = len(row)
        # unless returnJagged is true, fill the blank values
        if not returnJagged :
            for row in matrix :    
                row += [fillerValue] * (maxSize - len(row))
        if len(matrix) == 1 :
            # This is a vector, just return a 1-D vector
            matrix = matrix[0]
    return matrix

def printMatrix(matrix):
    for row in matrix:
        for cell in row:
            print cell,

#lap.py
#           
import sys
import copy
# need to update this to point to the location of parseCSV.py
sys.path.append('c:\\svns\\code\\python')
from parseCSV import parseCSV

# 
# initialize the problem - fname is the csv file with the cost matrix
# 
def initialize(fname, show):
    # read the costs matrix from the csv file
    costs = parseCSV(fname)
    # people[i] is the index of the task assigned to person i 
    #   or -1 if the person does not have an assigned task
    people = []
    # tasks[j] is the index of the person assigned to task j
    #   or -1 if the task is unassigned
    tasks = []
    # create the people and tasks lists
    for k in range(len(costs)):
        people.append(-1)
        tasks.append(-1)
    if show:
        print '{} people, {} tasks, {}x{} costs, lb = {:.2f}'.format(
            len(people), 
            len(tasks), 
            len(costs), 
            len(costs),
            simple_lb(costs))
    return costs, people, tasks

#
# show_solution - displays the current solution
#
def show_solution(costs, people, tasks):
    for k in range(len(people)):
        if people[k] > -1:
            task = 'T{}'.format(people[k])
            cost = costs[k][people[k]]
        else:
            task = 'n/a'
            cost = 0.0
        print '\tP{}, {}, {:.2f} '.format(k, task, cost)
    print '\nTotal cost: {:.2f} (lower bound: {:.2f})'.format(
        calc_cost(costs, people)[0],
        simple_lb(costs)
        )

#
# calc_cost - calculates the current solution cost
#
def calc_cost(costs, people):
    total_cost = 0
    num_assigned = 0
    # for each person
    for k in range(len(people)):
        # make sure the person has an assigned task
        if people[k] != -1:
            total_cost += costs[k][people[k]]
            num_assigned += 1
    return total_cost, num_assigned

#
# low_cost_task - finds the lowest cost available task for the
#   specified person
#
def low_cost_task(costs, person, tasks):
    # initialize with the biggest possible number
    min_cost = 1e308 
    # index of the low-cost task
    min_idx = -1
    # loop through all tasks
    for k in range(len(tasks)):
        # if the task is currently unassigned
        if tasks[k] == -1:
            # is the task lower cost than the current minimum?
            if costs[person][k] < min_cost:
                min_cost = costs[person][k]
                min_idx = k
    return min_idx, min_cost

#
# simple_lb - calculates a simple lower bound based on low-cost assignment
#
def simple_lb(costs):
    # min cost task for each person
    total_cost1 = 0;
    for k in range(len(costs)) :
        total_cost1 += min(costs[k])
    # min cost person for each task
    total_cost2 = 0;
    for k in range(len(costs)):
        total_cost2 += min([c[k] for c in costs])
    # return the better of the two bounds
    return max(total_cost1, total_cost2)

#
# clear_solution - clears the incumbent solution
#
def clear_solution(people, tasks):
    for k in range(len(people)):
        people[k] = -1
    for k in range(len(tasks)):
        tasks[k] = -1

#
# store_solution
#
def store_solution(people, tasks, cost, seq):
    # create the dictonary
    solution = {}
    # need to use copy since the lists are mutable
    solution['people'] = copy.copy(people)
    solution['tasks'] = copy.copy(tasks)
    solution['obj_val'] = cost
    solution['seq'] = copy.copy(seq)
    return solution

#
# main
#
def main():
    # default values
    fname = 'r.csv'
    # argv[0] - file name
    if len(sys.argv) > 1:
        fname = sys.argv[1]
    # initialize
    costs, people, tasks = initialize(fname, 1)
    # Simple assignment - person k gets task k for all k
    for k in range(len(people)):
        people[k] = k;
        tasks[k] = k;
    print '\nSolution:'
    show_solution(costs, people, tasks)

# if cmd line, execute main
if __name__ == '__main__' : main()

#lap_h1.py
#
import sys
# need to update this to point to the location of parseCSV.py
sys.path.append('c:\\svns\\code\\python')
from parseCSV import parseCSV

# 
# initialize the problem - fname is the csv file with the cost matrix
# 
def initialize(fname):
    # read the costs
    costs = parseCSV(fname)
    # people[i] is the index of the task assigned to person i 
    #   or -1 if the person does not have an assigned task
    people = []
    # tasks[j] is the index of the person assigned to task j
    #   or -1 if the task is unassigned
    tasks = []
    # create the people and tasks lists
    for k in range(len(costs)):
        people.append(-1)
        tasks.append(-1)
    return costs, people, tasks

#
# show_solution - displays the current solution
#
def show_solution(costs, people, tasks):
    for k in range(len(people)):
        if people[k] > -1:
            task = 'T{}'.format(people[k])
            cost = costs[k][people[k]]
        else:
            task = 'n/a'
            cost = 0.0
        print '\tP{}, {}, {:.2f} '.format(k, task, cost)
    print '\nTotal cost: {:.2f} (lower bound: {:.2f})'.format(
        calc_cost(costs, people)[0],
        simple_lb(costs)
        )

#
# calc_cost - calculates the current solution cost
#
def calc_cost(costs, people):
    total_cost = 0
    num_assigned = 0
    # for each person
    for k in range(len(people)):
        # make sure the person has an assigned task
        if people[k] != -1:
            total_cost += costs[k][people[k]]
            num_assigned += 1
    return total_cost, num_assigned

#
# low_cost_task - finds the lowest cost available task for the
#   specified person
#
def low_cost_task(costs, person, tasks):
    # initialize with the biggest possible number
    min_cost = 1e308 
    # index of the low-cost task
    min_idx = -1
    # loop through all tasks
    for k in range(len(tasks)):
        # if the task is currently unassigned
        if tasks[k] == -1:
            # is the task lower cost than the current minimum?
            if costs[person][k] < min_cost:
                min_cost = costs[person][k]
                min_idx = k
    return min_idx, min_cost

#
# simple_lb - calculates a simple lower bound based on low-cost assignment
#
def simple_lb(costs):
    # min cost task for each person
    total_cost1 = 0;
    for k in range(len(costs)) :
        total_cost1 += min(costs[k])
    # min cost person for each task
    total_cost2 = 0;
    for k in range(len(costs)):
        total_cost2 += min([c[k] for c in costs])
    # return the better of the two bounds
    return max(total_cost1, total_cost2)

#
# main
#
def main():
    # initialize parameters then check for command line changes
    show_intermediate = 1
    fname = 'r.csv'
    if len(sys.argv) > 1:
        fname = sys.argv[1]
        if len(sys.argv) > 2:
            show_intermediate = int(sys.argv[2])
    # initialize the data structures using the cost matrix file
    costs, people, tasks = initialize(fname)
    print '{} people, {} tasks, {}x{} costs, lb = {:.2f}'.format(
        len(people), 
        len(tasks), 
        len(costs), 
        len(costs),
        simple_lb(costs))
    # for each person, assign their low-cost task
    for k in range(len(people)):
        # find the low cost task for this person
        task, min_cost = low_cost_task(costs, k, tasks)
        # assign task to person and person to task
        people[k] = task
        tasks[task] = k
        # show current assignment
        if show_intermediate:
            if people[k] != -1:
                print 'Assigned P{} task T{} at cost {:.2f}'.format(
                    k,
                    people[k], 
                    min_cost
                    )
    # show solution
    print '\nFinal solution:'
    show_solution(costs, people, tasks)

# if cmd line, execute main
if __name__ == '__main__' : main()

#lap_h2.py
#
import sys
from random import sample
import lap

#
# solve - solves the problem for a given assignment sequence
#
def solve(costs, people, tasks, seq):
    total_cost = 0
    for k in seq:
        # find the low cost task for this person
        task, min_cost = lap.low_cost_task(costs, k, tasks)
        # assign task to person and person to task
        people[k] = task
        tasks[task] = k
        total_cost += min_cost
    return total_cost

#
# main
#
def main():
    # default values
    nreps = 100
    fname = 'r.csv'
    # argv[0] - file name
    # argv[1] - number of replications
    if len(sys.argv) > 1:
        fname = sys.argv[1]
        if len(sys.argv) > 2:
            try:
                nreps = int(sys.argv[2])
            except:
                print 'Invalid parameters.  Syntax: lab_h2.py fname nreps'
                exit()
    # initialize
    costs, people, tasks = lap.initialize(fname, 1)
    # initial solution with the "natural" sequence
    cost = solve(costs, people, tasks, range(len(people)))
    # store the solution -- need to use deepcopy so the best
    #   incumbent solution is not overwritten
    solution = lap.store_solution(people, tasks, cost, range(len(people)))
    print 'Iteration {:3d}  Cost: {:.2f}'.format(-1, solution['obj_val'])
    # iterate
    for k in range(nreps):
        # clear the current assignments
        lap.clear_solution(people, tasks)
        # sample a random sequence
        seq = sample(range(len(people)), len(people))
        # solve with the random sequence
        cost = solve(costs, people, tasks, seq)
        print 'Iteration {:3d}  Cost: {:.2f}'.format(k, cost)
        # if this solution is better than the best incumbent, 
        #   make it the best incumbent.
        if cost < solution['obj_val'] :
            solution = lap.store_solution(people, tasks, cost, seq)
    # show solution
    print '\nFinal solution:'
    print 'Sequence: {}'.format(solution['seq'])
    lap.show_solution(costs, solution['people'], solution['tasks'])

# if cmd line, execute main
if __name__ == '__main__' : main()

Answer 1

Stack溢出处的编程社区试图帮助您处理有关特定编程语言的编码错误和其他查询。让我说清楚，我们不是来帮你做作业的。下次你发帖的时候，要有你自己的东西。

谢谢你，耶杜拉格