Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- -- [[ API file ]] --
- local w,h = term.getSize()
- function calculateDistance(tNode1,tNode2)
- local turnCost = 0
- local deltaY,deltaZ
- local y1 = tNode1[2]
- local z1 = tNode1[3]
- local y2 = tNode2[2]
- local z2 = tNode2[3]
- deltaZ = z2-z1
- deltaY = y2-y1
- if deltaZ == 0 or deltaY == 0 then
- turnCost = 0
- else
- turnCost = 1
- end
- return math.abs(deltaZ) + math.abs(deltaY) + turnCost
- --return math.sqrt( (z2-z1)^2 + (y2-y1)^2 )
- end
- function twoOptSwap(route, i, k)
- local new_route = {}
- for c = 1,i-1 do
- table.insert(new_route,route[c])
- end
- for c = k,i,-1 do
- table.insert(new_route,route[c])
- end
- for c = k+1,#route do
- table.insert(new_route,route[c])
- end
- return new_route
- end
- function calculateTotalDistance(route)
- local total = 0
- for i = 1,#route-1 do
- total = total + calculateDistance(route[i],route[i+1])
- end
- return total
- end
- function display(route,distance)
- local l,h = term.getSize()
- shell.run("clear")
- for i = 1,#route-1 do
- paintutils.drawLine(route[i][2],route[i][3],route[i+1][2],route[i+1][3],colors.lime)
- end
- for i,coord in pairs(route) do
- term.setBackgroundColor(colors.yellow)
- term.setTextColor(colors.magenta)
- term.setCursorPos(coord[2]+1,coord[3]+1)
- term.write(string.char(i+64))
- end
- term.setBackgroundColor(colors.black)
- term.setTextColor(colors.white)
- term.setCursorPos(1,h)
- term.write(distance)
- end
- --[[nodes = {}
- local x= 12
- for y = 0,finaly do
- for z = 0,finalz do
- local id = getBlockId(x,y,z)
- if id and id > 0 then
- table.insert(nodes,{x,y,z})
- end
- end
- end
- ]]
- -- [[ Main File ]] --
- route = {}
- route[1] = {1,28,3}
- route[2] = {1,36,13}
- route[3] = {1,20,8}
- route[4] = {1,8,8}
- route[5] = {1,44,5}
- route[6] = {1,32,13}
- route[7] = {1,20,17}
- --route[8] = {1,28,3}
- route2 = {
- {6,5,1},
- {6,1,2},
- {6,1,5},
- {6,2,1},
- {6,2,6},
- {6,3,1},
- {6,3,6},
- {6,4,1},
- {6,4,6},
- {6,5,6},
- {6,6,2},
- {6,6,5},
- }
- for i = 1,#route2 do
- route2[i][2] = (route2[i][2]/6)*w
- route2[i][3] = (route2[i][3]/6)*h
- end
- function nearest_neighbor(existing_route)
- local best_distance = 10000
- local best_route = { route[1] }
- for i = 2,#existing_route-1 do
- for k = i+1,#existing_route do
- local new_distance = calculateDistance(existing_route[i],existing_route[k])
- if new_distance < best_distance then
- best_distance = new_distance
- best_route[i+1] = existing_route[k]
- end
- end
- end
- return best_route,best_distance
- end
- function tsp_algorithm(existing_route)
- local improve = 0
- while improve < 3 do
- local best_distance = calculateTotalDistance(existing_route)
- for i = 2,#existing_route-1 do
- for k = i + 1, #existing_route do
- new_route = twoOptSwap(existing_route, i, k)
- new_distance = calculateTotalDistance(new_route)
- if new_distance < best_distance then
- improve = 0
- existing_route = new_route
- best_distance = calculateTotalDistance(existing_route)
- display(existing_route,best_distance)
- sleep(0)
- end
- end
- end
- improve = improve + 1
- end
- return existing_route, best_distance
- end
- --local best_route,best_distance = tsp_algorithm(nodes)
- --display(best_route,best_distance)
- --term.setCursorPos(1,h-#best_route)
- --for i,v in pairs(best_route) do
- --print(i," ",v[2]," ",v[3])
- --end
- --textutils.pagedPrint(textutils.serialize(best_route))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement