Held karp och schemaalgoritm
Jag fick för ett tag sedan hjälp här att skapa en Held-Karp algoritm som hittar närmsta vägen i en plocksekvens.
Jag har också skrivit en schemagenerator i PHP, som helt enkelt testar olika kombinationer där den börjar att placera den anställda som har minst kompatibla avdelningar och sedan arbetar sig "uppåt" i värde. Varje avdelningar kan rymma olika antal medarbetare. Problemet med den är att den inte fattar när det inte går ihop sig, eftersom den testar oändligt tills alla har fått en placering.
Jag funderade på om man kunde använda Held Karp till detta istället för att försäkra sig om att placeringen går ihop, oavsett om den inte är HELT optimal utan bara nosar på den bästa lösningen. Jag tänker att det är bättre än att man riskerar att den tuggar och aldrig når ett slut.
Men då skulle den behöva se lite annorlunda ut än min nuvarande held-karp som jag fick hjälp med antar jag, och som i nuläget används till att beräkna kortaste vägen. Avståndsmatrisen blir väl kompetensmatrisen i detta fallet, men frågan är hur det skulle se ut med själva algoritmen, då vill man välja dom med lägst/högst siffra i kompabilitet med avdelningarna, och inte kortast väg i en viss ordning. Och blir problemet mer komplex då olika avdelningar rymmer olika antal medarbetare?
Här nedan följer koden som hittar närmsta vägen för en plockrutt. Jag skulle vilja modifiera denna så att det går att använda samma typ av map.csv men för att generera att schema. Är detta lättare sagt än gjort? Med tanke på att avdelning 1 kan rymma 5 personer, avdelning 2 kan rymma 11 personer osv.
Vill också påpeka att jag inte skrivit en enda rad i Pyhon, det fick jag hjälp med. Däremot har jag gjort en hel del med PHP-koden.
package main
import (
"bytes"
"encoding/csv"
"fmt"
"io"
"log"
"math/bits"
"math/rand"
"os"
"runtime"
"strconv"
"strings"
"time"
)
const MaxInt = int(^uint(0) >> 1)
// IntSet
type IntSet struct {
Storage uint
}
func (vs IntSet) Contains(value int) bool {
return (vs.Storage & (1 << uint(value))) != 0
}
func (vs IntSet) Count() int {
return bits.OnesCount(vs.Storage)
}
func (vs *IntSet) Insert(value int) {
vs.Storage |= 1 << uint(value)
}
func (vs *IntSet) Remove(value int) {
vs.Storage &= ^(1 << uint(value))
}
func (vs IntSet) Value() int {
return int(vs.Storage >> 1)
}
func (vs IntSet) Iter() []int {
n := vs.Count()
v := make([]int, n)
for c, i := 0, 0; c < n; i++ {
if vs.Contains(i) {
v[c] = i
c++
}
}
return v
}
func (vs IntSet) String() string {
buf := bytes.Buffer{}
buf.WriteString("{")
delim := ""
for c, i := 0, 0; c < vs.Count(); i++ {
if vs.Contains(i) {
buf.WriteString(fmt.Sprintf("%s%v", delim, i))
delim = ","
c++
}
}
buf.WriteString("}")
return buf.String()
}
// Combinations 'k' integers from a serie '1..n'
type Combs []IntSet
func combWithLen(n, k, first int, vs IntSet, acc Combs) Combs {
if k > vs.Count() {
for x := first; x <= n; x++ {
s := vs
s.Insert(x)
acc = combWithLen(n, k, x+1, s, acc)
}
} else {
acc = append(acc, vs)
}
return acc
}
func Comb(n, k int) Combs {
return combWithLen(n, k, 1, IntSet{}, Combs{})
}
// Held Karp
type Path struct {
Cost int
From int
}
func minPath(paths []Path) Path {
m := paths[0]
for i := 1; i < len(paths); i++ {
if m.Cost > paths[i].Cost {
m = paths[i]
}
}
return m
}
func pathFromTo(from, to int, c [][]Path, dists CostMatrix, prev IntSet) Path {
p := Path{}
p.Cost = c[prev.Value()][from-1].Cost + dists[from][to]
p.From = from
return p
}
func reverse(a []int) []int {
for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
a[i], a[j] = a[j], a[i]
}
return a
}
// CostMatrix
type CostMatrix [][]int
func (dists CostMatrix) CalcCostToSubsets(c [][]Path, edges, subsetSz int) {
maxWorkers := runtime.NumCPU()
workers := 0
done := make(chan bool)
for _, visited := range Comb(edges, subsetSz) {
if workers == maxWorkers {
<-done
} else {
workers += 1
}
go func(vs IntSet) {
subset := vs.Iter()
// Find the lowest cost to get to this subset
for _, k := range subset {
prev := vs
prev.Remove(k)
res := []Path{}
for _, m := range subset {
if m != k {
res = append(res, pathFromTo(m, k, c, dists, prev))
}
}
if len(res) > 0 {
c[vs.Value()][k-1] = minPath(res)
}
}
done <- true
}(visited)
}
// Wait for all workers to finish
for ; workers > 0; workers -= 1 {
<-done
}
}
func (dists CostMatrix) ShortestPath() (int, []int) {
n := len(dists)
c := make([][]Path, 1<<uint(n-1))
for i := 0; i < len(c); i++ {
c[i] = make([]Path, n-1)
}
// Add paths from start to first steps
for k := 1; k < n; k++ {
c[1<<uint(k-1)][k-1] = Path{dists[0][k], 0}
}
for s := 2; s < n; s++ {
dists.CalcCostToSubsets(c, n-1, s)
}
visited := IntSet{}
for k := 1; k < n; k++ {
visited.Insert(k)
}
// Add path back to start and calculate optimal cost
res := []Path{}
for k := 1; k < n; k++ {
res = append(res, pathFromTo(k, 0, c, dists, visited))
}
p := minPath(res)
cost := p.Cost
// Backtrack to find path
steps := make([]int, n+1)
for i := 1; i < n; i++ {
steps[i] = p.From
from := p.From
p = c[visited.Value()][p.From-1]
visited.Remove(from)
}
return cost, reverse(steps)
}
func (c CostMatrix) MaxDigitWidth() (width int) {
for row := 0; row < len(c); row++ {
for col := 0; col < len(c[row]); col++ {
w := 0
for d := c[row][col]; d > 0; d /= 10 {
w += 1
}
if width < w {
width = w
}
}
}
return
}
func (c CostMatrix) String() string {
fmtstr := fmt.Sprintf("%%%vv", c.MaxDigitWidth())
buf := bytes.Buffer{}
for row := 0; row < len(c); row++ {
if row == 0 {
buf.WriteString("{\n")
}
buf.WriteString(" { ")
for col := 0; col < len(c[row]); col++ {
buf.WriteString(fmt.Sprintf(fmtstr, c[row][col]))
if col != len(c[row])-1 {
buf.WriteString(", ")
}
}
buf.WriteString(" },\n")
if row == len(c)-1 {
buf.WriteString("}")
} else {
}
}
return buf.String()
}
func Abs(n int) int {
if n < 0 {
return -n
}
return n
}
func Max(a, b int) int {
if a < b {
return b
}
return a
}
type Location struct {
shelf int
level int
}
func cost(from, to Location) int {
dx := Abs(from.shelf - to.shelf)
dy := Abs(from.level-to.level) * 2
return Max(dx, dy)
}
func zeroMatrix(dim int) CostMatrix {
var c CostMatrix = make([][]int, dim)
for i := range c {
c[i] = make([]int, dim)
}
return c
}
func genMatrix(nodes, depth, height int) CostMatrix {
rand.Seed(time.Now().UnixNano())
c := zeroMatrix(nodes)
l := make([]Location, nodes)
for i := range l {
l[i] = Location{rand.Intn(depth), rand.Intn(height)}
}
for row := 0; row < nodes; row++ {
for col := row + 1; col < nodes; col++ {
c[row][col] = cost(l[row], l[col])
c[col][row] = c[row][col]
}
}
return c
}
func readMatrix(r io.Reader) CostMatrix {
cr := csv.NewReader(r)
rec, err := cr.ReadAll()
if err != nil {
log.Fatalln(err)
}
M := zeroMatrix(len(rec))
for row, line := range rec {
for col, str := range line {
v, err := strconv.ParseInt(strings.TrimSpace(str), 10, 32)
if err != nil {
log.Fatalln(err)
}
M[row][col] = int(v)
}
}
return M
}
func GetCostMatrix() CostMatrix {
if len(os.Args) == 1 {
return readMatrix(os.Stdin)
}
arg := os.Args[1]
if strings.HasSuffix(arg, ".csv") {
file, err := os.Open(arg)
if err != nil {
log.Fatalln(err)
}
return readMatrix(file)
}
dim, err := strconv.ParseInt(arg, 10, 32)
if err != nil {
log.Fatalln(err)
}
return genMatrix(int(dim), 50, 9)
}
// Program entrypoint
func main() {
start := time.Now()
time.Sleep(time.Second * 2)
c := GetCostMatrix()
fmt.Println(c)
fmt.Println(c.ShortestPath())
elapsed := time.Since(start)
fmt.Printf("Processen tog %s sekunder", elapsed)
}
hkgo.php (Som presenterar datan i webläsaren)
<?php
$output = [];
$cmd = 'C:/go/bin/go run c:/Go/src/hello/test.go map.csv 2>&1';
exec($cmd, $output, $return_var);
var_dump($output);
?>
Skapa map.csv
<?php
#SQL connection
$mysqli = mysqli_connect("127.0.0.1","root","","findpath");
$query = "SELECT * FROM coordinates";
$conn = (mysqli_query($mysqli, $query));
#general settings for total rows and columns
$total_rows = 9;
$total_columns = 10;
#functions to convert XXYYZ to array[y][x]
function row($string) {
$split_string = str_split($string);
$row = $split_string[2].$split_string[3];
#convert 0X to X if < two digits
if($row < 10) {
$row = $split_string[3];
}else {
$row = $split_string[2].$split_string[3];
}
return $row;
}
function column($string) {
$split_string = str_split($string);
$column = $split_string[4];
return $column;
}
#create "map" set all = 0
for($i = 0; $i < $total_columns + 1; $i++) {
for($j = 0; $j < $total_rows + 1; $j++) {
$input[$i][$j] = 0;
}
}
#set initial coordinate to 1
$input[0][0] = 1;
while($dbrow = mysqli_fetch_array($conn)) {
$number = $dbrow['number'];
#define return from functions as variables
$row = row($number);
$column = column($number);
#put values into array
$input[$row][$column] = 1;
}
function genPoints($inputb) {
$width = count($inputb[0]);
$height = count($inputb);
$points = [];
$counter = 0;
for($row=0; $row < $height; $row++) {
for($col=0; $col < $width; $col++) {
if($inputb[$row][$col] == 1) {
$points[] = array($row, $col);//[$row, $col];
$counter++;
}
}
}
return $points;
}
function cost($from, $to) {
list($row1, $col1) = $from;
list($row2, $col2) = $to;
/* if you pass column 4, add 4 points */
if (($col1 <= 4 && $col2 >= 5) || ($col2 <= 4 && $col1 >= 5)) {
return max((abs($row1 - $row2)), abs($col1 - $col2) * 2 + 4);
}else {
return max(abs($row1 - $row2), abs($col1 - $col2) * 2);
}
}
function genGraph($points) {
$sz = count($points);
$matrix = [];
for($from=0; $from < $sz; $from++) {
for($to=0; $to < $sz; $to++) {
$matrix[$from][$to] = cost($points[$from], $points[$to]);
}
}
return $matrix;
}
$points = genPoints($input);
$matrix = genGraph($points);
$fp = fopen('map.csv', 'w');
foreach ($matrix as $fields) {
fputcsv($fp, $fields);
}
fclose($fp);
?>
