0
я борюсь с этими проблемами (коды предоставляются):Как реализовать случайные пары парного обмена и наискорейшего спуска парного обмена (SDPI) эвристики для LAP?
Использование кода lap.py (и lap_h1.py и lap_h2.py по мере необходимости), осуществлению случайные пары парного обмена эвристики для LAP. Используйте 100 000 случайных пар для вашей процедуры.
Используя код, разработанный как часть проблемы 1, нанесите на себя самый крутой спуск , парный обмен (SDPI) эвристический для LAP.
ЛЮБАЯ ПОМОЩЬ БУДЕТ ПРИЗНАНА! Спасибо!
#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()